Продление Маркова

Тема в разделе "Машинное отделение", создана пользователем WildCat, 7 авг 2006.

  1. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Попробовал приделать продление Маркова. Я его понимаю так: если пустой ход опровергается фигурой, которой противник сделал последний ход, значит это был ход с угрозой и стоит посмотреть подальше.
    Реализация этого простого правила с удлиннением на 3/4 ply привела к потере нескольких plies и после 128 тестовых партий -144 пунктов рейтинга.
    Может быть я упустил какую-то очень важную деталь?

    Реализация примерно такая:
    Код:
        int null_score = Search(depth - null_depth, ply + 1, -beta, -beta-1);

    if (null_score < -20000) depth += MATE_THREAT;
    else if (null_score < beta && SearchLine[ply + 1].from == SearchLine[ply - 1].to) depth += MARKOFF_EXT;
    Может быть для этого продления нельзя пользоваться стандартным пустым ходом, а нужно вызывать специальный с окном (beta + 150, beta + 151) или (MATE - 100, MATE)?
    WildCat, 7 авг 2006
    #1

  2. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я понял это продление по другому...
    Если Предыдущий ход Пустой.
    Если перед пустым To = Текущий ход From, тогда продлеваем (ход той-же фигурой через пустой ход)
    Чтоб частично убрать проблему горизонта "через пустой ход".
    NS, 7 авг 2006
    #2
  3. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Так совсем не понятно, по какой причине продлевать все ходы последней ходившей фигуры?
    Это может быть какой-то совсем левый ход ферзем. После которого у этого ферзя столько ходов, что мы устанем их всех продлевать.
    WildCat, 7 авг 2006
    #3

  4. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В другой ветке я об этом писал - добавляем два условия.
    1. Этот повторный ход - не ход назад (то есть Ng1-f3, Nf3-g1 - не продляем)
    2. Сразу на это поле пойти было нельзя, Допустим первый ход Qd1-d2, второй Qd2-e2 - Если ход Qd1-e2 возможен сразу (то есть он в любом случае возможен сразу :) ), то не продляем.
    NS, 7 авг 2006
    #4
  5. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Это что-то меняет?
    WildCat, 7 авг 2006
    #5

  6. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да, это уменьшает количество ходов с продлениями.
    А само продление позволяет видеть проходы пешек и маневры фигур, которые без этого программа отсекает при помощи Null Move,
    Вдобавок вполне возможно что это позволит увеличить R в методе пустого хода. Но я сам еще не проверял.

    Продлеваются все, так как среди них с большей вероятностью может оказаться хороший ход. (Так как ход фигуры обычно создает угрозу именно от этой фигуры - ход Ферзя может угрожать матом ферзем, ход пешки - угроза прохода в ферзи, ход конем - перевод коня на сильное поле) и т.д.
    NS, 7 авг 2006
    #6
  7. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Все-таки это совсем другая идея нежели в продлении Маркова. Ты ее придумал тебе и проверять первому.
    В продлении Маркова не было идеи улучшить пустой ход, а была идея находить угрозы с помощью пустого хода.
    WildCat, 7 авг 2006
    #7

  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Попробую проверить :)
    Эти два условия можно добавить и в идею Маркова (опровергающий (после пустого) - не ход назад, и ход на поле, на которое нельзя было пойти изначально)
    NS, 7 авг 2006
    #8

  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Можно наверно добавить условие, что опровергающая оценка меньше статистической.
    NS, 7 авг 2006
    #9

  10. Booot Учаcтник

    • Участник
    Рег.:
    05.06.2006
    Сообщения:
    140
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Как я понял идею Маркова:
    Если пустой ход опровергается, то мы смотрим: не опровергался ли пустой ход ply-2 (то есть за ту же сторону) назад тем же ходом или угрозой побить на том же поле или ту же фигуру? Этим мы находим , например, ситуации, когда противник систематически "нависает" на какой-то наш слабый пункт (или просто гоняет фигуру пешками по доске ), а у нас практически единственные ходы для защиты от этой угрозы. То есть вариант практически форсированный и его нужно удлиннять горизонта для.
    Booot, 8 авг 2006
    #10

  11. Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    > Если пустой ход опровергается, то мы смотрим: не опровергался ли пустой ход ply-2 (то есть за ту же сторону) назад
    > тем же ходом или угрозой побить на том же поле или ту же фигуру? Этим мы находим , например, ситуации, когда
    > противник систематически "нависает" на какой-то наш слабый пункт (или просто гоняет фигуру пешками по доске ),
    > а у нас практически единственные ходы для защиты от этой угрозы. То есть вариант практически форсированный
    > и его нужно удлиннять горизонта для.

    Да, все верно. Перебор после пустого хода, если он не вызвал отсечения, возвращает нам ход-угрозу. Идея состоит в том, что если сделана пара ходов, а угроза осталась прежней, то мы производим продление. Тут есть несколько разных вариантов. У меня продление происходит в том случае, если а) ход-угроза один и тот же; б) ходы-угрозы представляют собой взятие одной и той же фигуры.
    Сергей Марков, 10 авг 2006
    #11
  12. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Понятно. Попробую сделать.

    Сергей!
    Может у тебя еще есть что рассказать? Например, что нового в SmarThink 1.0 по сравнению с 0.17a?
    WildCat, 11 авг 2006
    #12

  13. atoku Модератор

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    2.949
    Симпатии:
    9
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    А мне интересно, есть ли таки в Смарте функциональное программирование или нет :)
    atoku, 11 авг 2006
    #13

  14. Fruit Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    12.02.2006
    Сообщения:
    2.201
    Симпатии:
    64
    Репутация:
    3
    Оффлайн
    А что такое функциональное программирование?
    Fruit, 11 авг 2006
    #14

  15. atoku Модератор

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    2.949
    Симпатии:
    9
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    atoku, 11 авг 2006
    #15

  16. Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Ой, там на самом деле очень-очень много нового. Вы лучше спрашивайте конкретно о том, что интересует, а я буду рассказывать.
    Сергей Марков, 11 авг 2006
    #16

  17. Сергей Марков Учаcтник

    • Участник
    Рег.:
    13.05.2006
    Сообщения:
    136
    Симпатии:
    6
    Репутация:
    0
    Оффлайн
    Ну, он же не на LISP'е написан :)
    На самом деле код SmarThink очень архаичен. Написан на самом что ни на есть ANSI C с ассемблерными вставками. Структура программы в целом классическая: каскад, Search(...), Evaluate(...), CalculateExtensions(...). А вот среди применяемых методов много неклассических.
    Сергей Марков, 11 авг 2006
    #17
  18. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Я сделал продление примерно так.
    Код сразу после вызова Search в пустом ходе:
    Код:
        refut_move[ply] = 0;
    if (score < -20000)    depth += MATE_THREAT;
    else if (score < beta)
    {
        refut_move[ply] = search_move[ply + 1];
        if (ply >= 3)
        {
            if (refut_move[ply] == refut_move[ply - 2]) depth += MARKOFF_EXT;
        }
    }
    Продление MARKOFF_EXT = 3/4 ply.

    Правильно я все сделал?

    Стала заметно медленее и wacnew.epd решает чуть хуже. В реальных играх пока не тестировал.

    Чтобы отловить угрозу одной и той же фигуре:
    if (refut_move[ply].cap != empty && refut_move[ply - 2].cap != empty && refut_move[ply].to == refut_move[ply - 2].to)

    Так?
    WildCat, 11 ноя 2006
    #18
  19. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Лучше так:
    if (refut_move[ply - 2].to == search_move[ply - 1].from && refut_move[ply].to == search_move[ply - 1].to)
    WildCat, 11 ноя 2006
    #19

Поделиться этой страницей