winpooh: (Default)
Среди людей, лишь краем уха слышавших об успешной игре Фрицев и Рыбок против Каспарова, Крамника и пр., распространено мнение, что компьютеры "решили шахматы" - т.е. в каждой позиции программы могут найти идеальный ход. Да что там краем уха, отголоски этого мифа встречаются даже среди неплохих шахматистов-любителей, начинающих играть в адванс - современный, компьютеризованный вариант игры по переписке. После первых партий, с попытками следовать за компьютером ход-в-ход "по первой линии", они бывают немало удивлены :)) Впрочем, адванс - это тема для отдельной записи (и не одной), а сейчас о действительно решённых - с математической строгостью - играх.

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

Самый известный пример полностью решённой игры - классическая игра Ним. Оптимальный алгоритм для неё формулируется в виде правила сохранения некоторого легко вычислимого инварианта, так что построение базы данных не требуется.

Противоположный пример - малофигурные шахматные окончания. Никаких общих правил нет, но таблицы Налимова (объёмом до нескольких терабайт в случае 6-7-фигурных эндшпилей) обеспечивают идеальную игру в произвольной позиции. Наблюдать за ходами компьютера в некоторых окончаниях (вроде Ф+С против Ф+К) - очень хорошее средство разубедить себя в том, что шахматы есть игра логическая и стратегическая. Ходы производятся с человеческой точки зрения совершенно хаотичные и бессмысленные, но расстояние до мата (40... 30... 20 ходов...) неизменно сокращается.

При слабом решении требуется всё то же самое, но не для произвольной, а для начальной позиции. Так в 2007 году была решена игра чекерс (английские шашки). Насколько мне известно, факт решения чекерса не сильно огорчил игроков - мировые чемпионаты по-прежнему проводятся. Тем не менее, вы можете сыграть с онлайн-версией программы Chinook на её сайте. Если очень повезёт - получится ничья.

Наконец, ультра-слабое решение не даёт нам ничего, кроме оценки начальной позиции. Это полный аналог теорем существования в математике. Для игры Гекс на большой доске доказан выигрыш первого игрока, но кроме этого не известно ничего - ни как ходить, ни каков оптимальный вариант.

Игра Го полностью решена на доске 5х5 - но лишь в слабом смысле, хотя и для всех 25 начальных ходов. Библиотека Сенсея утверждает, что при анализе одного из вариантов на этой доске-малютке ошибся сам Cho Chikun - человек-легенда, возможно лучший игрок в Го 20-го века (после Го Сейгена, конечно :))



Большой список в разной степени решённых игр можно найти в Википедии. Упоминаются свободное рэндзю, реверси 6x6 и много других игр, названия которых для меня - полнейшая загадка...

Кросс-пост в Берлогу 2.0.

Profile

winpooh: (Default)
Vladimir Medvedev

January 2014

S M T W T F S
   123 4
5678 91011
12 13141516 1718
1920 2122 23 2425
26 272829 3031 

Syndicate

RSS Atom

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 23rd, 2017 08:43 am
Powered by Dreamwidth Studios