All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99

ViewsDownloads

Relative Articles

More...

Research on Different Heuristics for Minimax Algorithm Insight from Connect-4 Game

DOI: 10.4236/jilsa.2019.112002, PP. 15-31

Keywords: Heuristics, Minimax Algorithm, Zero-Sum Game, Connect-4 Game

Full-Text   Cite this paper   Add to My Lib

Abstract:

Minimax algorithm and machine learning technologies have been studied for decades to reach an ideal optimization in game areas such as chess and backgammon. In these fields, several generations try to optimize the code for pruning and effectiveness of evaluation function. Thus, there are well-armed algorithms to deal with various sophisticated situations in gaming occasion. However, as a traditional zero-sum game, Connect-4 receives less attention compared with the other members of its zero-sum family using traditional minimax algorithm. In recent years, new generation of heuristics is created to address this problem based on research conclusions, expertise and gaming experiences. However, this paper mainly introduced a self-developed heuristics supported by well-demonstrated result from researches and our own experiences which fighting against the available version of Connect-4 system online. While most previous works focused on winning algorithms and knowledge based approaches, we complement these works with analysis of heuristics. We have conducted three experiments on the relationship among functionality, depth of searching and number of features and doing contrastive test with sample online. Different from the sample based on summarized experience and generalized features, our heuristics have a basic concentration on detailed connection between pieces on board. By analysing the winning percentages when our version fights against the online sample with different searching depths, we find that our heuristics with minimax algorithm is perfect on the early stages of the zero-sum game playing. Because some nodes in the game tree have no influence on the final decision of minimax algorithm, we use alpha-beta pruning to decrease the number of meaningless node which greatly increases the minimax efficiency. During the contrastive experiment with the online sample, this paper also verifies basic characters of the minimax algorithm including depths and quantity of features. According to the experiment, these two characters can both effect the decision for each step and none of them can be absolutely in charge. Besides, we also explore some potential future issues in Connect-4 game optimization such as precise adjustment on heuristic values and inefficiency pruning on

References

[1]  Krauthammer, C. (2018) “Be Afraid”.
https://www.weeklystandard.com/be-afraid/article/9802
[2]  Allis, L.V. (1988) A Knowledge-Based Approach of Connect-Four. ICGA Journal, 11, 165-165.
https://doi.org/10.3233/ICG-1988-11410
[3]  Shock, M. and Shaout, A. (2007) AI for a Connect 4 Game.
[4]  Russell, S. J. and Norvig, P. (2016) Artificial Intelligence: A Modern Approach. Pearson Education Limited, Malaysia.
[5]  Pearl, J. (1984) Heuristics: Intelligent Search Strategies for computer Problem Solving.
[6]  Neummann, J. and Morgenstern, O. (1944) Theory of games and Economic Behaviour.
[7]  Sion, M. (1958) On General Minimax Theorems. Pacific Journal of Mathematics, 8, 171-176.
https://doi.org/10.2140/pjm.1958.8.171
[8]  Parthasarathy, T. (1970) On Games over the Unit Square. SIAM Journal on Applied Mathematics, 19, 473-476.
https://doi.org/10.1137/0119047
[9]  Shannon, C.E. (1988) Programming a Computer for Playing Chess. In: Levy, D., Ed., Computer Chess Compendium, Springer, New York, NY, 2-13.
https://doi.org/10.1007/978-1-4757-1968-0_1
[10]  Roughgarden, T. (2018) Complexity Theory, Game Theory, and Economics. Electronic Colloquium on Computational Complexity, Trier.
[11]  Madsen, K., Schjær-Jacobsen, H. and Voldby, J.B.R.G.E.N. (1975) Automated Minimax Design of Networks. IEEE Transactions on Circuits and Systems, 22, 791-796.
https://doi.org/10.1109/TCS.1975.1083973
[12]  Neto, G. and Lima, P. (2005) Minimax Value Iteration Applied to Robotic Soccer. Proceedings of the IEEE ICRA 2005 Workshop on Cooperative Robotics, Barcelona, 18-22 April 2005.
http://pdfs.semanticscholar.org/8bec/440961868d889d7e2011569dc9239fe3535a.pdf
[13]  Brams, S.J., Kilgour, D.M. and Sanver, M.R. (2007) A Minimax Procedure for Electing Committees. Public Choice, 132, 401-420.
https://doi.org/10.1007/s11127-007-9165-x
[14]  https://github.com/Qtrain/Java/blob/master/src/unfinishedProjects/connectfour/Board.java

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133

WeChat 1538708413