Ищем новые подходы - 2

Краткое содержание предыдущих серий.
В цех вольных кузнецов железных чудищ приходит городской сумасшедчий (МС).
"Покайтесь, языческие поклонники статистической ОФ!".
МС открывает храм "Ищем новые подходы", пытаясь ловить души кузнецов.
Предложенный подход (формализация известных алгоритмов разыгрывания определенных позиций) чуть не соблазнил одну неопытную душу (NS). Но суровый (читай - ленивый ) мастер WildCat сказал: "Не нужны нам частные алгоритмы. Универсальный давай. Или проваливай!" Пригорюнился было блаженный, да надоумило его: есть-де идейка, универсальная, а пойдет ли - то не ведомо". Тут пришел Tulean, да обложил ту идейку чудищем - етюдищем. Забросил МС свой храм, цех покинул, а думку-то думает. И приближается пора второго пришествия...

 

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

 

Пока из "надгробного камня" восстановим диспозицию.

Ядро нынешнего шахматного программирования - селективный перебор и ОФ, базирующаяся на статистиках.
Ряд позиций требуют глубины перебора, превышающей технические возможности обозримого будущего, и разыгрывание их программой на высоком уровне представляется проблематичным.

В качестве гипотетического альтернативного подхода обсуждается переход к "понятиям", приближающий программу к подходам квалифицированного шахматиста.

Обобщенно, такие понятия - слабость, схема динамической обороны слабостей (обобщенные поля соответствия),
средства разрушения обороны (размен, цугцванг и тд).
Программа оперирует планом атаки (обороны) слабости.

Два подхода к реализации этой абстрактной модели.
1. Формализация уже имеющихся знаний (программа распознает позиции, для которых есть планы, и играет по ним) - принципиальная возможность была показана, но это мы уже забраковали, чтобы не погружаться в частности.

2. Формализованы только абстрактные понятия (см. выше), а программа ищет план.
- а теперь мы попробуем прогуляться по этой ветке

Начнем с простенького эндшпиля и послушаем себя...

 

Люди уже забросили плановую игру, так как оказывается что шахматы всё-таки счетная игра
А машины должны сделать шаг назад?
Теория полей соответствия - это задача решаемая ретроспективным анализом, с ней всё ясно.
Очень тяжело найти позицию в которой бы ретроспективный анализ работал бы лучше чем простой перебор (так как Хеширование позиций приближает перебор к ретроспективному анализу)
А даже если он и будет работать лучше - то выигрываем копейки (во времени необходимом для нахождения решения).

 

Хотя под плановой игрой можно понимать несколько иное - продление на ходах перспективных в конкретной позиции. Причем тип позиции и план (перспективные ходы) определять исходя из формальных признаков - пешечной структуры, наличия определенного материала и т.д.

 

Сильно сейчас полемизировать не буду, повторюсь, что пытаюсь уйти от специфики (пример, условно успешный, мы разбирали, и их можно плодить, но сейчас уже не об этом).

Мы говорим об универсальном поиске плана, базирующемся на атаке-защите слабостей.
Универсальность не означает полную замену того, что есть.
Просто к триаде Дебютная библиотека - Перебор+ОФ - Эндшпильные таблицы, в середину добавляется Поиск плана. О технике переключения между (Перебор+ОФ) и (Поиск плана) пока говорить не будем. Неформально, мы ищем план, когда (Перебор+ОФ) не дают желаемого результата.
Задача поиска плана, похоже, будет весьма переборной, но предметом перебора будут не допустимые ходы, а допустимые расстановки фигур, обладающие определенными свойствами, и средства их достижения и разрушения. Предполагаемый выигрыш в силе программы, если он достижим, вытекает из конструктивности поставленных целей плана. Сейчас есть проверка, достигнута ли цель (на доступной глубине перебора). Пробуксовка метода начинается, когда на доступной глубине перебора ОФ не видит прогресса. Мы же попытаемся определить, что нужно сделать, чтобы цель достичь.

 

Странно... Что такое цель плана? Это более успешная расстановка фигур.
То есть та расстановка которая лучше.
То есть та расстановка, которая даст лучшую оценку по ОФ.
Так все шахматные программы тогда и занимаются плановой игрой.
Ищут более удачную расстановку, максимизируют значение ОФ.

 

Цель (абсолютная) игры - поставить мат.
Главные вспомогательные цели - выигрыш материала и проведение пешки в ферзи.
Я собираюсь плясать отсюда. Сейчас, если материал не выигран, ОФ может не сказать (неправильно сказать) о прогрессе. Отсюда позиции, где программы топчутся.
Вскорости я попытаюсь привести конкретный пример, и суждение скептика будет ценно

 

Я не вижу способа, как этого добиться. По крайней мере, пока ОФ базируется на статистиках.

 

Пытаюсь перейти к примеру. Я - не волшебник, не шарлатан, не идиот, убогость примера мне об'яснять не надо.
Увы, чистенько додавить даже простой случай мне не удалось, но уже хочется что-то зафиксировать (это средство от воспаления мозгов). Пока главную угрозу методе выразил NS

"Очень тяжело найти позицию в которой бы ретроспективный анализ работал бы лучше чем простой перебор (так как Хеширование позиций приближает перебор к ретроспективному анализу)
А даже если он и будет работать лучше - то выигрываем копейки (во времени необходимом для нахождения решения)."

Не исключаю, что этим и закончится, но попытка не пытка.

Итак, у нас есть цели
мат,
выигрыш материала,
проведение пешки

План обороны
найти расстановку и схему передвижения фигур, обеспечивающие недостижимость этих целей соперником

План атаки

Доказать отсутствие такой расстановки у соперника
Расстановки потенциально есть, но их можно не допустить (например, перерезая маршруты фигур)
Расстановки достижимы, но они могут быть разрушены (разменом, отвлечением, цугцвангом...)
[не все аккуратно, но это пока вбрасывание шайбы]

Собственно пример.

Король с пешкой против короля (если кто думает, что это игра в одни ворота, как думал я, то он ошибается. С абстрактных позиций - слабая сторона тоже должна рассматривать активную цель - выигрыш материала, поскольку у сильнейшей стороны он есть )

Цели сильнейшей стороны. Мат отпадает. Материала у соперника нет. Остается проведение пешки в ферзи.

Что можно противопоставить проведению пешки (активный план - уничтожение пешки, для простоты исключим)

1. Блокада на одном из полей (т.е. гарантия, что на этом поле при любых обстоятельствах будет фигура, своя или чужая)
2. Эффективный контроль одного из полей (т.е. гарантия, что на момент появления пешки на этом поле, поле будет под ударом, и пешка будет побита)
3. После превращения будет пат.

Опять для простоты берем центральную (е) пешку, исключая 1 и 3.

Т.е. цель черных - эффективно контролировать одно из полей.
Логично начать с поля превращения.
Первый эскиз обороны: король маневрирует по е8 и 5 окрестным полям.
Достижима такая расстановка? Допустим, да.
Эффективна ли она, т.е. достигает гарантии побития пешки на е8?
Нет, поскольку король - фигура особая, и не сможет побить на поле под контролем (короля) соперника.

Уточнение плана атаки: необходимым условием проведения будет контроль королем поля е8.
Уточнение плана обороны - необходимо не допустить контроля е8 соперником. Решение. Маятник е8-е7.
Это уже эффективная расстановка, поскольку она гарантирует черным контроль над е8.
Эффективную расстановку нужно разрушать.
А: взять все поля под под контроль.
Б: взять все поля, кроме одного, и вызвать цугуванг

А не проходит, поскольку е8 полностью контролируется черными.
Остается Б: взять под контроль е7.
Т.е. необходимое условие выигрыша: захват d6, e6 или f6
Корректируем оборону: е7--е6 (игнорируем для простоты потерю контроля над е8)
И т.д. пока не упремся в пешку.

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

 

Использовать логарифмическую шкалу для оценки материала: лучше ладья в простой технической позиции, чем ферзь в при короле под атакой.