Здравствуйте, Шебеко Евгений, Вы писали:

M>>Ну я немного копал в сторону шахматного программирования... А так, просто интересно, какие эвристики используются? Ну типа ходов-киллеров, ...
ШЕ>Treat-space search

ШЕ>В отличии от шахмат, здесь есть позиции, на которые надо обязательно реагировать.
В шахматах это техница ФВ (форсированного варианта). Начиная с некоторой глубины дальше считаются только шахи и взятия.

ШЕ>Собственно этот Allis заметил, что люди ищут сначала последовательность вилок, которые приводят к победе,
ШЕ>практически не обращая внимания на ходы противника. Если такая последовательность найдена, то начинают её уже проверять.
ШЕ>Ключевая особенность в том, что для построения последовательности на угрозу отвечают сразу всеми защитными ходами одновременно. Если последовательность всё ещё можно построить, то уже потом угроза анализируется на контратаки.

По сути это и есть NULL-move


ШЕ>У него ещё есть эвристика нулевого хода. Она у него даётся как: если игрок пропускает свой ход, то противник может построить выигрышную
ШЕ>последовательность вилок. Сказано, что типа эта позволяет видеть скрытые угрозы. Если честно, я не допёр как этим пользоваться, поэтому не использую.
ШЕ>Как бы непонятно, ну увидим мы угрозу на ход раньше. Совсем неочевидно, какими ходами её предотвратить. Это может быть ход на то место, откуда угроза разивается или к примеру боковые ходы, которые могут способствовать развитию контратаки.

Наверное пользоваться так: (1) поскольку мы ищем победу крестиков, то эвристику NULL-move имеет смысл выполнять для ноликов; (2) Нолики пропускают ход, и мы ищем атаку со стороны крестиков; (3) В случае, когда есть форсированный вариант, приводящий крестиков к победе, то можно эту последовательность рассматривать как киллер (т. е. при переборе всех возможных ходов ноликов, опровержение начинать с этого варианта). Вообще, alpha-beta очень чувствительна к порядку перебора вариантов.



ШЕ>Блин. Всё равно ничего не понятно получается. В общем сложно объяснить. Для того чтобы было понятно, нужно писать статью и подбирать картинки с примерами.
Все понятно, не переживай

Еще (A) идея Z-orbice. Многие позиции будут повторятся (+симметрии). Хотелось бы построить по позициям какой-нить хэш, чтобы это можно было быстро детектировать. Самая простая идея, построить таблицу, где каждой клетке поля соответствует некоторое число для крестиков (для ноликов соответсвенно). Потом мы делаем две суммы и mod на некоторое простое число. Что позволит быстро находить одинаковые позиции. Конечно, это не покрывает симметрии, но... Еще (B) имеет смысл расспросить данов по поводу теории дебютов, и взять ее за основу. Фактически, в свое время я читал, что в рендзю (запрещены вилки 3x3 и 4x4 черным) с выбором дебюта белыми (после третьего хода белые выбирают, хотят ли они играть черными) результативность составляла 55% в пользу белых. Соотвественно, уже сейчас теории этой игры очень сильно развита. (C) Еще для позиций, для которых не установлен результат, можно прикрутить ОФ для того, чтобы управлять alpha-beta.

Далее, очень сомнительно выглядит цифра 1 600 000 позиций. На моем компе шахматный движок без ОФ легко дает 3 000 000 позиций в секунду на одном ядре. Возможно, можно оптимизировать генерацию ходов.