Jump to content
  • Advertisement
Sign in to follow this  

Getting the Most out of Minimax/Negamax

This topic is 5069 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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.


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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!