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

Итак, представим себе, что нам надоело писать программу, играющую в шахматы.
Сколько можно вылизывать давно избитый альфа-бета алгоритм,
добавляя в него по мелочи новые эвристики поиска и оценки!
Работа мелкая, хуже вышивания…

Хочется решить проблему сразу и навсегда!
Как говорится, одним махом и без больших усилий. Как это сделать?

Вот несколько возможностей (про бред и ахинею не забываем!):

1. Самый простой путь – вообще ничего не делать!
Просто взять самое мощное железо, с немереным количеством ядер и памятью,
запустить самую сильную на сегодня Рыбку, выставить перед ней начальную позицию
и запустить бесконечный анализ.
Приходим через месяц (или через год) и смотрим.
А вдруг там уже выведен вариант с оценкой +2 пешки в пользу белых?
Вот и все – задача решена!

2. Если первый вариант не прокатит (а он почти наверняка не прокатит!),
то придется немного помучиться, используя в качестве помощника все ту же
сильнейшую версию Рыбки. Надо просто заставить ее поиграть саму с собой,
причем заставить ее сыграть все возможные партии.
А сколько их, этих партий всего? Где-то писали (не помню, где),
что всего существует примерно 10^100 партий. Ох, как много!
Не потянем – никакого времени не хватит!
Хотя постойте, а надо ли играть все партии?
У нас же есть принцип альфа-бета отсечений – если какой-то вариант привел
к выигрышу белых, то вдоль этого варианта не нужно искать усиление за белых –
нужно смотреть только ответвления за черных.
Это позволяет сократить число вариантов до корня квадратного из их общего числа.
Итак, остается всего 10^50 вариантов. Уже немного легче, но тоже многовато.
Где бы еще сэкономить?
Ах, да! У нас получилось так много потому, что в каждой позиции дерева
мы предполагали рассматривать все возможные ходы.
А зачем, если большинство этих ходов – полный бред и ахинея (Сергей, ты еще не икаешь?).
В огромном числе позиций вообще лучший ход – единственный,
все остальные с треском проигрывают. Да и Рыбка у нас под рукой на что?
Пусть она предложит два-три возможных хода, остальные мы отбросим.
Можно кроме Рыбки подключить к этому делу еще каких-нибудь Фритца, Хиаркса, Шреддера и Заппу.
В-общем, пусть у нас в среднем остается в каждой позиции 4-5 ходов.
Это намного лучше, чем в среднем 30, как это принято считать.
Сколько тогда у нас останется возможных вариантов в дереве? А фиг его знает!
Считать неохота, но интуитивно кажется, что значительно меньше, чем 10^50.
Хотя опять же интуиция подсказывает, что о-о-очень много.
Последнее, что приходит на ум – выставить приоритет разыгрывания партий.
В некоторых дебютных книгах есть такой параметр – число игр по каждому варианту.
Иногда это количество дальнейших разветвлений в книге, а иногда –
число партий из какой-то Мегабазы. Где меньше это число, там меньше разветвлений.
Ага, это то, что нам нужно! Начинаем играть варианты с наименьшего числа игр.
Все, надоело думать, надо трясти это дерево!
Пишем некую оболочку, которая умеет загружать разных Рыбок для анализа,
кладем туда дебютную книгу (это чтобы выбирать менее ветвистые варианты),
закладываем туда сценарий разыгрывания партий и запускаем.
Опять уходим на месяц (или на год). Интересно, что мы обнаружим, когда вернемся?

3. А что такое вообще дерево вариантов?
Попробуем посмотреть на него не сверху и не сбоку, а снизу.
Снизу – это там, где висят концы веточек.
Мы увидим целую россыпь кончиков ветвей, и на каждом кончике висит значение оценки.
Каждый такой кончик можно представить точкой в некотором N-мерном пространстве,
где N – число ходов к кончику. Наша задача в том, чтобы из этого множества точек
найти такую, в которой значение оценки принимает наибольшее значение,
при условии, что соперник будет нам мешать и искать наименьшее значение (минимакс, однако).
Сегодня мы занимаемся тупой работой – перебираем все точки.
А если искать оптимум каким-то более эффективным способом, как это делают
хорошие алгоритмы поиска экстремума функции, двигаясь в наиболее перспективном направлении?
Конечно, придется попрыгать по оврагам, т.е. локальным экстремумам.
Придется помучиться, чтобы сгладить эти неровные дороги,
или как сказал бы математик – сделать функцию гладкой и дифференцируемой.
Здесь могут пригодиться какие-то сортировки ходов.

4. А что такое вообще шахматы?
А это – доска с фигурками, и эти фигурки умеют передвигаться по определенным правилам.
Иными словами – перед нами типичная машина, состоящая из определенных элементов,
и эти элементы работают, подчиняясь каким-то установленным нами законам.
А работу машины можно описать системой уравнений, в которой нужно задать
принцип действия каждого элемента и взаимодействие этих элементов между собой.
А решение этой системы дает нам возможность предсказать поведение этой машины
в любой момент времени.
Как написать систему уравнений для, скажем, двигателя внутреннего сгорания –
еще можно сообразить. Изучаем физику, теормех, сопромат – и в конце концов напишем.
А для шахмат? Думай, башка, думай!...
Не-а, ничего не придумывается. Нет еще такого математического аппарата, хоть тресни.
Книги по дискретной математике не помогают – какие-то графы,
комбинаторика с перебором, линейное программирование с симплексами –
нет, это не для нас! Мы же не хотим, чтобы было сложно.
Надо что-то другое и попроще.

Но об этом потом. Как говорится, продолжение следует…

Hosted by uCoz