2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3
 
 Re: Шахматы. Дерево ходов
Сообщение10.11.2015, 01:46 
slavav в сообщении #1071825 писал(а):
Позиций не так много: 25 * 25 * 25 * 2 = 31250. (число способов поставить фигуру на доске в кубе на очерёдность хода).
А на 4 поделить не забыли? Доска, кажется, немного симметричная.

 
 
 
 Re: Шахматы. Дерево ходов
Сообщение10.11.2015, 08:43 
rockclimber в сообщении #1071892 писал(а):
slavav в сообщении #1071825 писал(а):
Позиций не так много: 25 * 25 * 25 * 2 = 31250. (число способов поставить фигуру на доске в кубе на очерёдность хода).
А на 4 поделить не забыли? Доска, кажется, немного симметричная.


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

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

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

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

 
 
 
 Re: Шахматы. Дерево ходов
Сообщение18.11.2015, 13:31 
Ну нет, король может быть зажат со всех сторон и при этом прекрасно себя чувствовать.

 
 
 
 Re: Шахматы. Дерево ходов
Сообщение26.11.2015, 11:12 
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 можно
поэтому при полном переборе, если хочется. чтобы он был умным, надо начинать перебор с тех ходов, которые гонять короля белых в центр, а если он в центре, рассматривать сначала только ходы ферзем
При этом же переборе за черных, в первую очередь рассматривать ходы, которые не пускаю короля белых в центр

 
 
 
 Re: Шахматы. Дерево ходов
Сообщение26.11.2015, 12:24 
Число позиций на доске 5 на 5 около 30000. Число позиций на доске 8 на 8 около 500000. Умный перебор не нужен.

 
 
 [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group