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

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

  1. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    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
    Оффлайн

    NS Нефёдов Сергей баннер

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

    WildCat Коршунов Игорь Команда форума

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

    NS Нефёдов Сергей баннер

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

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Это что-то меняет?
     
    WildCat, 7 авг 2006
    #5
  6. NS
    Оффлайн

    NS Нефёдов Сергей баннер

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

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

    WildCat Коршунов Игорь Команда форума

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

    NS Нефёдов Сергей баннер

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

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Можно наверно добавить условие, что опровергающая оценка меньше статистической.
     
    NS, 7 авг 2006
    #9
  10. Booot
    Оффлайн

    Booot Учаcтник

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

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

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

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

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Понятно. Попробую сделать.

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

    atoku Модератор

    Репутация:
    0
    А мне интересно, есть ли таки в Смарте функциональное программирование или нет :)
     
    atoku, 11 авг 2006
    #13
  14. Fruit
    Оффлайн

    Fruit Александр баннер

    Репутация:
    3
    А что такое функциональное программирование?
     
    Fruit, 11 авг 2006
    #14
  15. atoku
    Оффлайн

    atoku Модератор

    Репутация:
    0
    atoku, 11 авг 2006
    #15
  16. Сергей Марков
    Оффлайн

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

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

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

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

    WildCat Коршунов Игорь Команда форума

    Репутация:
    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. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    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