Главная » Теория

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

Добавлено Дата: 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 рас­сматривается ожидаемый результат и окно стремления. Выглядит, это при­мерно так:

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

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

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

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

Читать »

Повторы позиций

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

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

Допустим, наше перемещение представлено в виде

Читать »

Выборочные продления Краткая характеристика расширений

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

В полном широтном поиске, который мы рассматривали, глубина поиска задавалась при первом вызове рекурсивной функции и уменьшалась в каж­дом узле на 1. Таким образом, мы осуществляли полный перебор на неко­торую фиксированную глубину. Мы рассмотрели также устройство форси­рованного варианта, который вызывался при Depth = 0 и сглаживал эффект горизонта. Форсированный вариант просчитывал дальше наиболее сильные перемещения и давал приблизительную оценку позиции горизонта. Допус­тим, что при минимальном размере дерева перебора, т. е. при оптимальном порядке перемещений, для углубления счета на глубину N+1 нам необхо­димо рассмотреть в 20 раз больше позиций, чем при счете на глубину N. Это довольно приблизительно, но нам для рассуждений нужно отталкивать­ся от каких-то величин. Существует мнение, что увеличение глубины счета на один полуход повышает силу игры программы на разряд. Может, не сто­ит ломать голову над разными ухищрениями, а просто подождать, пока процессоры станут мощнее в 20 раз. Мы сможем считать на 9 полуходов, потом еще в 20 раз — мы сосчитаем на 10 полуходов. Бывают тактические последовательности, которые программа должна просчитывать значительно глубже. Например, если на доске существует форсированная угроза королю, то может потребоваться считать на 14 полуходов. Гроссмейстеры просчиты­вают некоторые варианты на 20 и более полуходов. Вряд ли мощность про­цессоров когда-либо возрастет до такого уровня, да и программы желатель­но писать сейчас, а не через 10 лет. Человек, когда просчитывает некоторые варианты, руководствуется множеством критериев, зависящих от его опыта. Он может просчитать ситуацию очень глубоко, проанализировав при этом минимальное количество позиций. Несмотря на то, что моделировать мыш­ление шахматиста мы не можем, существуют некоторые строки игры, про­счет которых можно продолжить по совершенно формальным признакам. Возникла простая идея — не сокращать глубину просмотра при некоторых ходах. Мы можем считать на 6 полуходов, но некоторые варианты будут рассмотрены значительно глубже. При каких же ходах не сокращается глу­бина счета? Если мы говорим о шахматах, то это, прежде всего, шах. При шахе игра как бы замирает и требует от противника немедленного ответа. Замедление счета при этом тоже минимальное, т. к. число легальных ходов под шахом ограничено, и узел будет обсчитан очень быстро. Продление все­го лишь шахов резко увеличивает силу игры программы. Считая на 6 полу­ходов, она способна обнаружить глубокие форсированные маты и другие комбинации, основанные на угрозе королю и приводящие к выигрышу ма­териала. Пример функции счета, продлевающей шахи:

Читать »

Дробный Depth

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

Нужно просчитывать глубже многие ходы, но это может привести к взрыву дерева поиска, и только шахи являются стопроцентно корректными расши­рениями на любой глубине. Возникла следующая идея: делать Depth дроб­ным. В каждом узле Depth уменьшается не на 1, а на 4. Начальное значение Depth тоже равно глубине просчета, умноженной на 4. Таким образом, в за­висимости от нашего представления о правдоподобности данного хода, мы можем при одних ходах увеличивать Depth на 4 (при шахах), а при других — на меньшую величину. Приведем примерный список расширений:

Читать »