Go is an ancient two player board game that has been played for several thousand years. Despite its simple rules, the game requires players to form long-term strategic plans and also possess strong tactical skills to handle the complex fights that often occur during a game. From an artificial intelligence point of view, Go is notable as a game that has been highly resistant to all traditional game playing approaches. In contrast to other board games such as chess and checkers, top human Go players are still significantly better than any computer Go playing programs. It is believed that the strategic depth of Go will require the use of new and more powerful artificial intelligence methods than the ones successfully used to create computer players for such other games. There have been some promising new developments using new Monte Carlo-based techniques to play computer Go in recent years, and programs based on this approach are currently the strongest computer Go players in the world. However, even these programs still play at an amateur level, and they cannot compete with professional or strong amateur human players. In this thesis we explore the idea of reusing experience from previous games to identify strategically important moves for a Go board position. This is based on finding a previous game position that is highly similar to the one in the current game. The moves that were played in this previous game are then adapted to generate new moves for the current game situation. A new computer Go playing system using Monte Carlo-based Go methods was designed as a part of this thesis work, and a prototype implementation of this system was also developed. We extended this initial prototype using case based reasoning (CBR) methods to quickly identify the most strategically valuable areas of the board at the early stages of the game, based on finding similar positions in a collection of professionally played games. The last part of the thesis is an evaluation of the developed system and the results observed using our implementation. These results show that our CBR-based approach is a significant improvement over the initial prototype, and in the opening game it allows the program to quickly locate the most strategically interesting areas of the board. However, by itself our approach does not find strong tactical moves within these identified areas, and thus it is most valuable when used to provide strategic guidelines for other methods that can find tactical plays.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:ntnu-8947 |
| Date | January 2008 |
| Creators | Houeland, Tor Gunnar Høst |
| Publisher | Norges teknisk-naturvitenskapelige universitet, Institutt for datateknikk og informasjonsvitenskap, Institutt for datateknikk og informasjonsvitenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0094 seconds