Sign in to follow this  

Getting the Most out of Minimax/Negamax

Recommended Posts

ssaemployee777    122
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
RPGeezus    216
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.


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
ssaemployee777    122
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