4 replies to this topic

[sefiroths]

Hi, i'm wondering if i can use minmax for this problem or i should try another way:
a player has 4 pawns that can move accordingly with a roll of 4 dice.
a pawn can move a square spending one die, 2 square spending 2 dice and so on.
a dce used for a pawn will be not used by another pawn.
this lead not to a list of moves, but a tree of moves...

i can make a search on the tree to find all possible game status makeing a list to parse on minmax...
or will be more convenient another approach?

thanks

Edited by sefiroths, 15 August 2012 - 11:26 AM.

[Álvaro]

The biggest obstacle to using minimax for this situation is not the difficulty of obtaining a list of moves. The problem is the presence of randomness.

I would try Monte Carlo techniques instead. Look up Monte Carlo Tree Search (MCTS). But if you don't have experiend writing engines for other games, this doesn't sound particularly easy to start with...

By the way, the singular is "die" and the plural is "dice".

[sefiroths]

i have correct the words, forget my anglish, thanks
i have searched and if i had understood well, MCTS plays many games with random moves till the end of the game, then choose the move that gave victory more times.
so i looked computer go, chess, connect 4...
perhaps to study the method should i start from tic-tac-toe and connect 4?

however, how can you make the list of moves so easily?

thanks for help

Edited by sefiroths, 15 August 2012 - 11:41 AM.

[Álvaro]

perhaps to study the method should i start from tic-tac-toe and connect 4?

Those games are fine. Chess is a bad place to start because it's not easy to get MCTS to play reasonably well. Tic-tac-toe I have implemented myself and it works just fine.

however, how can you make the list of moves so easily?

Well, since Monte Carlo methods don't rely on alternating turns, you could decompose a turn into several moves, and generate them randomly. So you roll your dice, then assign them to the pawns randomly and decide how much to move each pawn and in what direction also randomly.

If the resulting program doesn't play well (which is likely), you can improve it by selecting good moves more often than bad ones.

[sefiroths]

thanks for all explanations,
i'll try