Шахматы 4x4

Тема в разделе "Машинное отделение", создана пользователем Kirr, 6 май 2011.

  1. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.378
    Симпатии:
    2.446
    Репутация:
    163
    Оффлайн
    Начинаю понимать, ради чего сыр-бор затевать с "недошахматами". :)
    Kirr, нельзя ли эндшпиль ещё раз с диаграммками показать, с учётом анализа от Zayats?
  2. Zayats Без определенного статуса

    • Ветеран
    • Старожил
    Рег.:
    08.01.2007
    Сообщения:
    2.136
    Симпатии:
    1.223
    Репутация:
    131
    Оффлайн
    Думаю, это задача архисложная. Все так называемые "стадии" и "ключевые позиции" - суть продукт редукции абсолютного знания, его адаптация к особенностям человеческого мышления и человеческой памяти. Они (стадии и ключевые позиции) уникальны для различных классов эндшпилей и, соответственно, мнемоники формализуются по разному. Напр., со слоном против ладьи проще всего отступать в "правильный" угол, с конем против ладьи - на край, а ладьей против ладьи-слона лучше держаться на предпоследней. В эндшпиле ладья и центральная (слоновая) пешка против ферзя надо оставлять пешку на начальной позиции, если она уже ходила - лучше не двигать дальше, т.к. это лишь облегчит ферзю заход в тыл, но вот на за два хода до превращения позиция становится вновь ничейной - появилась контригра. Т.е. совершенно разнородные правила, каждое само по себе формализовать несложно, но означенные правила появляются как некое обобщение эмпирики, а не автоматически.

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



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


    1.Фе4+ Кра1(а2) 2.Фа8+ Крb1 3.Фа4

    Интересно было бы проверить, действительно ли подобные позиции встречаются чаще прочих или их важность обусловлена особенностями человеческого восприятия.
  3. MS Михаил Семионенков

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

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

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

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



    или



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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Наконец-то кто-то начинает меня понимать. :)

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

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

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

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

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

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Нет, человека из этой миссии нужно исключить. Слишком колоссальный объём работы, чтобы надеяться на существенную помощь человека в поиске эвристик.
  6. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Даже нет, можно ещё лучше. Берём одну фигуру. Берём произвольное поле или область полей. Смотрим все позиции где возможен ход этой фигурой из этой области или в эту область. Если при всех таких ходах значение метрики в позициях где фигура внутри области меньше, чем в позициях с фигурой снаружи области, значит мы нашли границу, необратимый переход. Это позволяет избавиться от условия строгого непересечения спектров, которое, вообще говоря, не обязательный (хотя и достаточный) признак необратимого перехода.
  7. MS Михаил Семионенков

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.378
    Симпатии:
    2.446
    Репутация:
    163
    Оффлайн
    Это спорно, в смысле, плясать от одной фигуры. Эвристики - о взаимном расположении фигур. Чуть двинули, скажем, пешечную структуру - область поменялась. Нужен более сложный процесс обобщения, если эвристики считать важным продуктом (лично я считаю, что если заваривать кашу, то не столько ради табличных решений, сколько для эвристик, которые можно изучать, преподавать).

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

    Kirr Администратор

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

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

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.378
    Симпатии:
    2.446
    Репутация:
    163
    Оффлайн
    Я согласен. "Обучающая выборка" я употребил слишком вольно, скорее в смысле
    "придумать формат представления и хранения эвристик".

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

    Kirr Администратор

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

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.378
    Симпатии:
    2.446
    Репутация:
    163
    Оффлайн
    Ну, начинать-то надо с трёх фигур. На самом деле, решив 3-5 фигурки, мы можем обнаружить, что полнопереборный генератор нам и не нужен. :)
    Мне представляется весьма вероятным, что полный перебор может быть перемещён с уровня позиций на уровень эвристик.
    Если Вы любите заниматься оптимизацией, то наверняка заметили, что шаги 2 и 3 в оптимизации зачастую трудно предсказать, не выполнив шаг 1.
  12. TopicStarter Overlay

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    Так я и делаю.

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

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

    • Команда форума
    Рег.:
    10.02.2006
    Сообщения:
    6.378
    Симпатии:
    2.446
    Репутация:
    163
    Оффлайн
    Рассуждения до кучи. Эвристики нам нужны дважды.
    1. Для оценки позиции.
    2. Для описания плана выигрыша.

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

    Kirr Администратор

    • Команда форума
    Рег.:
    11.02.2006
    Сообщения:
    1.208
    Симпатии:
    22
    Репутация:
    8
    Оффлайн
    К сожалению, не могу пока подтвердить эти данные, у меня число позиций получается меньшим:
    Код:
      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.

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

    • Участник
    • Старожил
    Рег.:
    25.03.2007
    Сообщения:
    1.012
    Симпатии:
    2.477
    Репутация:
    98
    Нарушения:
    15
    Оффлайн

Поделиться этой страницей