Шашки, оказывается, решены полностью в слабом смысле – то-есть посчитаны все оптимальные деревья и известно, как играть, чтобы была ничья.
“Известно, как играть, чтобы была ничья” не означает, кстати, умение выигрывать, и вот почему. Наиболее рациональной стратегией программы, “понявшей”, что ничья гарантированно достижима, вообще говоря не является скорейшее сведение партии к ничьей.
Рациональной стратегией будет поддержание потенциально ничейной позиции максимально долго, ожидая, что оппонент ошибётся.
Это прекрасное соображение, и ещё целую пачку похожих, я обнаружил как раз в публикации “Solving the Game of Checkers” по мотивам алгоритма программы Chinook.
Я пытался прикинуть схему оценки количества “мусорных” ветвей деревьев событий, совершенно, правда, в другой области – и наткнулся на эту работу, где такие соображения есть.
Картиночка вот оттуда.
15 страниц PDF, хорошо вдумчиво читается за часик. Много оценок, подходов и вообще соображений общего плана – и никакой зауми.
Советую http://library.msri.org/books/Book29/files/schaeffer.pdf