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

Устаревший метод выборочного поиска

Добавлено Дата: 9 February, 2011 категория: Алгоритмы, Игры

В процессе счета возникает множество вариантов, бесполезность которых видна человеку с первого взгляда. Как научить машину отсекать бесполез­ные варианты и оставлять нужные? Это не так просто. Всегда найдется ис­ключение из правил. Тем не менее на большой глубине поиска мы сталки­ваемся с дилеммой: либо не считаем ничего, либо считаем выборочно. Применительно к шахматам можно сказать, что существует ряд ходов, когда можно определенно предположить, что поиск нужно продолжить. Это, пер­вым делом, шах. Программа будет терять в качестве, а эффект горизонта оказывать сильное влияние. Во-вторых, взятия. Размены нужно рассматри­вать до появления спокойной позиции (это в форсированных вариантах де­лается повышением alpha текущей оценкой). Взятие является ходом, за ко­торым может последовать качественное изменение позиции. Теория игр го­ворит (это ясно, в принципе, и без теории), что ходы, дающие наибольшее приращение оценки в узле, нужно рассматривать глубже. Кроме шахов и взятий, существует целый ряд так называемых угроз. Простейшая угроза — это атака. Чтобы взять фигуру, ее нужно атаковать. Угрозой может быть и ход пешки на предпоследнюю горизонталь, т. к. следующим ходом пешка может превратиться в ферзя, и счет нельзя прекращать в этой точке. Но чаще всего угроза — это опасность выигрыша фигурой материала. Вес ата­кующей фигуры должен быть меньше атакуемой. Как правило, это атака на зависающую фигуру. Все это приблизительно и формально, потому что хо­дившая фигура может не атаковать сама, а освободить линию атаки для дальнобойной фигуры, возможна и другая комбинация. Но на практике так­тические последовательности, продолжающиеся на много (иногда более де­сяти) полуходов, состоят именно из простейших угроз немедленного выиг­рыша материала и взятий (шахи относятся к угрозам).

Читать »

Сортировка взятий (MVV/LVA)

Добавлено Дата: 5 February, 2011 категория: Алгоритмы, Игры

Это очень важная тема для шахмат. Взятия — это ходы, дающие наиболее значительное приращение оценки. Для ускорения alpha-beta поиска они должны рассматриваться первыми. Во многих позициях не обязательно ге­нерировать все перемещения, достаточно рассмотреть взятия, и они уже вы­зовут отсечку за beta. В шахматах есть еще статический поиск, где взятия рассматриваются до конца. Эта тема будет рассмотрена позже, пока лишь мы должны знать, что для статического поиска порядок ходов имеет наи­важнейшее значение, иначе это вызовет взрыв дерева поиска, и программа будет считать недопустимо долго. Мы уже рассматривали alpha-beta и пом­ним, что этот алгоритм работает принципиально быстрее при наилучшем порядке ходов. Если N — число позиций, которые программа должна рас­смотреть при полном переборе (N равно W в степени D, где W — пример­ное количество ходов в одной позиции, D — глубина просчета), то alpha-

Читать »

Игра "Уголки"

Добавлено Дата: 4 February, 2011 категория: Игры, Исходники

Для иллюстрации всего вышесказанного приведем небольшой пример. На игровом поле 8×8 находятся 12 черных шашек (в левом верхнем углу) и 12 белых (в правом нижнем). Нужно занять исходные позиции противника. Черные должны стремиться занять правый нижний угол, а белые — левый верхний. Шашки ходят во всех направлениях на одну клетку (кроме диаго­налей). Шашка может прыгать через другие шашки в любых направлениях (кроме диагоналей).

Читать »

Правдоподобная генерация перемещений

Добавлено Дата: 3 February, 2011 категория: Игры, Теория

В статическом поиске результат (и лучший ход) зависит от порядка переме­щений. Как это происходит? Допустим, у нас есть два тихих перемещения. Оба дают приращение в узле +8. Оба увеличивают alpha до значения боль­ше статической оценки после хода. Если мы просчитаем первым одно пе­ремещение, второе подрежется статической оценкой. Оба хода ведут к под­резанию. Это явление получило название нестабильности поиска. Обычно нестабильность поиска считается досадной помехой, мешающей осущест­вить грубое усилие более глубоко. Нестабильность поиска возникает в тех случаях, когда отсечка или сокращение глубины основаны на пределах alpha-beta. В качестве примера посмотрим на использование нулевого хода. Мы можем применять нулевой ход без всяких условий:

Читать »

Эвристика убийцы

Добавлено Дата: 26 January, 2011 категория: Игры, Теория

Порядок ходов при alpha-beta переборе имеет принципиальное значение. Хеш-таблица позволяет запоминать проделанную работу, и если позиция встретится вновь, мы имеем, как минимум, лучший ход для этой позиции, который можем попробовать сначала. Это все справедливо для очень боль­шой хеш-таблицы и одинаковых позиций. Но часто ситуация бывает сле­дующая: позиции отличаются в несущественных моментах, а лучший ход, вызывающий отсечку, совпадает. Возникла идея: попробовать сначала луч­ший ход для этого уровня, в надежде, что он будет лучшим и в данной по­зиции. Это часто срабатывает. Если у двух позиций один общий предок, то часто лучший ход в них один и тот же. Данная эвристика получила назва­ние эвристики убийцы (Killer heuristic). Она работает неточно, но может давать хорошую прибавку в скорости. Все дело в приоритете конкретной эвристики для оптимизации перемещений. Я, например, опытным путем пришел к следующему порядку:

Читать »

Грубое усилие и избирательность

Добавлено Дата: 22 January, 2011 категория: Алгоритмы, Игры

Когда в 70-е годы прошлого века состоялся второй матч между русской "Каиссой" и американской Chess, то создатели американской программы сделали эпохальное заявление: "Мы собираемся заниматься выборочным

поиском, потому что полный перебор — это тупик". Такое или подобное заявление делали многие шахматные программисты на определенном этапе своей деятельности. И только очень немногие сделали приличную програм­му выборочного поиска. Среди них Ричард Лэнг с его программой Genius. В чем же трудность? Почему так мало удачных программ выборочного по­иска? На этот вопрос можно ответить, но меня смущают некоторые вещи. Я недавно читал книгу по ЗЭ-движкам и понял содержание только первых нескольких глав, да и то потому, что сам в свое время построил простей­ший ЗЭ-движок. Остальная часть книги совершенно непонятна. Темы не раскрыты, а только затронуты, тон менторский, автор — явный зазнайка. В примерах программ к книге у него вращался (очень медленно) трехмер­ный зеленый бублик, и это приводилось в качестве достижения трехмерного моделирования. Если бы все читали только эту книгу, то не было бы ни Doom, ни Ducke, ни других хороших игрушек. Для кого была написана та книга? Видимо, для тех, кто и так все знает, а только хочет нечто освежить в памяти. Я все боюсь уподобиться этому автору. Для меня в alpha-beta ал­горитме и его свойствах нет ничего сложного, потому что я долго занимался этим вопросом. Как дела обстоят у читателя? Да простят меня профессио­налы, я буду много времени уделять тривиальным вещам и много раз по­вторяться. Я надеюсь, что при каждом повторе высветится та или иная грань алгоритма.

Читать »

Пример игры "Крестики-нолики"

Добавлено Дата: 21 January, 2011 категория: Игры, Исходники

Напомним правила: игра идет на квадратном поле 3×3 клетки. Игроки по очереди ставят в клетках крестики (один) и нолики (другой). Выигрывает тот, кто первым замкнул линию (вертикальную, горизонтальную, диаго­нальную — неважно). Программа написана на языке Turbo Pascal 7 (см. листинг П1.1). Вывод осуществляется в текстовом режиме.

Читать »

Теория выборочного поиска

Добавлено Дата: 19 January, 2011 категория: Игры, Теория

Данная тема является довольно скользкой, и я ни в коем случае не претен­дую на роль классика в этом жанре. Понятия нечетки, и трудно провести грань между белым и черным. Это напоминает интегральное исчисление: сумма бесконечно малых величин дает что-то осязаемое. Так и с выбороч­ным поиском. Рассуждая логически, нельзя резать ветви дерева перебора без их предварительного исследования. Данная задача интригует програм­мистов и математиков уже давно, и многие утверждают, что только полный перебор дает правильный результат. Применительно к шахматам, наилуч­ший порядок — вещь труднодостижимая. Но это в сторону.

Читать »

Статические понятия

Добавлено Дата: 17 January, 2011 категория: Игры, Теория

В каждой позиции существует две статические оценки: до хода (l score) и после хода (r_score). Оценка до хода является общей для всей позиции, оценка после хода изменяется после каждого перемещения. Рассмотрим эти величины подробнее, r score, как правило, больше l_score. Это относится к взятиям, как к перемещениям, дающим наибольший прирост оценки, и к другим ходам, оценка которых больше 0. Существуют еще отрицательные ходы.

Читать »

Безопасность короля

Добавлено Дата: 16 January, 2011 категория: Игры, Теория

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

Читать »

NegaScout

Добавлено Дата: 14 January, 2011 категория: Алгоритмы, Игры

— самый популярный на сегодня алгоритм грубого усилия. Он чрезвычайно прост и дает некоторое (до 50%) ускорение, не внося ника­кой дополнительной погрешности в вычисление. Он очень хорошо сочета­ется с современными атрибутами шахматных программ — хеш-таблицами. не предусматривает извлечения строки главного изменения или других хитростей. Основная его идея следующая: прежде чем исследовать любой узел, мы его пытаемся сначала отсечь за перебором с нулевым окном (от alpha до alpha+1). Если результат счета улучшает alpha, тогда перебираем снова. Учитывается также один тонкий момент. Если мы перебрали с нуле­вым окном и получили результат больше, чем alpha, то это — наш мини­мум, и мы можем смело повторить перебор с пределами не от alpha до beta, а от полученной оценки до beta. Само собой, если этот наш минимум уже сравнялся с beta, то уточнять его не нужно. Можно сразу вернуть beta. Это очень похоже на Principal Variation, за исключением повышения alpha при повторном переборе. Первый ход в каждом узле рассматривается с полным окном. Какой это ход? Это зависит от генератора перемещений. Это может быть ход из хеш-таблицы, хорошее взятие или любой другой ход. Алгорит­мом это не определяется. Просто этот ход первый.

Читать »

Futility pruning

Добавлено Дата: 13 January, 2011 категория: Игры, Теория

Автор идеи — Эрнст Хайнц, применивший ее в своей программе DarkThough. Сама идея очень проста. На последних двух полуходах перебора оценка не­точна, и можно, основываясь на текущей статической оценке позиции и характеристике узла, подрезать целую ветвь поиска. Нельзя с определен­ностью сказать, что вносит погрешность, т. к. в двух послед­них узлах программа и так постоянно ошибается. Можно сказать, что ошибки будут, но несколько другого характера.

Читать »

Alpha-beta

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

Сейчас мы рассмотрим основной алгоритм оптимизации перебора. Он на­зывается alpha-beta отсечениями, или просто alpha-beta. Суть его в том, что для получения оценки такой же точности, как и при полном переборе, со­вершенно не обязательно просматривать все варианты. Для определения отсекаемых вариантов не требуется знать особенностей данной игры.

Читать »

Использование строки главного изменения

Добавлено Дата: 11 January, 2011 категория: Алгоритмы, Игры

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

Читать »

Более сложные приемы ZObrist-ключи

Добавлено Дата: 9 January, 2011 категория: Игры, Теория

 

Для написания шахматной программы нужно уметь сравнить две позиции, одинаковы ли они? Такая задача возникает довольно часто, и ее выполнять нужно с максимальной скоростью. Например, при построении хеш-таблицы нужно иметь ключ, однозначно идентифицирующий позицию. При поиске конкретной позиции сначала находится начало подсписка, соответствующе­го данному ключу. Хотя ключ и не совсем точен, поиск значительно сокра­щается.

Читать »