Главная » Статьи для тега "взятия"

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

BitBoard

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

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

Читать »