Шахматы. Дерево ходов

[rockclimber]

Я сейчас немного подумал и придумал такой вариант.
Конкретно для такого эндшпиля (король и ферзь против короля) строим алгоритм так. Ферзь, находясь в любой точке поля, делит его на 4 изолированные (то есть король противника не может перейти из одной части в другую) друг от друга части. Общее направление движения - ограничивать свободу короля так, чтобы рано или поздно запереть его. Поэтому:
1. первым ходом определяем, куда должен пойти ферзь. Условия:
1.1 поле доступно для хода и
1.2 король противника оказывается в зоне минимального размера.
2. каждый следующий ход должен уменьшать доступную для короля противника область, но: для загона может использоваться король, поэтому надо смотреть на два хода вперед (то есть откидывать ветки, которые через 2 хода не дают улучшения).
Я конечно не ахти какой мастер шахмат и доски под рукой нет, но вроде 7 ходов должно быть достаточно для выигрыша из любой позиции.

[mserg]

Если речь идет о желании научиться программировать игры, то следует иметь в виду следующее.

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

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

Также можно посмотреть оптимизацию этого алгоритма: альфа-бета отсечение

[shukshin]

Geen, для белых - кратчайший выигрыш
для черных - ничья или длиннейший выигрыш белых

[rockclimber]

rockclimber в сообщении #1071472 писал(а):

но: для загона может использоваться король, поэтому надо смотреть на два хода вперед (то есть откидывать ветки, которые через 2 хода не дают улучшения).

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

[Geen]

rockclimber в сообщении #1071472 писал(а):

Я сейчас немного подумал и придумал такой вариант.

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

[Iam]

Geen, в теории игр определено понятие оптимальных стратегий. В данном случае для некоторой стратегии белых оптимальной стратегией черных является та, для которой обеспечивается максимальная длительность игры. Аналогично (с точностью наоборот) определяется оптимальная стратегия белых. Оптимальная игра это такая, при которой игроки используют стратегии составляющие седловую точку.

[Geen]

shukshin в сообщении #1071476 писал(а):

для черных - ничья или длиннейший выигрыш белых

Как чёрные могут добиться ничьей??

-- 08.11.2015, 23:21 --

Iam в сообщении #1071484 писал(а):

в теории игр определено понятие оптимальных стратегий.

Я знаю

Iam в сообщении #1071484 писал(а):

Оптимальная игра это

А вот тут можно ссылку? А то ни разу не встречал.

[rockclimber]

Geen в сообщении #1071483 писал(а):

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

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

[Iam]

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

[Geen]

Iam в сообщении #1071491 писал(а):

Вам нужно зацепиться за слова или понять, что ТС имел в виду?

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

rockclimber в сообщении #1071490 писал(а):

Там применительно к теории игр есть какие-то нетривиальные нюансы?

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

[Anton_Peplov]

shukshin в сообщении #1071456 писал(а):

я надеюсь, самый затянутый мат при самой оптимальной игре не длиннее семи полуходов на доске 5 на 5 с такими фигурами.

Это Вы зря надеетесь. Возьмите доску 5 на 5, поставьте черного короля в самый центр, а белого короля на самый край. Задача ферзя с королем - оттеснить вражеского короля на последнюю горизонталь или вертикаль. Задача черного короля - до последнего не давать себя оттеснить. За сколько ходов удалось поставить мат?

[mserg]

(Оффтоп)

mserg в сообщении #1071475 писал(а):

Если речь идет о желании научиться программировать игры, то следует иметь в виду следующее.

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

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

Также можно посмотреть оптимизацию этого алгоритма: альфа-бета отсечение

"Вражеский ферзь" выше читать как "Вражеский король". Хотя, видимо, это не важно.

[Sender]

shukshin в сообщении #1071468 писал(а):

поднимаемся наверх, если для всех BlackReplies Код:

move->mark = 1;

Код:

this->mark = 1;

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

[slavav]

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

[mserg]

(Оффтоп)

slavav в сообщении #1071825 писал(а):

Позиций не так много: 25 * 25 * 25 * 2 = 31250. (число способов поставить фигуру на доске в кубе на очерёдность хода).

Пока никто не успел, пошучу первым: "Раньше, вроде бы, не разрешалось на одну клетку ставить несколько фигур. Наверное, что-то поменялось в шахматных правилах"