Главная » Алгоритмы

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

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

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

Читать »

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

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

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

Читать »

Вращенный BitBoard

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

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

Читать »

Рекурсия

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

Кто получил специальное образование (повезло с преподавателем) или сам занимался этим вопросом, тот, несомненно, знает преимущества рекурсив­ных алгоритмов. В обычных учебниках им отводится до смешного мало места или не отводится вообще. Популярно следующее замечание: "Любая задача, решенная с помощью рекурсии, может быть решена и обычным способом". Это так, если моделировать стек программы. Некоторые задачи, тем не менее, практически невозможно решить без рекурсии. Объем кода неимоверно возрастает, и без всякой пользы.

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

Задача о ферзях

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

Найти способ расстановки 8 ферзей на доске 8×8 так, чтобы они не били друг друга. Данная задача решается методом перебора с помощью рекурсии. Прежде чем поставить на доску очередного ферзя, нужно проверить, не бьет ли его какой другой ферзь. Если мы будем каждый раз сканировать все воз­можные перемещения всех ферзей, то это достаточно неэффективно. Мож­но ускорить проверку, если обратить внимание на один факт. Ферзь, как известно, ходит во всех направлениях, по всем диагоналям, вертикалям и горизонталям. С вертикалями и горизонталями все понятно: если был хоть один ферзь с координатой X или Y такой, как у нашего ферзя, то данное поле бьется. Как быть с диагоналями? Если диагональ восходящая (/), то сумма X и Y для всех клеток диагонали одна. Если нисходящая (\), то раз­ность X — Y для всех клеток одинакова. Мы можем иметь некоторые мно­жества, обнуленные в начале вычисления:

Читать »

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

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

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

Читать »

Локальные функции

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

Локальной или вложенной называется процедура или функция, описанная внутри другой процедуры (функции). Она может иметь свои локальные пе­ременные, а может и обращаться к переменным функции, внутри которой она описана. Вызывать ее можно только из функции, внутри которой она описана, т. е. область видимости ограничена родительской функцией.

Читать »

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

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

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

Читать »

Ханойские башни

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

Имеется 3 стержня: А, В и С. На стержень А нанизано п дисков так, что диск с меньшим диаметром всегда лежит поверх диска с большим. Говоря другими словами, на стержне А пирамида из дисков, сужающаяся вверх. Требуется переместить все диски на стержень В. Стержень С можно исполь­зовать в качестве вспомогательного. Основное условие состоит в том, что диск с большим диаметром не должен находиться поверх диска с меньшим.

Читать »

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

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

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

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

Читать »

NegaScout

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

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

Читать »

Alpha-beta

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

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

Читать »