# Getting the Most out of Minimax/Negamax

## Recommended Posts

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)
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

Now, here's what I need help on. I know I will be returned a value of 1 if player 1 wins, a value of -1 if player 1 loses but I want to know what moves were performed to get reach that value. Basically I want a list such as: [1,2,3,1...] which tells me how many objects were taken away by each player until the end (when the game is won or lost) Please help out ;) [Edited by - ssaemployee777 on August 3, 2004 1:47:26 PM]

##### Share on other sites
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.

##### Share on other sites
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)

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628366
• Total Posts
2982274

• 10
• 9
• 13
• 24
• 11