AI Game Playing

Problem Definition

In this assignment, we attempt to create a smarter computer player playing a game called AtroposGame. We do this by having the computer think of future moves and seeing if this will cause the computer to win or lose using AlphaBeta testing. This program is useful since it can be used real world situations like in a strategy such as chess moves.



Method and Implementation

We implemented the alphabeta pruning method with some additional threshold. We initialize alpha to negative infinity and beta to positive infinity. We then run the algorithm which get to the lowest level of the tree and return a score for its condition to decide whether it's good or bad for us to make this move in this depth. the value of alpha and beta keeps being updated in each recursive process inside this method. Within the update process, when alpha is greater or equal to beta, it will break; as a result, the tree will be much smaller than doing an exhaustive search.

 

Design and use of evaluator

The evaluator will return 10 when we will definitely win going this way, -10 when we will definitely lose, or 1 when it's hard to decide. And within the alphabeta search method, whenever it's found that we are going to lose or win for sure, it will stop the recursive alphabeta process and return a very big number to prune even more efficiently. In this way, good threshold and alphabeta pruning works together to make this player plays fast. 

  

Experiments

We tested our codes against the Default player on different board sizes using different lookahead values. We also ran tests against itself.

To run the code:

Compile:javac AtroposGame.javajavac hqgengPlayer.java

 

Run:java AtroposGame # "java hqgengPlayer"Replace # with a number indicating the size of the board, the board size should be at least 5. 

 

Results

Results for hqgengPlayer playing against the Default AI.We ran each setting 20 times and recorded the approximate win ratio.
board size 5 - lookahead 5win ratio: 50%
board size 7 - lookahead 5win ratio: 65%
board size 10 - lookahead 5win ratio: 80%
board size 15 - lookahead 7win ratio: 100%


Results for hqgengPlayer playing against itself.
board size 7 - lookahead 5 win ratio: 50%

Discussion

The speed gets to be slower when board size gets bigger or the depth of alphabeta search gets deeper. However, in general, out algorithm runs very fast, it takes about ten seconds to run for size 15 board with 5 depth alphabeta pruning. And the winning ratio gets to be very high after the board size reaches 10. However, when the size of the board reaches 20 or depth reaches 10, it gets to be very slow and will take much more than 10 seconds to finish the game. 

 

Due to time constraint, we did not implement very detailed configuration for certain patterns, but it works pretty well because our method runs fast enough to allow us to get into good depth in reasonable speed.

Conclusion

This was a very interesting project in gaming AI. The alpha beta procedure is a fairly simple AI for game playing but can be efficient when compared to an AI that just moves randomly within legal space. The lookahead value is very important, a high value would mean it will be more intelligent but a lot slower at the same time, finding an ideal value is very important. For other board games such as chess the alpha beta procedure would be a lot more complicated. But there are AI players out there who can beat the best human chess players in the world. But as for another board game called GO, there is no such AI that can beat a human player. Possibly because the board is too big and the number of possible moves is too many, so we cannot yet efficiently implement a fast AI that can beat a human.

 



 

Credits

Haoqing Geng, Stanley Cheng,Xuli Song