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

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

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

Главная строка изменения — это строка перемещений, которую программа посчитала лучшей. Оценка, возвращаемая функцией AlphaBeta, является результатом этой строки. Данная строка как бы является продолжением хо­да, который программа делает. Насколько информативна эта строка? Это трудно сказать однозначно. Для напряженных строк игры бывает, что вся строка предсказана правильно. Для спокойных позиций бывает, что пра­вильно предсказан только первый ход, т. к. программа его непосредственно сделала. Извлечение главной строки представляет интерес еще и с точки зрения скорости выполнения программы. Если мы после каждой итерации имеем главную строку изменения, нам легче просчитать следующую. До по­явления хеш-таблиц это был основной (вместе с эвристикой убийцы) спо­соб перебрать более глубоко.

Читать »

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

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

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

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

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

Читать »

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

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

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

Читать »

Сокращенное вычисление

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

Я использовал этот прием сам, но не относился к нему серьезно. Каково же было мое удивление, когда я увидел, что он используется в программах, за­нимающих первые строчки в рейтинге. Существует эвристика нулевого хо­да, позволяющая, основываясь на сокращенном поиске, отсечь неперспек­тивные ветви дерева. Мы пропускаем ход противника после нашего хода, делаем еще один сокращенный поиск, и если оценка все равно не улучшает alpha, то узел можно подрезать. Ожидается, раз мы сделали два хода подряд и не улучшили alpha, то если противник сделает ход, мы его подавно не улучшим. LazyEval работает по-другому. Мы ищем не на полную глубину, а на сокращенную.

Читать »

Вращенный BitBoard

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

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

Читать »

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

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

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

Читать »

Razoring

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

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

Читать »

Сортировка простых перемещений

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

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

Читать »

MTD(f)

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

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

int alpha = …

int beta = alpha+1;

score = AlphaBeta(alpha,beta);

if (score >= beta) alpha = score;

Читать »

Перебор с нулевым окном

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

В этом разделе мы рассмотрим несколько отвлеченную тему. Она будет не­обходима для понимания особенностей работы некоторых алгоритмов. Это — перебор с нулевым окном. Используется вариант alpha-beta алгорит­ма с амортизацией отказов. Что такое нулевое окно? Мы вызывали alpha- beta поиск с окном от -infinity до infinity. Результат получается такой же точности, что и при полном переборе. Если мы присвоим alpha некоторое значение, например 0, то beta при нулевом окне будет alpha+1. Поиск при нулевом окне намного быстрее, чем при полном окне. Это связано с тем, что больше будет отсечек. Допустим, мы вызвали alpha-beta функцию поис­ка с нулевым окном и получили некоторый результат:

Читать »

Испытанный метод сортировки перемещений

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

Существует старый и простой способ сортировки, популярный на протяже­нии многих лет. Перемещения генерируются в некотором буфере. У каждо­го описателя перемещения есть поле, назовем его sortvalue. Это поле со­держит значение данного перемещения для сортировки. Применяют аналог пузырьковой сортировки: весь массив не сортируют сразу, а подкачивают вверх только одно самое лучшее перемещение. Функция подкачки получила даже традиционное название Pick.

Читать »

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

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

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

Читать »

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

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

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

Читать »

Силовое решение – пример простой программы

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

Здесь мы рассмотрим пример простой программы, осуществляющей так на­зываемое силовое решение: полный перебор на 6 полуходов, выборочные продления и форсированные варианты с взятиями до конца. Такая про­грамма, конечно, не будет играть очень сильно, но уровень первого разряда ей обеспечен. При хорошей оценочной функции и дебютных справочниках, она может показать и лучший результат. Но это в сторону. Наша задача сейчас состоит в построении простейшей программы, а не в погоне за ре­зультатами. Данная программа использует alpha-beta алгоритм перебора, NegaScout и сортировку перемещений по значению. Взятия сортируются по принципу MW/LVA (наиболее ценная жертва — наименее ценный напа­дающий). Остальные перемещения сортируются в три списка по значению. Хеш-таблица не будет задействована. Наша программа и так должна сосчи­тать на 6 полуходов, а отвлекаться на второстепенные вещи мы пока не бу­дем.

Читать »

Правила игры в шахматы

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

Если кто забыл, напомним основные правила игры. Начальная позиция изображена на рис. 2.1.

Рис. 2.11. Ходы ладьи                    Рис. 2.12. Ходы ферзя

Целесообразно упомянуть еще ряд правил:

?     Все фигуры, кроме пешек, бьют точно так же, как ходят.

Читать »