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.
2026-05-15 04:10:41.1778818241
Tree search on game of Imperfect Information
811 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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.