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

Атака дальнобойных фигур

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

Давней мечтой шахматных программистов является генерация взятий даль­нобойных фигур, не строя линии. Генерация взятий является самым кри­тичным по времени выполнения фрагментом программы. Дело в том, что больщинство позиций можно отсечь только взятиями, и даже не обязатель­но иметь весь список перемещений. Кроме того, взятия в форсированном поиске рассматриваются до конца. Генерация перемещений на глубине 20 намного больше влияет на скорость выполнения программы, чем на глуби­не 5. Для ускорения получения взятий существует много методик. Мы рас­смотрим только один старый и очень простой прием. Идея следующая: ос­новная масса перемещений после хода некоторой стороны не изменяется, за исключением некоторых ходов, связанных с последней ходившей фигу­рой. Например, если пешка пересекла линию ферзя, то ферзь уже не может бить по этой линии. Остальная масса перемещений осталась без изменений. Изменились только ходы пешки и ферзя, которому она перекрыла линию. Мы сейчас, для простоты, не будем рассматривать, как можно корректиро­вать перемещения всех фигур при ходе, а рассмотрим только дальнобойные фигуры. Введем некоторый массив, где будут представлены все фигуры на доске, независимо от цвета и веса. Их можно представить как ферзи без учета цвета. Даже если это пешка, мы ее будем рассматривать как ферзя, потому что она так же может перекрыть линию дальнобойной фигуре. Ферзь, как известно, объединяет в себе ходы всех дальнобойных фигур. Каждая клетка нашего нововведенного массива будет иметь 8 ссылок на ближайшие фигуры по всем лучам. Наш массив будет иметь размерность не 8 х 8, а 10 х 10. По краям находятся лишние описатели. Даже если по ли­нии фигуры нет, ссылка все равно будет указывать на некоторый элемент, а именно на ближайший за пределами доски. Если нам нужно убрать некото­рую фигуру, мы просто должны восстановить все перекрестные ссылки. Фигура справа, например, будет ссылаться на фигуру слева. Чтобы поста­вить фигуру в новое место, мы должны просканировать 8 лучей во всех на­правлениях до первой фигуры или до края доски и навести перекрестные ссылки. В действительности, нам нужно сканировать не 8 лучей, а 4. Когда мы нашли фигуру справа, она уже ссылается на фигуру слева, и ее искать и строить линию не нужно. Таким образом, при каждом ходе мы строим до­полнительно только 4 луча, но можем выбирать взятия дальнобойных фи­гур, не строя линии. Если это ладья, то нужно просто проверить ссылки по вертикали и горизонтали, не указывают ли они на фигуры противника. Об­ратите внимание, что если одна фигура бьет другую, то все остается без из­менений, и никаких лучей строить не нужно. Когда на глубине идет поиск одних взятий, это позволяет очень быстро вычислять результат размена дальнобойных фигур. При некоторой изощренной технике можно брать взятия с фронта. Мы просто просматриваем список фигур противника, на­чиная с самых ценных, и сразу видно, какие фигуры их бьют. Далее приве­ден пример кода, дающего возможность брать взятия дальнобойных фигур, не строя линий:

Читать »

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

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

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

Читать »

Статический поиск

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

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

Читать »

Сокращения глубины поиска

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

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

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

Читать »

Поиск стремления

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

(Aspiration search) — еще одна идея ускорения alpha-beta перебора. Из корня дерева перебора функция AlphaBeta вызывается с преде­лами alpha = -infinity, beta = infinity, где infinity — максимально воз­можный результат.

Функция AlphaBeta возвращает оценку лучшего (по ее мнению) хода. Ско­рость счета сильно зависит от alpha-beta пределов. Возникла простая идея: зачем уточнять alpha-beta пределы, когда результат счета в большинстве случаев примерно известен. В качестве параметров функции ALphaBeta рас­сматривается ожидаемый результат и окно стремления. Выглядит, это при­мерно так:

Читать »

Principal Variation Search

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

Поиск с основным вариантом имеет название (PVS). Мы делаем предположение, что нам известны лучшие ходы в неко­торых узлах. Тогда, если мы нашли такой ход, мы его рассматриваем с пол­ным alpha-beta окном, как при стандартном alpha-beta алгоритме. Ожидает­ся, что ход потенциально хороший и может повысить значение alpha в узле.

Читать »

Форсированные варианты

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

По окончании полного перебора поиск может быть продолжен в форсиро­ванном варианте, который, в сущности, является конечной стадией выбо­рочного поиска. Основное его назначение — дать примерную оценку пози­ции горизонта. Какие ходы являются форсированными? В самом простей­шем случае это взятия. Взятия в шахматах дают самый большой прирост оценки (существенно больше, чем стратегическая оценка), и поэтому рас­смотрение взятий в глубине поиска сглаживает до некоторой степени эф­фект горизонта. Взятия являются также ходами, требующими немедленной реакции. В шахматах бывают очень длинные размены, которые программа должна рассматривать до конца. Если программа считает на 8 полуходов и рассматривает все размены в конце, уровень ее игры будет значительно вы­ше. Кроме взятий, и другие ходы могут являться форсированными. Напри­мер, шахи. Шах является, в сущности, видом атаки. Атака может быть на пешку, на ферзя, а в случае шаха — на короля. Шах является особым ходом в шахматах. Игра при шахе как бы замирает, и сама ситуация требует более глубокого просчета. Шахи в очень сильной степени влияют на эффект гори­зонта. Если форсированные варианты не рассматривают шахи, их оценка является уж очень приблизительной. В некоторых случаях и этого бывает достаточно. Если программа считает глубоко и имеет развитую систему вы­борочных продлений полного перебора, то на некоторой глубине ей может оказаться достаточно самой приблизительной оценки горизонта. Существу­ют два основных подхода к этой проблеме:

Читать »

Эффект горизонта

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

Шахматы — сложная игра. Перебор на некоторую фиксированную глубину для спокойных, тихих перемещений, может быть, и достаточен. В напря­женных же строках игры программа может получить неверный результат и повести себя непредсказуемо, например, начать выбрасывать фигуры. Это явление получило название эффекта горизонта. Простейшее его прояв­ление — программа не может до конца рассмотреть длинный размен, ей кажется, что она выигрывает, а на самом деле она теряет. Существует еще множество проявлений эффекта горизонта. Например, если программа пе­ребирает на 8 полуходов, то в некоторой строке игры вполне может оказать­ся несколько взятий и шахов, и программа в конце перебора получит неиз­вестно что. Вариантов тактики на доске может быть сколько угодно, и даже в серьезной, профессиональной программе может обнаружиться эффект го­ризонта. Например, наш ферзь в ловушке. Человек посмотрит на такую по­зицию, и ему ясно практически сразу, что ферзь пропал. Программа же смотрит не так. Она находит длинную тактическую строку, в которой, на­пример, есть размен фигур, шах, несколько угроз или просто атак, и она уже не видит потерю ферзя, данный ход вытеснен за горизонт видимости программы. Существует великое множество всяких тактических последова­тельностей, которые приводят к эффекту горизонта. Как же бороться с этим эффектом? Лучше всего перебрать ходов на 16 или на 20, но это невозмож­но, и приходится прибегать ко всяческим хитростям. В конце основного поиска (полного перебора) вставляют упрощенный поиск, который рас­сматривает только форсированные ходы. В самом простейшем случае это взятия. Считается правилом хорошего тона рассматривать взятия до конца. Таким образом, программа как бы считает до конца, но не все. В более сложных вариантах форсированного поиска до некоторой глубины могут просматриваться шахи и даже некоторые другие ходы (например, атаки). Более подробно об организации форсированных вариантов будет сказано позже. Далее, в основном дереве перебора глубину в напряженных строках можно сделать более гибкой, т. е. чтобы программа просматривала такие строки глубже, чем остальные. Это называется выборочными продлениями. Типичные случаи продлений — при шахе, при размене, при авансе пешек (пешка пошла на предпоследнюю горизонталь). Продления могут быть, если оценка данного хода существенно отличается от остальных (это, как прави­ло, взятия). Если программа рассматривает взятия до конца и имеет неко­торые выборочные продления, то эффект горизонта в значительной степени уже сглажен. Но все не так просто. Тактических последовательностей может быть много. Если мы начнем продлевать все такие варианты, это приведет к взрыву дерева поиска и программной аварии. Я уже упомянул о варианте, где ферзь попадал в ловушку. Полный переборщик, чтобы увидеть это, дол­жен считать на 12 полуходов, что нереально. Если расширять строки, то нужно расширять и атаки, что приведет к резкому замедлению поиска, и программе для нормальной игры не будет хватать простых перемещений в полном дереве перебора. Это напоминает ситуацию "нос вытащишь — хвост увязнет, хвост вытащишь — нос увяз". Программа не видит других важных стрфк, которые не попадают под упрощенные критерии сильных перемещений.

Читать »

Детекторы шахов

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

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

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

Читать »

Списки фигур

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

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

1)   король;

Читать »

Хеш-таблицы одним из самых мощных способов повышения про­изводительности компьютера

Добавлено Дата: 19 December, 2010 категория: Игры, Структуры данных, Теория

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

Читать »

Пример генерации перемещений

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

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

Читать »

MiniMax и NegaMax

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

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

Читать »

Alpha-beta с амортизацией отказов

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

Мы рассмотрели alpha-beta алгоритм. Он всегда возвращает значение из alpha-beta диапазона. Если мы, например, вызвали функцию поиска из кор­ня дерева с параметрами alpha = — 1, beta = 1, то, каким бы ни был истин­ный результат, наша функция вернет значение из заданного промежутка alpha и beta. Можно модернизировать функцию таким образом, чтобы воз­вращаемое значение не ограничивалось этим промежутком. Представим, что мы в некоторой точке дерева. Функция перебрала все перемещения, но так и не смогла улучшить alpha. В таком случае можно вернуть не alpha, а мак­симальное полученное значение для этого узла. Это никоим образом не скажется на конечном результате. Точность просчета будет такой же. Alpha- beta перебор с возвратом максимального полученного результата каждой функции называется alpha-beta с амортизацией отказов. Приведем его код:

Читать »

Единственный ответ

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

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

Читать »