Journal of the Korean Society for Computer Game (한국컴퓨터게임학회논문지)

Korean Society for Computer Game (한국컴퓨터게임학회)
권호 표지

The best move sequence in playing Tic-Tac-Toe game

삼목 게임에서의 최선의 수순

  • Choi, Young-Wook (Department of Baduk Studies, Division of Sports Science, Sehan University) ;
  • Lee, Byung-Doo (Department of Baduk Studies, Division of Sports Science, Sehan University)
  • Received : 2014.09.01
  • Accepted : 2014.09.22
  • Published : 2014.09.30
⟨ Previous Next ⟩

Abstract

The game of Go is an oriental strategic board game originated from China at least more than 2,500 years ago. The Monte-Carlo Tree Search (MCTS) algorithm in Go is a method that uses a large number of simulations to approximately estimate the winning rate of candidate moves by sampling the game. The two computer Go programs called Crazy Stone and Mogo defeated human Go professionals on the $9{\times}9$ board in 2006. Prior to our implementing MCTS into computer Go, we tried to find out the best move sequence in playing Tic-Tac-Toe game as a test bed. The experimental results revealed that the first player should play the center to ensure the highest winning rate, and the game result becomes a draw if two players do their best.

Keywords

References

  1. G. Chaslot,"Monte-Carlo Tree Search", Research Report, Netherlands Organization for Scientific Research, p. 110, 2010.
  2. S. Gelly and D. Silver,"Achieving Master Level Play in 9x9 Computer Go", Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008.
  3. Byung-Doo Lee,"Monte-Carlo Search Applied to the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol.14, No.3, pp. 47-54, 2014. https://doi.org/10.7583/JKGS.2014.14.3.47
  4. Byung-Doo Lee and Jong-Wook Park, "Applying Principal Component Analysis to Go openings", Journal of Korea Game Society, Vol.13, No.2, pp. 59-70, 2013. https://doi.org/10.7583/JKGS.2013.13.2.59
  5. Byung-Doo Lee,"Analysis of Korean, Chinese and Japanese Pro Go Player's Openings", Journal of Korean Society for Computer Game, Vol.26, No.4, pp. 17-26, 2013.
  6. Byung-Doo Lee,"Comparison of LDA and PCA for Korean Pro Go Player's Opening Recognition", Journal of Korea Game Society, Vol.13, No.4, pp. 15-24, 2013.
  7. Byung-Doo Lee,"Korean Pro Go Player's Opening Recognition Using PCA", Journal of Korean Society for Computer Game, Vol.26, No.2, pp. 228-233, 2013.
  8. Byung-Doo Lee,"Applying Neuro-fuzzy Reasoning to Go Opening Games", Journal of Korea Game Society, Vol.9, No.6, pp. 117-126, 2009.
  9. Byung-Doo Lee,"Eye Shape Analysis of Life-and-Death Problems with a Heuristic Influence Function, in the Game of Go", Journal of Korean Society for Computer Game, No.15, pp. 111-117, 2008.
  10. C. Pinaki,"Artificial Intelligence Based Strategies to Play the Tic-Tac-Toe Game", Journal of Technology and Engineering Science, Vol.1, No.1, pp. 62-69, 2009.
  11. Wikipedia,"Monte-Carlo Method", from http://Kowikipedia.org/wiki, 2014.
  12. M.H.M. Winands and Y. Brornsson, "Evaluation Function Based Monte-Carlo LOA", from http://www.ru.is/-yngvi/pdf/WinandsB09.pdf, 2014.
  13. Yahoo,"To win a tic tac toe game, what is the best first move?", from https://answers.yahoo.com/question/index?qid=20071126092114AAIyE3Y, 2014.
  14. Autodesk Inc.,"Winning tic-tac-toe Strategies", from http://www.instructables.com/id/Winning-tic-tac-toe-strategies/, 2014
  15. R. Aycock,"How to Win at Tic-Tac-Toe", from http://www.cs.jhu.edu/-jorgev/cs106/ttt.pdf, 2002.
  16. K. Hughart,"Monte Carlo Tree Search in Borad Game AI", from http://ebookbrowsee. net/kyle-hughart-monte-carlo-tree-search-in-board-game-ai-docx-d422628740, 2014.
  17. K. Constance and N. Mariko,"The Educational Value of Tic-Tac-Toe for Four- to Six-Year-Olds", from http://www.nctm.org/uploadedFiles/Lessons_and_Resources/tcm2008-05-523a.pdf, 2014.