Главная » Теория

Замечания по технике программирования

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

Профессионал может пропустить эту статью. В ней содержатся некоторые тривиальные веши, которые, тем не менее, полезно знать.

Стековые переменные

Переменные могут быть стековыми или глобальными. Когда начинается выполнение функции, в стек программы заносится адрес возврата, происхо­дит переход на начало машинных инструкций данной функции. Вот типич­ная сигнатура функции:

Читать »

Эвристика истории

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

(History heuristic) является статистическим методом упо­рядочивания перемещений. Позиция имеет размер 8×8 или 0..63. Можно сделать некоторую таблицу [64] [64], обнуленную в начале вычисления. Если данное перемещение вызывает улучшение alpha (или отсечку за beta), то в клетке [ni] [n2] можно увеличить значение на 1, где ni — позиция, от­куда пошла фигура, а n2 — куда пошла.

Читать »

Простая оценочная функция

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

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

Читать »

Razoring

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

Идея та же, что и Futility pruning. Только там подрезались два граничных узла, а теперь мы возьмемся за два следующих. Поле роста (margin) теперь больше и равно максимальной величине материального приращения. Обыч­но вполне достаточно величины одной королевы. Условия подрезки дерева:

Читать »

MTD(f)

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

Много было попыток сделать невозможное — решить проблему перебора. Одна из таких попыток — – Замечено, что перебор с нулевым окном выполняется быстрее:

int alpha = …

int beta = alpha+1;

score = AlphaBeta(alpha,beta);

if (score >= beta) alpha = score;

Читать »

Просмотр шахов в форсированном поиске

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

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

Читать »

Недействительное перемещение

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

Нулевой ход, или недействительное перемещение, используется в большин­стве современных программ. История его открытия довольно туманна. Та­кое впечатление, что он известен был всегда, но об этом открыто не гово­рили. Существовала тенденция сокрытия информации о шахматных про­граммах. Каждому казалось, что он открыл нечто уникальное, до чего никто не додумался, но потом постепенно становилось известно, что все исполь­зуют, в принципе, одни и те же методы. Так было и с нулевым ходом. Офи­циально его еще не существовало. Франц Морш услышал о нем в 1986 году в Германии на мировом первенстве среди шахматных программ, где Дон Бил участвовал с шахматной программой, использующей технику NullMove (Нулевой ход). Франц Морш использовал его в своей программе Fritz, ко­торая и по сей день входит в тройку сильнейших программ. Позже, когда о нем написали Donninger, Beal, Goetsch & Campbel, нулевой ход стал все­общим достоянием.

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

Futility pruning

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

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

Читать »

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

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

 

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

Читать »

Проще некуда (оценочная функция)

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

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

Читать »