Sign in to follow this  
Kani

Query on Alpha-Beta pruning...

Recommended Posts

Hi All, I am planning to implement {Minimax + Alpha Beta pruning} for a game. In chess, there is a strategy known as gambit. A player sacrifices a piece earlier on this the game, which will give him advantage later on in the game. Will {Minimax + Alpha Beta pruning} recognize gamit moves? Or because of pruning, won't the gambit moves get pruned. Or should the utility function take care of this? The game I am planning to implement is not chess. It is an imperfect information card game reduced to perfect information using (selective if I implement it) sampling. I am taking the example of chess because the card game is not very popular.. :P Kindly share your thoughts on this... regards and thanks, Kani

Share this post


Link to post
Share on other sites
Kani,
minimax is based on an evaluation function to decide wich nodes are worth examining or not, so you must take care of "gambits" when evaluating the positions.
In chess usually an approach is used to search deeper certain positions just not to evaluate them in an incorrect way.
As an example, if you have a near to promote pawn and you don't examine promotion, probably your position is underestimated. There are plenty of similar situations.

Since I'm also working on card games ... would you mind sharing information about wich game are you interested on? Send me a private message if you like.

Hope it helps

Share this post


Link to post
Share on other sites
First of all, minimax doesn't prune anything; it's just a mechanism to collect heuristic (or final) values down the tree and propagating them up. Alpha-beta is an improvement over the minimax algorithm that allows pruning of large parts of the tree, but the result is guaranteed to be the same that you would get if you do search the whole tree. So alpha-beta accidentally pruning something important is never an issue.

A chess program will play gambits if it thinks that the sacrifice is favorable. This can be because of positional advantages (your utility function considers development and/or space and it compensates for the loss in material), or because the search is deep enough that it sees how the material is going to be recovered.

Share this post


Link to post
Share on other sites
alvaro is right -- alpha-beta pruning is guaranteed to return the same response as pure minimax. Minimax is an algorithm that returns the optimal move to play ASSUMING THAT BOTH PLAYERS ARE PLAYING OPTIMALLY. In most cases, this is probably what you want. However, often the search space is too large to completely visit (ie reach every single possible game combination to its conclusion, minus pruning). This will probably be the case in your card game, although some games (classically 3x3 Tic-Tac-Toe) can be completely evaulated.

The trick then is to search to a certain tree depth and to stop searching at that point. To properly implement this, you'll need a heuristic function that evaluates (estimates) the strength of the "board position" at the stopped point, probably using methods that you make up based on your knowledge of the game. In this case, if you need to restrict the search depth, than perhaps in your heuristic function you should give extra consideration to "special moves" such as the gambit.

Also note that if you're using selective sampling, this is already a form of heuristic so your software will already not play a "perfect" game. Thus, the play strength will be limited based on the accuracy of your heuristic function, your search depth, and the strength of the sampling technique.

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