418project

This project is maintained by diwangcmu

Go AI

Project for 15-418 Fall 2017, by Di Wang (diw2) and Bo Gao (bgao).

Final Report

Final report The following is the proposal and the checkpoint report.

Instructions:

For sequential life-and-death problem:

$ cd ld_src

$ g++ -std=c++11 -O2 readfile.cpp -o seq -lm

$ ./seq -s test.txt

For parallel life-and-death problem (need CUDA):

$ cd ld_src

uncomment line 87 in readfile.cpp

comment line 87 in readfile.cpp

$ make

$ ./cudaSearch -s test.txt

For sequential full board AI:

$ cd ai_src

$ make

$ ./cudago

For parallel full board AI (need CUDA):

$ cd ai_src

uncomment line 31 in go_Decision.cpp

comment line 32 in go_Decision.cpp

$ make

$ ./cudago

Summary

We are going to implement a Go AI using tree search algorithm on CUDA in the GHC clusters, and report a detailed performance analysis with respect to different factors including board size, CUDA block size, memory access frequency.

Background

Go: Go is an abstract strategy board-game for two players, in which the aim is to surround more territory than the opponent. Our interactive application is the artificial intelligence creating a computer program that plays the game with users.

Alpha-beta pruning: The idea for tree search is Alpha-beta pruning which is an adversarial search algorithm used commonly for machine playing of two-player games. It is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.

Benson’s algorithm: In the game Go, Benson’s algorithm (named after David B. Benson) can be used to determine the stones which are safe from capture no matter how many turns in a row the opposing player gets, i.e. unconditionally alive.

Challenge

First of all, the workload of this problem is too large for not only there are a huge number of possible points to make a current move, but even more potential conditions on the following sequence of moves. It’s really hard to achieve considerable speedup on such large problem size.

Additionally, we cannot use tree search alone for the best decision of each move, because of the great number of possibilities that makes exhausting every one of them impossible. Therefore we have to incorporate the use of expert knowledge for a more clever searching algorithm. The task to take these heuristics, formalize them into computer code, and utilize pattern matching algorithms to recognize these general rules is challenging to implement.

Resources

The resources we use are basically GHC cluster computers, and we will start from scratch. Also, we will reference to Monte-Carlo Go Developments (B. Bouzy and B. Helmstetter), a paper that explores an intermediate approach in which a Go program performs a global search using very little knowledge.

We also need to find resources on detailed pattern matching algorithms as well as specific implementations, but are still in search of those.

Goals and Deliverables

The first thing that we plan to achieve is a full UI of Go that is able to interact with the user. The application should follow the general rules of Go.

And we also plan to achieve a life and death problem solver for Go. This solver should provide the correct sequence of moves to the problem, and can respond to any user’s incorrect moves. This requires the solver to know in advance which is the optimal sequence of moves given the current board state, which closely resembles that in an actual Go game.

We hope to achieve a competitive Go AI that can beat amateur players. The AI should be able to do the basics achievable to any human player, to evaluate which player is in an advantage given any board state, and to what extent. It can also project if a piece is dead or alive.

The demo we plan to show is a graphical, interactive interface. It has two modes, one as the life and death problem solver, and the other as a Go playing program which can play reasonably with the user.

We will analyze on whether parallelism helps in the search algorithm, and if so, to what extent. We would also analyze the importance of granularity in the parallel algorithm. Also, we are curious if correctness will be affected when the factors of the parallel algorithm change, including the block size and thread number.

Platform choice:

We decide to use CUDA as the platform for our main algorithm. This means that we are using the Shared Address Space model, which has many benefits over Message Passing and Data Parallel.

Our model will not need to have communications between the threads, because the decision for the best move only depends on the current board state, but not the sequence of moves that reaches it. Therefore making any form of communication between threads would only incur unnecessary overhead.

Also, data parallelism is not necessary because there is really no data that we can parallelize on.

Our idea right now is to dynamically make the threads proceed with a work queue of the different possibilities. The system would still perform the calculations even when the next move by the player is yet to be placed. When the move is finalized, we intend to make all the invalid possibilities (i.e. board states that could no longer happen) disappear.

Schedule

Week 1:

Week 2:

Week 3:

Week 4:

Checkpoint Report

The work done so far: We successfully implemented the Go UI, along with the capture rules and ending rules. The UI in Java prompts up a yellow board, and allows the users to place black and white stones in order. If a move is prohibited then the user cannot place the move, but can still place a valid move afterwards.

In terms of the life and death problem AI, we first debated on the model and algorithm behind the AI. Originally we decided on using Cuda and Alpha-Beta pruning, but then found that it is very hard to share messages between Cuda threads.

One approach is to declare shared memory arrays in a Cuda block, which we started to implement. We also borrowed an idea from a previous project, which is to first run one branch of Alpha-Beta pruning sequentially, and then use the pruning results to run the rest in parallel. However, the bottleneck to this approach is that it is hard to find a useful and accurate heuristic for Go. Some small changes in the board state in one area can affect the entire balance of the board. Therefore the Alpha-Beta pruning returned very poor results. We decided to not go along that approach.

After the unsatisfactory results with Alpha-Beta tree, we decided to implement a simple Tree search in parallel. We still used Cuda, but this time the threads are divided with respect to the combination of the first two possible moves given the current board state (e.g. black places at (3,3), and white places at (3,4)). Then the search will continue until we reached the ending stages.

Here are some screenshots of the AI’s decision of whether a piece is alive or dead: Black dead Black unknown Black dead 2 Black unknown 2

Goals and Deliverables: We believe that our original goal of implementing an interactive tsumego (life and death problem) AI is achievable. However, the full Go game interactive AI might be a stretch. It is hard to exhaust every possibility, since there are around 3^(19*19) possibilities, resulting from each point on the board being either unoccupied, black or white. Also, we found that it is hard to implement a parallel tree search algorithm given a full game board. Therefore pattern matching is required to reduce the possibilities to search for, but we have not started on that. Therefore this becomes a “nice to have”. The revised list of goals is as follows:

Poster Session: We plan to show the above interactive game demos at the poster session.

Schedule for coming weeks: