SapioGo

A Go client using Neural Networks and the SANE Genetic Algorithm.

Ryan Flannery `ryan.flannery@gmail.com` http://www.ryanflannery.org	Kevin Upchurch `upchurks@email.uc.edu` http://kevinup.wordpress.com/
Advisor: Professor John Schlipf `john.schlipf@uc.edu` http://cs.uc.edu/~schlipf

SapioGo was the 2004 computer science senior design project of Ryan Flannery and Kevin Upchurch, under the guidence of John Schlipf. The goal of SapioGo was to create an artificially intelligent Go game client that was capable of playing Go competently against novice human players.

Useful Links about Go

History of Go

Playing Go

Computer Go

Project Documentation and Downloads

Documentation

(dvi) (ps) (pdf) Requirements Document
(dvi) (ps) (pdf) Time Line
(dvi) (ps) (pdf) Design Document Not yet finished.
(dvi) (ps) (pdf) Analysis Document Not yet finished.
(dvi) (ps) (pdf) User Manual
(dvi) (ps) (pdf) All-inclusive Final Document
(zip) (gzip'd tarball) LaTeX sources for all documents

Other Downloads

SapioGo Source Code
- (zip) (gzip'd tarball) GTP & GMP library
- (zip) (gzip'd tarball) Neural Network library
- (gzip'd tarball) SANE-Network library
- (zip) (gzip'd tarball) SapioGo
(zip) (gzip'd tarball) SapioGo Documentation
(zip) (gzip'd tarball) (website) cgoban v1.9
(website) gnugo

Project Log

:: 26 June 2004 :: Kevin got married today! Congratulations to he and his new wife!

:: 10 June 2004 :: SapioGo wins best Computer Science Senior Design project for 2004!
Tonight was the Electrical and Computer Engineering and Computer Science awards banquet for all 2004 graduates. We were honored with the award for this years best senior design project! Even better...the banquet had free beer!

Providing the award is Professor Karen Davis. That's Ryan on the Left and Kevin on the right Below is a picture of everyone who helped contribute to the project, minus Professor Schlipf.

From left to right: Meghan Murphy, Ryan Flannery, Carrie Lucken, and Kevin Upchurch

:: 09 June 2004 :: SapioGo is complete! Well, at least for now! The quarter has come to and end, and with it so has our (Kevin and Ryan's) undergraduate studies at UC. The official project of SapioGo, as our senior design project, is thus complete. I'll try to post finalized source code, documents, and generations within the next couple of days.
We both had an absolute blast working on this project and plan to continue it through at least summer quarter. After talking with Professor Schlipf, we have some good ideas on how to tweak SANE that may help improve the learning curve.

:: 02 June 2004 :: Today, everyone in Electrical & Computer Engineering and Computer Science at UC who participated in a senior design project hosted a four-hour long presentation in Rhodes Hall.
OK, OK, so our presentation was slightly lacking. Ryan forgot the Go board and although we had a poster-board, we had nothing on it. Kevin made up for it with Oreo's and pop.

Left: That's Kevin on the left and Ryan on the right. Right: a close-up of our awesome presentation table!

:: 15 May 2004 :: Today, we are meeting to try and put together a rough draft of our final paper as well as review some of the progress SapioGo has made (it's still learning!) Some of the generations we have completed have been posted: generations/

:: 05 May 2004 :: Much has happened since the last few updates. First, we have forced ourselves to "finish" implementation. That is, we are forcing ourselves to stop making improvements! We wish we had more time to devote to this project, but we must wrap everything up in the next couple of weeks. This includes at least two weeks worth of solid learning, preparing a great deal of documentation, and a presentation. We may (and most likely will) continue with this project, but for now, there will be no more source/design changes. We should have the code up for download shortly.

:: 27 April 2004 :: It's running! It's running! It's running AND it's learning! Well, we will see how well it learns after it finishes five generations. The first generation just completed (after running for just over two and a half hours) and you can download the saved neural network here. We also have a beta version of our code that you can download above, in the Downloads section, the SapioGo (full) download.

:: 25 April 2004 :: :: 24 April 2004 :: :: 23 April 2004 :: For the past three days, we have met for at least eight hours each day, and have accomplished much! The implementation is nearing completion and we are determined not to leave the LaRC office at UC until we have a working, learning Go program! Once everything is *near* completed, we'll post the source tarballs to this website. We have broken the code base into four separate branches: (1) an independent library for the Neural Network, (2) an independent library for the SANE Neural Network, (3) an independent library for the GTP interface, and (4) the source code for the main Go program that uses the previous 3 libraries.

:: 21 April 2004 :: We met with Professor Schlipf today and discussed the progress with our implementation. Since we switched to using GTP instead of GMP, our progress has slowed slightly. We now, however, have GTP well understood and are close to finishing our game-shell code. Our game shell library has evolved into a generalized library that can be used to quickly and easily implement a Go game in C++. Also, our weekly Senior Design class was canceled for today, so we spent the time (and an additional few hours) working on our code. The SANE algorithm extension of the Neural Network library is also almost complete. We are now focusing on merging the two codes.

:: 15 April 2004 :: We discovered that GNU Go implements the GTP protocol and that you can even use GNU Go to act as a middle-man between two other games playing Go. The standard GNU Go distribution even contains sample code on how to use GNU Go as such a middle-man, and how to implement GTP using GNU Go!

:: 14 April 2004 :: After working extensively with the GMP library, we discovered that much of the implementation is incomplete. Worse, even some of what is implemented is incorrect. As a result, we have decided to abandon the GMP protocol library in favor of an alternative. Currently, we are researching GTP (the Go Text Protocol), whose design is significantly more mature. Unfortunately, the GTP protocol has yet to be finalized, so finding existing implementations is hard. We hope this change will retard our progress too much (hopefully no more than one week.)

:: 10 April 2004 :: Today we worked extensively on the Neural Network library and the SANE extension. Specifically, we stress tested the neural network library for board sizes of 19. With that, the neural network has an input layer of roughly 2 * (19 * 19), an output layer of size 19 * 19, and a hidden layer of size 10,000...and it's still able to make one iteration in just over a single second! As such, a 19x19 board is definitely feasible (although we will still work exclusively with a 9x9 for the purpose of this project.)

:: 07 April 2004 :: Today, we met after our Senior Design Project class to discuss some difficulties Kevin encountered with the GMP library we are using. After some brain-wracking, Kevin solved the problem and we are one stop closer to nearing completion of the game "shell" code. Next, we need to focus on incorporating the two code bases together and hope they play well together.

:: 20 March 2004 :: Yesterday marked the beginning of our Spring break at school, and we met to discuss what we plan to get accomplished during the break. We plan to have the actual implementation of the neural network library, with the SANE layer included, as well as the game shell completed by the start of next quarter (29 March 2004).

:: 12 March 2004 :: We met today with Professor Schlipf for our weekly meeting. We discussed numerous implementation issues, especially the Neural-Network and SANE object-hierarchy's, as well as the game structure as a whole.
We also discussed how we plan to make our project different from other projects that have modeled Go using SANE. Most of our discussion focused on adding/removing/changing the inputs from the board to the Neural Network, such as including the number of moves made so-far, the number of stones on the board (total, and per-player), as well as including the distance from the edge of the board for each intersection on the board. We briefly discussed modifying the SANE algorithm itself in some particular aspects to make it model a more human construction.
Next week, we both have multiple exams and do not expect to make much progress. We aren't even sure if we will meet with Professor Schlipf next week. After examinations finish, however, we hope to get the majority of our implementation completed during spring break.

:: 10 March 2004 :: We met today at UC before our evening classes to discuss implementing more of our project. We decided the following: Kevin will work on implementing the general game structure (specifically the GMP, Go Modem Protocol, library) and Ryan will work on the Neural-Network implementation, with support for the SANE structure (although SANE will not actually be implemented yet). After that, we will merge our code and begin work on SANE.

:: 05 March 2004 :: We met again with Professor Schlipf today for a weekly meeting. We nailed down the structure of our neural network as well as the design of SANE. After reading Professor David Moriarty's paper where SANE is first introduced and explained, we feel much more confident about how it works. We even discussed, briefly, some of the approaches for implementing this. We're ready to begin some proof-of-concept implementation and hope to have something by the next meeting (note that we're leaving "something" vague, so as not to disappoint anybody!)

:: 01 March 2004 :: We met with Professor Schlipf today for our weekly meeting. We were supposed to meet last Friday, 27 February, but Professor Schlipf had to postpone the meeting until today. We presented the SANE algorithm and discussed how to structure a Go game so that we could use SANE to model it. Professor Schlipf pointed out a number of areas where we still need to further research how SANE works, namely, how it evolves neurons and breeds blueprints. We especially need to further design the general structure of our neural network, such as what our inputs are and how they are interpreted, what our outputs are and how they are interpreted, and how to evaluate the output based on the input for each iteration of the neurons firing.

:: 24 February 2004 :: We both met today to further discuss the SANE (Symbiotic Adaptive Neuro-Evolution) genetic algorithm to evolve the weights and bias in neural networks. It was decided that we should focus on creating some proof-of-concept code implementing SANE before a final decision is made.

:: 20 February 2004 :: Met with Professor Schlipf today for our weekly meeting and briefly explained all that we had learned concerning neural networks and genetic algorithms. Our research period is over, and we are now trying to tackle the design and structure of our neural network. Further, we still need to research how to apply a genetic algorithm to evolve the structure, weights, and bias in our neural network. From the research we've done so far, it seems that the SANE (Symbiotic Adaptive Neuro-Evolution) algorithm has been used extensively, and very successfully, with go.

:: 18 February 2004 :: Met briefly during our lunch breaks to discuss what other trivial parts of the project we could begin implementing. It always feels good to at least have some actual program up-and-running...even if it's nowhere near complete.

:: 13 February 2004 :: Met with Professor Schlipf today for our weekly meeting and really started to discuss some of the finer details of neural networks and genetic algorithms. We definitely need to do more research in both areas to get a better of understanding of how we can apply these methods to a game of go.

:: 08 February 2004 :: We both met briefly to review some of the various approaches used to model Go and what kind of success the various methods have had in the past.

:: 07 February 2004 :: Kevin read up on genetic algorithms based on the books that he had gotten from the library. Found lots of good information on implementations of genetic algorithms in various problems, but was not able to find a clear connection as to how to apply a genetic algorithm to GO.

:: 06 February 2004 :: After spending the past two weeks reading about various types of neural networks and their implementation, Ryan presented the subject of neural networks, the logic behind them, various implementations, and what kinds of neural network approaches have been used in the past when dealing with Computer Go.

:: 30 January 2004 :: Met with Professor Schlipf today, but only briefly, as all of us had other pressing engagements. We handed in a rough draft of our requirements document and briefly updated Professor Schlipf on our progress. After Professor Schlipf reviews our requirements document and returns it to us, we will make our revisions and then submit our first official piece of documentation for the project.

:: 23 January 2004 :: We met with Professor Schlipf today and began to put together our requirements document. We already have most of our requirements specified, we simply have to formalize them into a document (something the both of us would rather not take the time to do). We plan to have the requirements document completed next week, as well as devoting more time into researching other endeavors made to model go on a computer.

:: 21 January 2004 :: Kevin went to the Cincinnati public library and rented numerous books on the subjects of neural networks, genetic algorithms, heuristic algorithms, and anything he could find that dealt with Computer Go. We have decided to split up the subject material: Kevin will take genetic algorithms and Ryan will take neural networks. After a week, we will each switch books and research the other subject. As of right now, it looks as if we will be using a mix of neural networks and genetic algorithms establish a program that will learn.

:: 20 January 2004 :: We put together a simple Go game shell that uses the Go Modem Protocol (GMP) library to communicate a Go game via TCP. We then put together a simple go demo, available for download above, that runs against localhost and uses GMP to connect to a client, namely cgoban v1.9 (also available for download above), and play a game. The test client simply makes random moves.

:: 16 January 2004 :: Met with Professor Schlipf today for our second weekly meeting and, after we spent the past week researching other work in this field, we laid down a preliminary time line for our project. We then spent some time discussing the requirements for our project, including what methods we would be using to achieve an intelligent system, what kinds of go (rule-sets, time-systems, etc.) our client would be capable of playing, and some more practical matters, such as what language our project would be written in and what operating system our project would run on.

:: 09 January 2004 :: We met for the first time this quarter with Professor Schlipf today and he explained the basics of a senior design project, including what kind of documentation is expected and when. We spent a great deal of time identifying what other professors here at UC have appropriate research experience to be a real asset to the project and wether-or-not they would be available sometime within the next six months to help with the project.