минимакс для игры "спички"

[Shadowfiend]

Здравствуйте,
есть 3 кучки (в 1 кучке - 7 спичек, во 2 кучке - 5 спичек, в 3 кучке - 3 спички) забирать можно любое количество спичек, но только из одной кучки, проигрывает тот, кто возьмёт последнюю спичку.
Количество ходов в этой игре не такое большое, поэтому думаю можно построить сразу всё дерево игры, но как правильно реализовать минимакс для игры и как хранить дерево игры?

1) Получается, если начальное состояние [7,5,3] и, если компьютер ходит первый, он может взять 1 спичку из любой кучки, 2 спички из любой кучки, 3 спички из любой кучки, 4 спички или из 1, или из 2 кучки, 5 спичек из 1 или 2 кучки, 6 спичек из 1 кучки, 7 спичек из 1 кучки. (имеется 15 вариантов первого хода), 13 вариантов второго хода и т.д.
Как генерировать и хранить в программе эти варианты?

 

[regnor]

Как генерировать

комбинаторика

хранить в программе эти варианты

вариантов много, можно просто в массиве

 

[Shadowfiend]

комбинаторика


вариантов много, можно просто в массиве

А как потом массив использовать в минимаксе? надо же как-то дойти до листьев, оценить их и потом подниматься по уровням вплоть до корневого узла и только затем возвращать оценку?

 

[Shadowfiend]

Насколько я понимаю, должно быть так:
Игра началась, компьютер ходит первый (например), в метод getMoves() передаётся состояние поля, например, [7,5,3], затем полученные все возможные ходы (я посчитал, вроде всего 192 варианта существует) передаются в minimax() и то, насколько легко будет пройтись по всем вариантам и оценить их, влияет структура данных в которой будут храниться возможные ходы.

 

[regnor]

Насколько я понимаю, должно быть так:
Игра началась, компьютер ходит первый (например), в метод getMoves() передаётся состояние поля, например, [7,5,3], затем полученные все возможные ходы (я посчитал, вроде всего 192 варианта существует) передаются в minimax() и то, насколько легко будет пройтись по всем вариантам и оценить их, влияет структура данных в которой будут храниться возможные ходы.

вам нужна оценка, то есть что то, что будет указывать, что это успешный ход, или нет
а 192 варианта можно пройтись в лоб циклом for, это не так много элементов
и успешные писать в массив, и выбирать рандомом, например
и на втором ходу можно удалять не актуальные ходы, и так же пробегать
а в целом да, так

upd
если у вас задача в алгоритме прохода по всем ходам, то как вариант, можно проходить только по актуальным ходам на данный момент, для этого нужно распределить варианты, какие относятся к первому ходу, ко второму и так далее, и проходить ходы в зависимости от стадии игры, для этого можно использовать словарь

больше пока ниче дельного в голову не идет...

 

[Shadowfiend]

можно пройтись в лоб циклом for,

Так в этом и проблема, какие должны быть условия, как найти все возможные ходы. [7,5,3], [6,5,3], [5,5,3] и т.д. и как потом реализовать *минимакс

*
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
пример из википедии

 

[regnor]

Так в этом и проблема, какие должны быть условия, как найти все возможные ходы. [7,5,3], [6,5,3], [5,5,3] и т.д. и как потом реализовать *минимакс

*
function minimax(node, depth, maximizingPlayer) is
if depth = 0 or node is a terminal node then
return the heuristic value of node
if maximizingPlayer then
value := −∞
for each child of node do
value := max(value, minimax(child, depth − 1, FALSE))
return value
else (* minimizing player *)
value := +∞
for each child of node do
value := min(value, minimax(child, depth − 1, TRUE))
return value
пример из википедии

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