beta pruning depth
I have implemented a connect 4 AI to play in a tournament for my class. I have implemented a depth limited minimax with alpha-beta pruning. We are allowed to give one depth to give as an argument for the tournament. My program will make a move, then another student will make a move, and this continues until there is a winner. It is also a modified connect 4 in which the entire 42 spots in the 6×7 game board are filled, and every 4-in-a-row is a point, and the most points wins.
My question is about the alpha-beta pruning. Our moves have to take "about 1 second", so anything under 2 seconds should be fine. Running my program without alpha-beta pruning allows a move about 1.3 seconds or less at depth 6. Depth 7 is unacceptable. Now, with alpha-beta pruning, can I guarantee that I can change my depth to go deeper? I know on average that it will let me go deeper, but I believe on the worst case nothing gets pruned, and I would exceed the time limit. Is this correct?
This IS correct: in the worst-case scenario, alpha-beta is just as slow as minimax.
Bit there is a really small chance for that to happen. To optimise alphabeta and prevent that problem, search "move ordering alpha beta" on google.
If you have to stay inside a time limit, I suggest to use iterative deepening (search with depth 1, 2, ..., x). That should not be a problem due to the exponential explosion. If your program runs out of time, just play the move you figured out with the previous searchdepth.
链接地址: http://www.djcxy.com/p/9636.html上一篇: 实施和使用四行（connect4）游戏的MinMax
下一篇: beta修剪深度