Jump to content

  • Log In with Google      Sign In   
  • Create Account

can i use minmax for player that has more moves contemporary connected?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 sefiroths   Members   -  Reputation: 138

Like
0Likes
Like

Posted 15 August 2012 - 02:14 AM

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.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 15 August 2012 - 07:04 AM

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".

#3 sefiroths   Members   -  Reputation: 138

Like
0Likes
Like

Posted 15 August 2012 - 11:38 AM

i have correct the words, forget my anglish, thanks Posted Image
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.


#4 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 15 August 2012 - 12:59 PM

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.

#5 sefiroths   Members   -  Reputation: 138

Like
0Likes
Like

Posted 16 August 2012 - 07:35 AM

thanks for all explanations,
i'll try




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS