Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Ok... I have a game of imperfect information and I want to compute its Minimax Value.From the lectures I know that in order to find the value for a Perfect information game I can use tree search methods.Also I know that this problem for Imperfect information games is NP-hard.But if the game tree is very small can I use alpha-beta pruning for example?Someone told me that I cant but I cannot understand why.

share|improve this question
add comment

1 Answer

In some situations it is possible to turn imperfect information into perfect information of sorts and the use any search method, such as alpha beta pruning. The idea is that you build your game tree by considering all possible moves, based on the information that is available until that point. For example, in a card game you may not know which card is where but you can just assume it is played by some player at a certain point, after which you know that it cannot be played in the subtree below that move. (In a game of bridge, the possibilities may even be restricted further by the bidding history.) Of course this "virtual" game tree can be much bigger than what is actually reachable for a game. However, alpha beta pruning combined with some good heuristics (e.g. move ordering) might just prune enough to make this still a feasible approach.

share|improve this answer
    
How to turn the imperfect to perfect?If I change the game to be perfect then I will have a different game.Do you mean by creating a new game tree with all possible combinations for example? –  nikosdi Nov 25 '12 at 14:45
    
@nikosdi: Yes, like I tried to explain in the card game example. Of course it will not necessarily give the minimax value for the actual tree since it considers much more options and the max value may be too low (or the min value too high). –  WimC Nov 25 '12 at 14:53
    
I understand it.But the value will be a value for a different game.The problem is generally hard I understand.But if I want the value of the game how I can compute it?(In a case of an small game).This is why I tried aplha beta but I had problems with the info-set –  nikosdi Nov 25 '12 at 14:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.