The Transactions of The Korean Institute of Electrical Engineers (전기학회논문지)

The Korean Institute of Electrical Engineers (대한전기학회)
권호 표지
DOI QR코드

DOI QR Code

An Implementation of Othello Game Player Using ANN based Records Learning and Minimax Search Algorithm

ANN 기반 기보학습 및 Minimax 탐색 알고리즘을 이용한 오델로 게임 플레이어의 구현

  • Received : 2018.11.06
  • Accepted : 2018.11.14
  • Published : 2018.12.01
Download PDF
⟨ Previous Next ⟩

Abstract

This paper proposes a decision making scheme for choosing the best move at each state of game in order to implement an artificial intelligence othello game player. The proposed decision making scheme predicts the various possible states of the game when the game has progressed from the current state, evaluates the degree of possibility of winning or losing the game at the states, and searches the best move based on the evaluation. In this paper, we generate learning data by decomposing the records of professional players' real game into states, matching and accumulating winning points to the states, and using the Artificial Neural Network that learned them, we evaluated the value of each predicted state and applied the Minimax search to determine the best move. We implemented an artificial intelligence player of the Othello game by applying the proposed scheme and evaluated the performance of the game player through games with three different artificial intelligence players.

Keywords

References

  1. Silver, D. et al., "Mastering the game of Go with deep neural networks and tree search", Nature 529, 484-489, 2016. https://doi.org/10.1038/nature16961
  2. Silver, D. et al., "Mastering the game of Go without human knowledge", Nature 550, 354-359, 2017. https://doi.org/10.1038/nature24270
  3. M. Campbell, A.Joseph Hoane, Feng-hsiung Hsu, "Deep Blue", Artificial Intelligence, Volume 134, Issues 1-2, 57-83, 2002. https://doi.org/10.1016/S0004-3702(01)00129-1
  4. M. Buro, "LOGISTELLO-A Strong Learning Othello Program", NEC Research Institute, Princeton, NJ, 1997.
  5. P. S. Rosenbloom, "A World-Championship-Level Othello Program", Artificial Intelligence 19, 279-320, 1982. https://doi.org/10.1016/0004-3702(82)90003-0
  6. K.-F. Lee, S. Mahajan, "The Development of a World Class Othello Program", Artificial Intelligence 43, 21-36, 1990. https://doi.org/10.1016/0004-3702(90)90068-B
  7. J. Schaeffer, H.J. van den Herik, "Chips Challenging Champions: Games, Computers and Artificial Intelligence", 135, 2002.
  8. Gunawan, Hendrawan Armanto, Joan Santoso, Daniel Giovanni, Faris Kurniawan, Ricky Yudianto, Steven, "Evolutionary Neural Network for Othello Game", Procedia -Social and Behavioral Sciences, Volume 57, Pages 419-425, 2012. https://doi.org/10.1016/j.sbspro.2012.09.1206
  9. P. Liskowski, W. M. Jaskowski and K. Krawiec, "Learning to Play Othello with Deep Neural Networks", in IEEE Transactions on Games, 2018
  10. R. S. Sutton, A. G. Barto, "Reinforcement Learning : An Introduction", MIT Press, Cambridge, MA, 1998.
  11. N.J. van Eck and M. van Wezel, "Reinforcement learning and its application to othello", Technical Report EI 2005-47, Econometric Institute Report, 2005.
  12. M. van der Ree and M. Wiering, "Reinforcement learning in the game of Othello: Learning against a fixed opponent and learning from self-play", 2013 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning (ADPRL), Singapore, pp. 108-115, 2013.
  13. J. P. Fishburn, "Appendix A: Some Optimizations of ${\alpha}-{\beta}$ Search", Analysis of Speedup in Distributed Algorithms, UMI Research Press, pp. 107-111, 1984.
  14. S. H. Lee, D. Y. Kim, and Y. W. Cho, "Image Recognition based on Deep Learning Using Multi-Dimensional Neural Network and Decision Making Neural Network", Journal of Korean Institute of Intelligent Systems, vol. 28, no. 1, pp. 34-40, 2018. https://doi.org/10.5391/JKIIS.2018.28.1.34