2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Шахматы. Дерево ходов
Сообщение08.11.2015, 14:08 


20/10/12
235
Здравствуйте, уважаемые участники форума!
Задачка такого плана:
доска 5x5, эндшпиль король-ферзь(пусть белый) - против короля(позиция любая допустимая, не шах, не мат, не пат)
научить программу ставить мат поиском по полному дереву возможных ходов
строю дерево рекурсивно спускаясь поиском с возвратом (ограничиваюсь глубиной 7-8),
надеясь что на такой глубине есть выигрышная ветка, при любой игре черного короля.

И вот наконец когда у меня есть это самое дерево в 100 Мб, как мне по нему выбирать оптимальную игру?
Что бы не быть голословным:

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
///в узле храним только ход, хотя могли бы и конфигурацию на доске (массив 5x5)
///памяти жалко, все-таки дерево не маленькое вырастает
typedef struct _node
{
    int horz; //куда?
    int vert;
    int figure;//какая фигура?

    int depth;//глубина от начальной позиции в количестве полуходов
    int mark; //какая-то информация о ходе - например, мат (нигде не использую пока что)
    vector < struct _node * > replies; //возможные ответы
}node;

Поиск(int field[5][5], int order, node *T)
{
///по всем клеткам
for(i = 0; i < 5; ++i)
          for(j = 0; j < 5; ++j)
          {
                if(!order)//чей ход?
                {
                 if(possible_for_Q(j, i, field))
                {
                        node *move = new node;
                        find(field, &Qx, &Qy, &Wx, &Wy, &Bx, &By);

                        move->depth = T->depth + 1;
                        move->figure = QUEEN;
                        move->horz = j;
                        move->vert = i;
                        move->mark = 0;
               
                        T->replies.push_back(move);

                        field[Qy][Qx] = 0;
                        field[i][j] = QUEEN;

                        play(field, 1, move);

                        field[Qy][Qx] = QUEEN;
                       field[i][j] = 0;
                  }
                 if(possible_for_W(j, i, field))
                  {
                        ///...
                  }
                }
                else if(order)
                   ///......

           }
}
 

Вот что-такое у меня сейчас есть, перебирающее некоторое количество осмысленных вариантов
(нельзя, например, терять ферзя это всегда избегаемо и т.п.)
Как по построенному дереву программе выбирать ход? (всегда побеждать)
Победа компьютера всегда есть и это очевидно из соображений для доски 8x8,
глубина ~7 эвристическая, такой вывод сделал после просмотра таблиц налимова для такого же окончания.

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


27/04/09
28128
Ну, если вы просто построили дерево и всё, то толку от него не больше, чем от перебора на месте. Надо его при/после построения допилить. В том числе можно выкинуть много неинтересных ходов — например, приводящих к той же позиции (с учётом того, кто ходит) за не большее число ходов. Для этого можно хешировать позиции и записывать уже полученные в какой-то большой список, и каждую новую с тем же цветом ходящего проверять, нет ли её хеша в списке. Это и быстро, и при удачной функции хеширования отсеет большинство, если не все, повторений.

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

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


26/05/14
981
Вам нужна эвристическая функция (функция оценки). Эта функция по позиции возвращает число. Чем больше число, тем "желаннее" для вас позиция. Например, мату должны соответствовать большие значения, а потере ферзя или пату маленькие. С помощью этой функции вам надо оценить все позиции в дереве и выбрать самую лучшую. Затем делаете шаг по пути от текущей позиции в лучшую.

Для эндшпилей, насколько я знаю есть специальные эвристические функции. Навскидку такая функция должна учитывать материал (храним ферзя) и уменьшать площадь доступную противному королю.

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


01/09/13
4318
slavav в сообщении #1071433 писал(а):
Вам нужна эвристическая функция (функция оценки).

Зачем? Ведь в задаче требуется полное дерево построить...

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


20/10/12
235
slavav
действительно, зачем дерево ходов, если есть эвристика и наоборот.
метод выбран - полностью построенное дерево ходов до глубины скажем 7. как нестрогий факт - уже должны появится ветки полной победы при любой игре короля. вопрос - их найти в гигантском дереве.

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


06/07/11
5627
кран.набрать.грамота
А что если в процессе построения дерева каждый раз, когда находится выигрышный ход (мат), передавать по цепочке к корню информацию о найденном решении и помечать все узлы, ведущие к этому решению? Тогда, кроме всего прочего, можно будет после окончания перебора еще и выкинуть все ненужные ветки.

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


26/05/14
981
Прошу прощения. Я не понял вопрос. ТС, добавьте в дерево ссылки от детей к родителям. Обойдите дерево, найдите мат. От него вернитесь по цепочке ходов к начальной позиции. Сделайте ход вдоль найденного пути.

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

-- 08.11.2015, 21:59 --

shukshin в сообщении #1071445 писал(а):
действительно, зачем дерево ходов, если есть эвристика и наоборот.


Эвристика и дерево работают вместе. Называется best-first search.

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


20/10/12
235
slavav, да, я это называю отбрасыванием совсем нелогичных ходов.
вот какая штука. мало мат найти. мат должен быть для каждого ответа черных.

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


01/09/13
4318
shukshin в сообщении #1071445 писал(а):
полностью построенное дерево ходов до глубины скажем 7

С чего вдруг "до глубины 7" будет полным деревом?

shukshin в сообщении #1071311 писал(а):
как мне по нему выбирать оптимальную игру?

Ну как обычно - есть цена игры. Если имеем полное дерево, то цена определена на листьях "изначально". Идём от листьев к корню всякий раз вычисляя цену игры в узле как максимум или минимум (в зависимости от того чей ход) от цены в дочерних узлах...

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


01/11/14
195
Мат дель Рио (в примере 21) на поле 5х5 с жертвой коня, затем ферзя ставится одним слоном (против ферзя, ладьи и трех пешек). Такие ситуации могут возникать после 7-го хода.

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


20/10/12
235
Iam, речь идет не совсем о шахматах. Хочу научить компьютер выигрывать тривиальный эндшпиль.
Geen, я надеюсь, самый затянутый мат при самой оптимальной игре не длиннее семи полуходов на доске 5 на 5 с такими фигурами.

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


01/09/13
4318
shukshin в сообщении #1071456 писал(а):
я надеюсь

Не надо надеяться ;-) надо просто полное дерево построить.

shukshin в сообщении #1071456 писал(а):
Хочу научить компьютер выигрывать тривиальный эндшпиль.

Попробуйте крестики-нолики....

shukshin в сообщении #1071456 писал(а):
речь идет не совсем о шахматах.

А как с правилом трёхкратного повторения позиции? ;-)

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


01/11/14
195
shukshin, если говорить о тривиальном эндшпиле с такими фигурами, то задачка выглядит несложной. С учетом симметрии есть всего три матовых позиции черного короля. Далее перебираем немного вариантов матового расположения белых фигур и двигаемся в обратных допустимых направлениях, пока не покроем всевозможные исходные варианты расположений всех фигур.

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


20/10/12
235
Iam
можно и с конца, но те же проблемы. просто найдем путь к какому-то мату при определенной игре короля.
Geen
повторения нет смысла смотреть, оптимальная игра, понятно, без повторений

Из всех моих обсуждений и размышлений можно наверное такой алгоритм сделать:
если мат отмечаем
Код:
mark = 1;

поднимаемся наверх, если для всех BlackReplies
Код:
move->mark = 1;

Код:
this->mark = 1;

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


01/09/13
4318
shukshin в сообщении #1071468 писал(а):
повторения нет смысла смотреть, оптимальная игра, понятно, без повторений

Оптимальная для кого????

И что такое вообще "оптимальная игра"?

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

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



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

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


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

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