Здравствуйте, уважаемые участники форума!
Задачка такого плана:
доска 5x5, эндшпиль король-ферзь(пусть белый) - против короля(позиция любая допустимая, не шах, не мат, не пат)
научить программу ставить мат поиском по полному дереву возможных ходов
строю дерево рекурсивно спускаясь поиском с возвратом (ограничиваюсь глубиной 7-8),
надеясь что на такой глубине есть выигрышная ветка, при любой игре черного короля.
И вот наконец когда у меня есть это самое дерево в 100 Мб, как мне по нему выбирать оптимальную игру?
Что бы не быть голословным:
///в узле храним только ход, хотя могли бы и конфигурацию на доске (массив 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 эвристическая, такой вывод сделал после просмотра таблиц налимова для такого же окончания.
надо просто полное дерево построить.