Разум, машины и математика

ГО — ОДНА ИЗ ВЕЛИЧАЙШИХ НЕРЕШЕННЫХ ЗАДАЧ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

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

Сегодня еще ни одна компьютерная программа не смогла без форы обыграть профессионального игрока в го.

Правила этой стратегической китайской игры крайне просты, однако по ходу партий постоянно возникают невероятно сложные сценарии. В го играют на доске, разделенной линиями на квадраты размером 19 х 19. Два игрока по очереди ставят фишки белого и черного цвета на свободные пересечения линий доски. Если одна или несколько фишек оказываются полностью окруженными фишками другого цвета, то «захваченные» фишки снимаются с доски. Игрок может в любой момент передать право хода противнику, но если оба они передают право хода два раза подряд, партия заканчивается, и победителем признается тот, кто на момент прекращения партии имел более выгодную позицию.

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

Доска и фишки для игры в го. Последние традиционно называются камнями.

Положение фишек на доске в одной из партий финала чемпионата мира, прошедшего в 2002 году, где встретились Чхве Мёнхун (белые) и Ли Седоль.

* * *

Почему мы называем этот раздел искусственного интеллекта поиском, если речь идет о численной оптимизации? К поиску относятся задачи и другого типа, к примеру, так называемые комбинаторные задачи. Их решения образованы различными элементами, которые могут сочетаться между собой и порождать комбинаторное пространство. Решение такой задачи определяется оптимальным множеством элементов. Хороший пример комбинаторной задачи — шахматная партия. Оптимальным решением этой задачи будет последовательность ходов, ведущих к выигрышу.