Teach a Computer to Play Board Game

Abstract

This project is based on General Game Playing project. General game players are computer systems able to play strategy games based solely on formal game descriptions supplied at "runtime". They don't know what the game they play until the game starts. Unlike specialized game player, general game players cannot rely on algorithms designed for specific games; they must discover such algorithms themselves. General game playing expertise depends on intelligence on the part of the game player (i.e. artificial intelligence) and not just intelligence of the programmer of the game player. Each game takes place in an environment with finitely many states, with one distinguished initial state and one or more terminal states. They link together in tree structure. To solve this problem, we have to write a player with good tree search skill. There are two basic approach of GGP exist today, one is knowledge-based and the other one is knowledge-free approach. The former use an approach called MiniMax to derive knowledge about the game that can be used for evaluation. The latter consider the game like a black box for generating legal moves and successor state of the game. In this project, we try to improve the knowledge-free approach, Monte Carlo Tree Search, by adding knowledge analysis.