Шахматы 4x4

Начинаю понимать, ради чего сыр-бор затевать с "недошахматами".
Kirr, нельзя ли эндшпиль ещё раз с диаграммками показать, с учётом анализа от Zayats?

Конечно, заявленная Kirr-ом идея автоматического выявления этих самых "редукций" - дело жутко далёкого будущего. Начать можно с обратной задачи: человек вбрасывает эфристику "класс позиции - план выигрыша", а комп тупо находит находит исключения, заставляя человека пересмотреть как класс позиции, так и план выигрыша.

Например, я заявляю эвристику для KPk:

класс позиции: при ходе сильнейшей стороны, король слабейшей стороны вне квадрата
план выигрыша: скорейшим способом проводим ферзя

комп тыкает носом в позиции типа



или



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

Наконец-то кто-то начинает меня понимать.

Сорри, не было времени углубиться в анализ (Пеняйте на Crest-а ).

Согласен, это сложно, но мы можем пытаться.

Вот, например, самое прямолинейное направление атаки на эту проблему. Берём определённый решённый эндшпиль. Берём какую-то одну фигуру (например, чёрного короля), начинаем ставить на разные поля, и смотрим спектр метрики. Если находим поля (или области из нескольких полей), где спектры не пересекаются, то вот мы и нашли фазы с необратимым переходом между ними. (Лучше, наверное, использовать DTZ для этих целей).

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

В итоге мы, как минимум, сможем уменьшить размер таблиц, ещё больше приближаясь к WDL (или даже обходя WDL). Это - реальная и практическая цель. В идеале нам, наверное, захочется совсем выбросить таблицы, и оставить лишь "понимание". Реально это или нет - я пока не знаю.

Интересно. Нужно думать и пробовать.

Нет, человека из этой миссии нужно исключить. Слишком колоссальный объём работы, чтобы надеяться на существенную помощь человека в поиске эвристик.

Даже нет, можно ещё лучше. Берём одну фигуру. Берём произвольное поле или область полей. Смотрим все позиции где возможен ход этой фигурой из этой области или в эту область. Если при всех таких ходах значение метрики в позициях где фигура внутри области меньше, чем в позициях с фигурой снаружи области, значит мы нашли границу, необратимый переход. Это позволяет избавиться от условия строгого непересечения спектров, которое, вообще говоря, не обязательный (хотя и достаточный) признак необратимого перехода.

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

И если об эвристиках - стартовую обучающую выборку всё одно человек должен сделать руками и формализовать, обкатать на решённых эндшпилях.

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

Если в каких-то окончаниях найдутся полезные эвристики для одной фигуры - это будет уже замечательно. Если же нет - то я по крайней мере буду уже точно знать, что их там нет.

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

Я согласен. "Обучающая выборка" я употребил слишком вольно, скорее в смысле
"придумать формат представления и хранения эвристик".

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

Полная доска всё-таки предьявляет несколько другие требования к эффективности генератора, если мы хотим работать с шестью-семью фигурами. Меньше помещается в память - следовательно нужен какой-то своп таблиц на диск. Любого результата нужно ждать дольше времени. В общем, можно было бы ограничиться пятью фигурами и что-то пробовать, мне показалось привлекательнее уменьшить доску. Так удобнее обкатывать новые концепции, и упрощение получается как раз критическое. Без жёстких рамок по эффективности можно меньше времени тратить на оптимизацию, и больше на что-то более интересное.

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

Ну, начинать-то надо с трёх фигур. На самом деле, решив 3-5 фигурки, мы можем обнаружить, что полнопереборный генератор нам и не нужен.
Мне представляется весьма вероятным, что полный перебор может быть перемещён с уровня позиций на уровень эвристик.
Если Вы любите заниматься оптимизацией, то наверняка заметили, что шаги 2 и 3 в оптимизации зачастую трудно предсказать, не выполнив шаг 1.

Так я и делаю.

Всё может быть. Я с вами согласен, что это очень интересное направление, несомненно достойное экспериментов. Удастся ли избавиться от перебора на уровне позиций, и как это всё будет выглядеть - вопросы пока открытые.

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

Рассуждения до кучи. Эвристики нам нужны дважды.
1. Для оценки позиции.
2. Для описания плана выигрыша.

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

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

Код:

  2             5
  3           325
  4         9,309
  5       142,572
  6     1,277,268
  7     6,819,308
  8    20,282,213
  9    26,156,564

В сумме 54,687,564.

(Данные из нового генератора на ранней стадии разработки, поэтому могут быть неточными).