В прошлой статье («Мир ПК», №12/07, с. 52) мы разобрались в том, какие преимущества перед человеком имеет электронная машина. Прежде всего это отличная «память», которая никогда, за редким исключением, не подведет, и замечательные счетные способности, даже и не снившиеся людям. Пользуясь этим, компьютер способен победить практически в любой игре, перебрав все возможные варианты ходов соперников и найдя в каждой позиции самый лучший. Но не все так просто, иначе почему же «ничейность» такой сравнительно несложной игры, как шашки, была доказана лишь совсем недавно?

Немного математики

Тот способ, которым находят лучший ход, основан на переборе всех вариантов и называется переборным. Однако известно, что самая большая проблема переборных решений (и это касается не только логических игр, но и многих других задач) заключается в числах, но не в тех, которые встречаются нам каждый день, а в невероятно огромных числах!

Многие думают, что нет предела вычислительной способности компьютера, нужно лишь добавить немного оперативной памяти «притормаживающему» Photoshop и поставить четырехъядерный процессор, если приходится часто перекодировать фильмы. Но это не совсем так.

Многие задачи, начиная с выяснения результата идеальной партии в шахматы и заканчивая расшифровкой генетических кодов и моделированием Вселенной, упираются в «тугодумие» (применительно к этим задачам, конечно) современных компьютеров.

В борьбе за вычислительные способности в ход идут все средства: параллельное программирование, сверхмощные многопроцессорные суперкомпьютеры, распределенные вычислительные сети, состоящие из огромного количества вычислительных узлов… Но все же решение многих задач пока не под силу электронным машинам.

Сколько звезд на небе?

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

Да, именно так. Например, количество позиций, возникающих в тех же шашках, оценивается астрономическим числом 5×1020, или 500 квинтиллионов позиций. Это не шутки!

Самому мощному компьютеру в мире понадобится не меньше месяца непрерывной работы, чтобы полностью просчитать такую сравнительно простую игру, как шашки, путем перебора! Что же говорить о шахматах, го или невинной забаве героев произведений братьев Стругацких  — трехмерных шахматах?

Как объять необъятное и сосчитать бесконечное

Впрочем, на этом проблемы с большими числами не заканчиваются, ведь нужно еще и хранить все те позиции, которые принимают участие в переборе. А сколько на это потребуется памяти? Возьмем количество позиций в шашках (каждую позицию представим шестью байтами, меньше вряд ли удастся), умножим на восемь и получим количество байт, необходимых для кодирования всех возможных шашечных позиций. Сколько получилось? Немало, около 4 зеттабайт или, если перейти к более привычным цифрам, около 4 миллиардов терабайтных жестких дисков!

А для шахмат? Даже и считать не стоит — до таких запоминающих уст-ройств технологии дорастут еще не скоро…

Загадочная эвристика и обучение машин

Вот, пожалуй, и все. Вывод наш неутешителен: просто так, с наскока, непобедимую программу, способную выиграть даже у чемпиона мира, не создать… Но ведь нельзя же совсем отступиться от этой затеи? Пусть наша программа и не будет безупречна, главное, чтобы она очень хорошо играла на обычном ПК без зеттабайтных жестких дисков и тысячеядерных процессоров!

Каким же образом это сделать? В прошлый раз, придумывая алгоритм для игровой программы-всезнайки, мы воспользовались двумя обычными человеческими слабостями. Первая из них — неидеальная память, которая может «сбоить» при больших нагрузках даже у хорошо тренированного человека. Вторая — очень и очень ограниченные (по сравнению с компьютером, конечно) возможности по перебору вариантов: просчитать сложнейшую миттельшпильную шахматную позицию даже на два-три хода не каждому по силам. Но раз игра на человеческих слабостях не принесла желаемого успеха, нужно попробовать уравнять сильные стороны: научить программу использовать те же методы, которые приводят к успеху людей. Если при этом не забывать о «врожденных» достоинствах компьютера, то наша программа, безусловно, станет сильнее многих, а то и всех интеллектуалов логических игр.

Итак, какие способности homo sapiens, хотя бы немного знакомого, например, с шахматами или шашками, могут заинтересовать нас?

Кратко перечислим эти сильные стороны интеллекта, а в следующей статье подробно разберем, каким образом их можно реализовать в виде программы.

Несомненно, одно из важнейших качеств, присущих человеку, — способность к обучению. Каким было бы человечество (да и было бы оно вообще?), если бы не тяга к знаниям, способность воспроизведения знаний в умениях и закрепление умений навыками? Яркие личности с сильными способностями к обучению тащили (и до сих пор тащат) все человечество по ступеням эволюции, а сами поднимаются по ступеням карьерных лестниц.

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

Шахматы не были бы шахматами, шашки — шашками, а другие игры стали бы значительно более скучным занятием, если бы в каждой возникающей позиции человек перебирал все возможные ходы… Но любой игрок — и любитель, и профессионал — рассматривает только несколько (обычно два-три, максимум — десять) из возможных ходов, отсекая бесполезные (а зачастую даже вредные), означающие топтание на месте, или ход вдалеке от основных боевых действий на игровом поле. Конечно, в логических играх нет правил без исключений, иногда полезно сделать и «тихий» ход, но вряд ли вам придет в голову, играя в крестики-нолики на «бесконечном» поле, поставить свой знак за две сотни клеток от ближайшего «крестика» или «нолика» противника!

Не всегда есть необходимость в подробном пересчете вариантов и продумывании ходов. Иногда даже мимолетного взгляда, брошенного на позицию, достаточно, чтобы предсказать исход партии. Неважно, сколько ходов еще нужно сделать, чтобы поставить мат сопернику,  — два или двадцать два, если шансов у вашего противника нет даже на ничью… Оценка позиции, основанная на самых очевидных факторах (количество фигур или шашек на доске: у кого больше, тот и выигрывает; наличие дамок или матовых угроз; благоприятное расположение «камней»), может дать достаточно точный ответ о том, хорош или нет рассматриваемый вариант. Обучение, выбор хорошего «хода-кандидата» и оценка позиции лежат в основе победы.

Вот это мы и обсудим в следующей статье.