Sign in to follow this  
ssaemployee777

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 this post


Link to post
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 this post


Link to post
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)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this