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

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

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

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

Читать »

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

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

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

Читать »