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

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

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

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

Читать »

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

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

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

Читать »

Principal Variation Search

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

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

Читать »

Списки фигур

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

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

1)   король;

Читать »

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 с амортизацией отказов. Приведем его код:

Читать »

BitBoard

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

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

Читать »