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

[rockclimber]

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

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

А на 4 поделить не забыли? Доска, кажется, немного симметричная.

[slavav]

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

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

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

А на 4 поделить не забыли? Доска, кажется, немного симметричная.

Нет, не забыл. Моя идея в том что даже простое представление в виде номеров клеток под фигурами даёт такое малое число вариантов, что оптимизировать полный перебор графа нет смысла. Мы можем забыть про симметрию доски и про то что фигуры нельзя ставить в одну клетку. Граф можно обойти меньше чем за секунду на современном компьютере и займёт он 30 килобайт памяти. Зачем оптимизировать?

[Mihaylo]

Задача относится к теории игр. Более-менее доступно о методе решения таких задач рассказывается в книге Рассела С., Норвига П. Искусственный интеллект. Современный подход. 2006. (глава 17. Принятие сложных решений).

Дерево всех возможных ходов - это, конечно, замечательно. Можно даже посчитать, сколько ходов осталось до окончания эндшпиля, если бы соперник не мог делать произвольные ходы. Из-за неопределенности хода соперника число ходов до окончания эндшпиля является случайной величиной.
Если применить некоторую эвристику по отношению к стратегии соперника, то число ходов до окончания игры может стать более-менее неслучайным, более определенным.
Как уже посоветовали, потренируйтесь на "крестиках-ноликах".

[B@R5uk]

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

[Sender]

Ну нет, король может быть зажат со всех сторон и при этом прекрасно себя чувствовать.

[ET]

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

доска 5x5, эндшпиль

Извините, а почем сразу 8 на 8 не хотите? На доске 8х8 вся эта тема наверное имела бы смысл, а на 5х5....
Дело в том, что я еще в студенчестве писал решалку шахматных задач. Могу сказать, что на современных компах та решалка на четырехходовках, насыщенных фигурами, уже не очень тормозит. А тут доска в 2 раза меньше и малое число фигур. На такой доске сколько максимальное число ходов до мата? Думаю, вполне приемлемо просто до конца расчитать. Поэтому если писать что-то такое умное, то есть смысл сразу на нормальной доске

-- Чт ноя 26, 2015 15:07:04 --

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

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

Конкретно для доски 5 на 5 я бы другое предложил: Если король белых в центре, то сомневаюсь в существовании позиций, где нельзя поставить мат в 3 хода, а скорее всего всегда в 2 можно
поэтому при полном переборе, если хочется. чтобы он был умным, надо начинать перебор с тех ходов, которые гонять короля белых в центр, а если он в центре, рассматривать сначала только ходы ферзем
При этом же переборе за черных, в первую очередь рассматривать ходы, которые не пускаю короля белых в центр

[slavav]

Число позиций на доске 5 на 5 около 30000. Число позиций на доске 8 на 8 около 500000. Умный перебор не нужен.