def NegaMax(objects, player):
if objects == 0:
if player == 1:
return 1
if player == 2:
return -1
best = -2
successors = GenerateMoves(objects)
while successors:
new_objects = objects - successors[0]
del successors[0]
value = -NegaMax(new_objects, OtherPlayer(player))
if (value > best):
best = value
return best
Getting the Most out of Minimax/Negamax
Author
Hello. I'm fairly new to AI programming.
I have a Negamax function for Nim (the kind where you remove 1,2, or 3 objects at a time and the person to take the last one loses). It's written in python -- still should be easy to understand:
Note: player 1 is the maximizing player
Note: successors is a list of the possible number of objects that can be taken away (usually 1,2, and 3)
The link Alvaro posted has code to do what you want.
Essentially each and every move in the tree gets a list of moves. As you traverse up the list a parent node chooses the child nodes list.
i.e.
If you do a 7 ply search, each leafe node (move 7) will contain a list with 1 move-- the move it just made.
At ply 6, say there are 4 options. This move contains a list with one move (the move at ply 6). It chooses the best one, addes the child nodes list to it's list, therefore generating a list with two moves.
Up the tree you...
At ply 0 you'll have a selection of moves, each with a list 6 moves long. Picking the best one and adding it's list to the current move will give you a list of 7 moves.
Good luck.
Essentially each and every move in the tree gets a list of moves. As you traverse up the list a parent node chooses the child nodes list.
i.e.
If you do a 7 ply search, each leafe node (move 7) will contain a list with 1 move-- the move it just made.
At ply 6, say there are 4 options. This move contains a list with one move (the move at ply 6). It chooses the best one, addes the child nodes list to it's list, therefore generating a list with two moves.
Up the tree you...
At ply 0 you'll have a selection of moves, each with a list 6 moves long. Picking the best one and adding it's list to the current move will give you a list of 7 moves.
Good luck.
Author
Thanks for the link and the explanation but I dont understand the C-code given on the link, because as far as I know, Python doesn't use those structures, and pointers, and 'buffers'. Can anyone clear up these terms for me so I can relate them to Python? (psuedocode would help)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement