Шашки

[ermouth]

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

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

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

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

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

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

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

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

Comments

[service-picky.livejournal.com]

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

думаю, для людей это тоже весьма частая стратегия, и вполне рациональная. В переговорах, например, двух хорошо подготовленных квалифицированных соперников.

[ermouth.livejournal.com]

Конечно, это называется «тянуть время, изматывать противника» )

Я просто, кажется, никогда не встречал такого в работах по машинным реализациям.

[service-picky.livejournal.com]

кстати, думал об этом не в разрезе затяжки времени. Просто - хорошо посчитал бюджет переговоров, готов, есть конструктивное решение, проходящее где-то по ожидаемой "середине" интересов сторон, а может и вовсе winwin. И вот, вооруженный и застрахованный, спокойный и неторопливый, решаешь выслушать оппонента...

про машинную реализацию не скажу ) но все игры машин с человеками, начиная с морского боя в игровых автоматах, ждут ошибки человека ))