Шашки

Шашки, оказывается, решены полностью в слабом смысле – то-есть посчитаны все оптимальные деревья и известно, как играть, чтобы была ничья.

“Известно, как играть, чтобы была ничья” не означает, кстати, умение выигрывать, и вот почему. Наиболее рациональной стратегией программы, “понявшей”, что ничья гарантированно достижима, вообще говоря не является скорейшее сведение партии к ничьей.

Рациональной стратегией будет поддержание потенциально ничейной позиции максимально долго, ожидая, что оппонент ошибётся.

Это прекрасное соображение, и ещё целую пачку похожих, я обнаружил как раз в публикации “Solving the Game of Checkers” по мотивам алгоритма программы Chinook.

Я пытался прикинуть схему оценки количества “мусорных” ветвей деревьев событий, совершенно, правда, в другой области – и наткнулся на эту работу, где такие соображения есть.

Картиночка вот оттуда.

15 страниц PDF, хорошо вдумчиво читается за часик. Много оценок, подходов и вообще соображений общего плана – и никакой зауми.

Советую http://library.msri.org/books/Book29/files/schaeffer.pdf