2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:09 


17/10/08

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

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

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

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:09 


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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:10 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
rockclimber в сообщении #1071472 писал(а):
но: для загона может использоваться король, поэтому надо смотреть на два хода вперед (то есть откидывать ветки, которые через 2 хода не дают улучшения).

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:17 
Заслуженный участник
Аватара пользователя


01/09/13
4318
rockclimber в сообщении #1071472 писал(а):
Я сейчас немного подумал и придумал такой вариант.

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:18 


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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:18 
Заслуженный участник
Аватара пользователя


01/09/13
4318
shukshin в сообщении #1071476 писал(а):
для черных - ничья или длиннейший выигрыш белых

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

-- 08.11.2015, 23:21 --

Iam в сообщении #1071484 писал(а):
в теории игр определено понятие оптимальных стратегий.

Я знаю ;-)

Iam в сообщении #1071484 писал(а):
Оптимальная игра это

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:29 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Geen в сообщении #1071483 писал(а):
Вы немного вперёд забегаете - использовать эвристики, альфа-бета отсечение и т.п. можно только освоившись с понятием дерева игры
Ну мы люди простые, теорию игр и шахмат не изучали. А какие могут быть трудности с понятием дерева? Дерево и дерево. Там применительно к теории игр есть какие-то нетривиальные нюансы?

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:29 


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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение08.11.2015, 23:47 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Iam в сообщении #1071491 писал(а):
Вам нужно зацепиться за слова или понять, что ТС имел в виду?

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

rockclimber в сообщении #1071490 писал(а):
Там применительно к теории игр есть какие-то нетривиальные нюансы?

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение09.11.2015, 00:08 
Заслуженный участник
Аватара пользователя


20/08/14
8062
shukshin в сообщении #1071456 писал(а):
я надеюсь, самый затянутый мат при самой оптимальной игре не длиннее семи полуходов на доске 5 на 5 с такими фигурами.

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение09.11.2015, 01:31 


17/10/08

1313

(Оффтоп)

mserg в сообщении #1071475 писал(а):
Если речь идет о желании научиться программировать игры, то следует иметь в виду следующее.

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

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

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

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение09.11.2015, 21:23 


14/01/11
2916
shukshin в сообщении #1071468 писал(а):
поднимаемся наверх, если для всех BlackReplies Код:

move->mark = 1;

Код:

this->mark = 1;

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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение09.11.2015, 22:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Шахматы. Дерево ходов
Сообщение09.11.2015, 23:53 


17/10/08

1313

(Оффтоп)

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group