Главная » Игры

BitBoard

Добавлено Дата: 12 December, 2010 категория: Алгоритмы, Игры

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

Читать »

Повторы позиций

Добавлено Дата: 11 December, 2010 категория: Игры, Теория

Определение повторов позиций — не такая тривиальная тема. Она затрону­та многими корифеями шахматного программирования. Я не буду пытаться объять необъятное, а покажу, как простейшим способом научить программу распознавать повторы позиций.

Допустим, наше перемещение представлено в виде

Читать »

История развития шахматных программ

Добавлено Дата: 8 December, 2010 категория: Игры, История

Когда же в первый раз машина заиграла в шахматы? На этот вопрос трудно ответить, наверное, в 1769 году. Венгерский инженер барон Вольфганг фон Компелен создал машину, способную играть в шахматы (рис. 1.1). Она была предназначена для развлечения королевы Марии-Терезии. Машина, дейст­вительно, неплохо играла — внутри ее сидел сильный шахматист, который и делал ходы. История примечательная и, в некоторой степени, актуальна и в наши дни. Что программист вложит в машину, то она и играет. Гарри Кас­паров, например, понимает этот тезис буквально. Он утверждает, что в его втором, решающем матче с DeepBlue (первый он выиграл), начиная со вто­рой партии, в игру машины вмешивался человек и компенсировал неспо­собность машины понимать позиционную игру. Оставим этот вопрос на совести корпорации IBM и Гарри Каспарова. Я лично нисколько не сомне­ваюсь, что Каспаров может выиграть еще один матч с DeepBlue (если этот матч возможен), если, конечно, ему повезет.

Читать »

Выборочные продления Краткая характеристика расширений

Добавлено Дата: 8 December, 2010 категория: Игры, Теория

В полном широтном поиске, который мы рассматривали, глубина поиска задавалась при первом вызове рекурсивной функции и уменьшалась в каж­дом узле на 1. Таким образом, мы осуществляли полный перебор на неко­торую фиксированную глубину. Мы рассмотрели также устройство форси­рованного варианта, который вызывался при Depth = 0 и сглаживал эффект горизонта. Форсированный вариант просчитывал дальше наиболее сильные перемещения и давал приблизительную оценку позиции горизонта. Допус­тим, что при минимальном размере дерева перебора, т. е. при оптимальном порядке перемещений, для углубления счета на глубину N+1 нам необхо­димо рассмотреть в 20 раз больше позиций, чем при счете на глубину N. Это довольно приблизительно, но нам для рассуждений нужно отталкивать­ся от каких-то величин. Существует мнение, что увеличение глубины счета на один полуход повышает силу игры программы на разряд. Может, не сто­ит ломать голову над разными ухищрениями, а просто подождать, пока процессоры станут мощнее в 20 раз. Мы сможем считать на 9 полуходов, потом еще в 20 раз — мы сосчитаем на 10 полуходов. Бывают тактические последовательности, которые программа должна просчитывать значительно глубже. Например, если на доске существует форсированная угроза королю, то может потребоваться считать на 14 полуходов. Гроссмейстеры просчиты­вают некоторые варианты на 20 и более полуходов. Вряд ли мощность про­цессоров когда-либо возрастет до такого уровня, да и программы желатель­но писать сейчас, а не через 10 лет. Человек, когда просчитывает некоторые варианты, руководствуется множеством критериев, зависящих от его опыта. Он может просчитать ситуацию очень глубоко, проанализировав при этом минимальное количество позиций. Несмотря на то, что моделировать мыш­ление шахматиста мы не можем, существуют некоторые строки игры, про­счет которых можно продолжить по совершенно формальным признакам. Возникла простая идея — не сокращать глубину просмотра при некоторых ходах. Мы можем считать на 6 полуходов, но некоторые варианты будут рассмотрены значительно глубже. При каких же ходах не сокращается глу­бина счета? Если мы говорим о шахматах, то это, прежде всего, шах. При шахе игра как бы замирает и требует от противника немедленного ответа. Замедление счета при этом тоже минимальное, т. к. число легальных ходов под шахом ограничено, и узел будет обсчитан очень быстро. Продление все­го лишь шахов резко увеличивает силу игры программы. Считая на 6 полу­ходов, она способна обнаружить глубокие форсированные маты и другие комбинации, основанные на угрозе королю и приводящие к выигрышу ма­териала. Пример функции счета, продлевающей шахи:

Читать »

Дробный Depth

Добавлено Дата: 6 December, 2010 категория: Игры, Теория

Нужно просчитывать глубже многие ходы, но это может привести к взрыву дерева поиска, и только шахи являются стопроцентно корректными расши­рениями на любой глубине. Возникла следующая идея: делать Depth дроб­ным. В каждом узле Depth уменьшается не на 1, а на 4. Начальное значение Depth тоже равно глубине просчета, умноженной на 4. Таким образом, в за­висимости от нашего представления о правдоподобности данного хода, мы можем при одних ходах увеличивать Depth на 4 (при шахах), а при других — на меньшую величину. Приведем примерный список расширений:

Читать »