Shogi Rodin Thinker Amazons

Grimbergen Cognitive Science and Games Laboratory

Tokyo University of Technology, School of Computer Science

Room: Research Tower A-0806 and A-0811
Tel: +81-42-637-2591 (Extension: 2591)
E-mail:How to reach me

Research Outline

The main objective of the research in this lab is the programming of human problem solving. At the moment, we are using the games Shogi (Japanese chess), Go, Mahjong, Amazons and Clobber as application domains. The shogi program SPEAR is participating every year in the CSA World Computer Shogi Championships. Amazons is a relatively new game, but is often used for game programming research. The research using Go, Mahjong and Clobber is still in its initial stage, but each of these games is well-suited for modelling aspects of human thinking.

The reasons for using games are the following.

Research topics

  1. Analysis of the thinking processes of human game players

    Kasparov Thinking

    What are humans thinking when they are playing games or solving puzzles? The answer to this lies in analyzing and programming the cognitive processes of game players. Specifically, the research in this lab uses Marvin Minsky's Society of Mind theory as the foundation of our modelling programs. Minsky's theory has only been partially implemented because of the complexity of many application domains, but I feel that it is possible to make a full implementation of the different aspects of the theory in a limited domain like games. We are currently in the process of making a full implementation of Minsky's theory in shogi.

    Also, as graduation thesis research, we have been analyzing the thinking processes of people solving puzzles like Sudoku.

  2. Development of a shogi program to beat the best human players


    The shogi program SPEAR, which is developed at our lab, currently has a playing strength of about 4-dan amateur. SPEAR participates every year in the CSA World Computer Shogi Championships, finishing with 5 wins and 4 losses (12th place among 42 participants) in the latest tournament which was played in May, 2009. The aim of this research is to further improve SPEAR to beat the best human shogi players.

    To achieve this, search, evaluation and learning are vital.

    SPEAR is available online. If you want to give it a try, please download it from the SPEAR webpage. It is not a stand-alone application, but runs under a special user interface called Shogidokoro. If you have problems getting SPEAR to work under Shogidokoro, please contact me.

  3. Improving the search in Amazons

    TAS Medals

    The strength of game programs is largely determined by how far the program is able to look ahead. This search depth is closely related to the number of possible moves that can be played in a position on average, because most game programs look at all moves in a position. In shogi the average number of legal moves in a position is about 80, but in Amazons this is more than 400 (actually, there are more than 2000 possible moves in the starting position of a game of Amazons!). Therefore, doing deep search is much more difficult in Amazons than in most other games. We are using Amazons to investigate methods to improve the efficiency of search algorithms.

    A master student in our lab has made an Amazons program that has participated three times in the Computer Olympiad. In 2004 it won the silver medal in the Amazons tournament played at the Olympiad in Israel and in 2005 it won a bronze medal in the tournament held in Taiwan. One of the aims of our research is to further improve the program and participate in the Computer Olympiad again.

  4. Development of a strong Clobber program


    Clobber is a combinatorial game, which makes it a little bit different from games like shogi and Amazons. The most important feature of a combinatorial game is that it splits up in a number of different subgames as the game progresses. It is possible to win these subgames separately, but lose the game as a whole. Investigating the relation between local subgames and the overall outcome of the game is the topic of ongoing research at our lab.

    Clobber is also one of the games at the Computer Olympiad, so another goal is to improve the Clobber program that has been developed at our lab and participate with this program in a future Olympiad.

  5. Development of a Go program


    In our research lab we don't have a Go program yet. In Go, it is very hard for the computer to evaluate positions. Also, the average number of moves in a Go position may be smaller than in Amazons, but much larger than in shogi (about 250). Therefore, it is difficult to make a strong Go program based on search and evaluation. To avoid these problems, Monte Carlo search, which doesn't need to evaluate positions, has become a very popular search method. With this method, it is possible to make Go programs that are quite strong. The focus of future Go research in our lab is not limited to Monte Carlo search, but we are aiming to start the development of a Go program sooner rather than later.

  6. Development of a Mahjong program


    In the case of Mahjong, it is unknown exactly what the opponent is holding, so this is an imperfect information game and different from the games above. How to use probabilities to decide the best move is the problem in Mahjong.

    As a graduation research theme, the open source Mahjong program Maujan was used to compare attacking play with defensive play. However, we have not developed our own Mahjong program yet, which is one of our aims.

  7. Research into video game AI

    All the games above are classic board games, but there is also a lot of interesting research regarding video games. I am especially interested in how to make the behavior of NPCs (Non-Player Characters) more human-like. This research is not even in the planning stages yet, so this is a long-term goal, but it might become a priority when I can find some good students interested in this work.