GO AI AI controller for the game of GO (current project)

After learning how to play GO, I had an idea: "What if this was played on a multidimensional grid?" I researched the topic with no success. My research continued and upon discovering computer GO is a relatively undeveloped area due to its difficult nature, I had to give it a go.

What is GO?

GO (NOT to be confused with the programming language) is a two player strategy game. It is the oldest known game. Some estimates are as old as 4,000 years, others around ~2,500 years or more. It certainly predates the birth of Christ. In the east, it is so popular, countries such as Japan have twenty-four hour TV channels dedicated to it.

What are the rules?

Despite GO's few simple rules, I will not explain them here.
Instead, I will state a few facts to help the reader get an idea of what the game involves:
• The board is 19x19.
• Moves are made on intersections of the grid.
• Black moves first(unless white has been handicapped).
• Moves can be on any empty intersection (unless Ko, or Suicide).
• Empty adjacent intersections next to a stone or connected stones are referred to as liberties.
• When a stone (or stones) run out of liberties (the liberties are occupied by stones of the opposite colour) they die.
• Dead stones are removed from the board and become the opposite colour's prisoners.
• The game ends by one player resigning or both players agreeing it's time to end the game and check the score.
• The objective of the game is to obtain more territory (empty surrounded intersections) than your opponent.

Below is a full game between two professionals:
(;GM[1]FF[4]SZ[19]PW[roln111]WR[8d]PB[xuyin]BR[6d]DT[2015-05-31]PC[The KGS Go Server at http://www.gokgs.com/]KM[0.50]RE[W+0.50]RU[Japanese]OT[5x10 byo-yomi]CA[UTF-8]ST[2]AP[CGoban:3]TM[0]HA[2]AB[pd][dp];W[cd];B[ed];W[gc];B[cc];W[cg];B[pp];W[nc];B[kd];W[qf];B[nd];W[md];B[ne];W[oc];B[pc];W[me];B[pf];W[pg];B[qe];W[of];B[pe];W[nf];B[mf];W[ke];B[mg];W[lf];B[lg];W[je];B[oh];W[og];B[pi];W[rf];B[re];W[qi];B[qj];W[qh];B[pj];W[nh];B[mi];W[rj];B[rk];W[si];B[rh];W[rg];B[ph];W[ni];B[ng];W[mj];B[li];W[ql];B[qk];W[rl];B[sk];W[ok];B[oe];W[qg];B[sf];W[qn];B[qo];W[oo];B[po];W[pn];B[op];W[no];B[np];W[mp];B[mq];W[lq];B[mo];W[lp];B[mn];W[nm];B[mr];W[lr];B[mm];W[lj];B[ji];W[jj];B[nl];W[om];B[jn];W[or];B[pr];W[qq];B[qr];W[ns];B[nq];W[ip];B[ro];W[hn];B[il];W[ii];B[ki];W[kj];B[sg];W[kl];B[in];W[kn];B[ko];W[jm];B[jp];W[jq];B[lo];W[im];B[iq];W[hq];B[kq];W[ir];B[kr];W[cn];B[bo];W[bn];B[co];W[en];B[er];W[bc];B[ih];W[hh];B[hi];W[ij];B[hd];W[gd];B[hg];W[gh];B[gg];W[fh];B[he];W[hc];B[ce];W[dd];B[de];W[be];B[dc];W[bd];B[id];W[fg];B[ic];W[ig];B[ge];W[ec];B[jh];W[kc];B[kb];W[jd];B[lb];W[kg];B[jg];W[ld];B[fc];W[eb];B[fd];W[fb];B[ib];W[gb];B[ee];W[ff];B[fe];W[mc];B[dg];W[dh];B[jc];W[lc];B[ch];W[cf];B[nk];W[nj];B[eh];W[di];B[eg];W[ei];B[eo];W[dn];B[an];W[am];B[ao];W[bm];B[fo];W[ho];B[jo];W[pb];B[qb];W[mh];B[lh];W[if];B[ja];W[ob];B[jf];W[ie];B[mb];W[ml];B[ri];W[kf];B[rn];W[fq];B[fr];W[eq];B[dq];W[gr];B[gp];W[gq];B[fn];W[fm];B[cr];W[jr];B[ks];W[qa];B[rb];W[ha];B[hb];W[ga];B[ia];W[lm];B[hp];W[io];B[pl];W[ol];B[qm];W[rm];B[pk];W[pm];B[nn];W[on];B[sm];W[oj];B[sl];W[qm];B[js];W[ln];B[kp];W[is];B[ls];W[gn];B[gs];W[hs];B[fs];W[ra];B[sb];W[na];B[ma];W[nb];B[do];W[fi];B[sa];W[pa];B[];W[])

If you want to learn the rules in full, I would recommend this site. It has pleasant interactive tasks to step you through each rule in isolation.

Why is computer GO difficult?

Several distinct features of GO make it difficult to create AI for:
• More pieces as the game progresses -- As a game progresses; more stones are added. This makes the task gradually more complex.
• Unobvious game state -- at any given point during a game, it takes an expert to say who is winning. For an AI to make a similar determination is expensive and complex. See Game scoring section for papers on the subject.
• Number of games -- GO has possible games. Chess has a mere possible games.
• Large board -- games are played on 19x19 grid giving us 361 intersections. Chess is played on an 8x8 grid giving us 64 cells.
• Simple rules -- a player can make a move almost anywhere there isn't a stone already. This means there are several times more valid moves than in chess.
• Whole board awareness -- Good moves in GO consider the whole board. The game can have pieces added or removed. Therefore, as much of the board needs to be evaluated as possible for every move.
• Shapes -- when a GO AI faces a human, it has difficulty keeping up with our pattern matching skills. Certain shapes have predictable outcomes, which human players can pick out relatively easily. See Ladder, Net, Ko variants, etc
• End game -- these facts combined lead to the end game becoming a PSPACE level problem.

Current features

C++11 with OpenGL 4

OpenGL 4 is different to my previous encounters with OpenGL; many functions are officially deprecated.

Eigen

A SIMD linear algebra library (Eigen) is used to standardise all maths code and accelerate graphics. The purpose of using Eigen is not specifically for the graphics maths. It has been included in the project for use with the artificial neural networks (future task). These networks will require many maths function calls, and due to the nature of neural networks they are well suited for SIMD.

Fully functioning gameplay

Gameplay functionality has been tested by playing back over 100,000 professional games without any error or deviation (50 minutes run time with single thread, over 18 million moves played). Additionally a set of automated tests have been created, they are designed to force every branch of move making code to be visited, again no errors detected.

SGF parser

SGF is GO's file format. Due to the game's popularity, it is easy to obtain records of professional and classic games. I have amassed a database of over 173,000 games for testing. The parser features what I call "partial parsing", since the parser employs regex, it's possible (via bit field) to choose what data to pluck out of a SGF file. This allows for quick searching for games with specific criteria (e.g. won by less than 3 points).

Abstract representation

The codebase is designed to support any size board of any number of dimensions (1D, 2D, 3D, 4D, 5D etc).

Ray casting based moves

Since we have to render in 3D, being able to make moves in 3D allows us to move on any dimensional game (once it is being rendered in 3D). A move is made by casting a ray at the scene from the camera to the mouse position (projected on the near plane), when it collides with an intersection (a sphere) a move is made at that location.

Future features

Game scoring (current task)

A game of GO is scored if both players agree it's time to end the game. This only happens when a game is close. For humans this is a trivial task, for a computer algorithm this is complicated. In order to decide whose territory is whose, life and dead of stones needs to be decided. This requires problem solving; it's comparable to solving check mate problems in chess. In GO; this is called tsumego.

The following prerequisites are required to calculate the score in the end game of GO:
• Calculate if every stone is alive or dead (tsumego combined with life and dead).
• Compute each stone's influence (think of ripples on a pond, each stone radiates side effects).
• Using influence in a formula, decide if every empty intersection is territory for white or black.
• Sum the territory, prisoners and Komi to decide a clear winner (it's not possible to have a draw in GO).

This is somewhat easier said than done, below are related papers:
• Benson's algorthim: wikiPage, paper.
• Martin Muller: Recognizing Secure Territories In Computer Go, An Improved Safety Solver for Computer Go, Position Evaluation in Computer Go, publications.

AI controller

Once scoring is complete, genetic algorithms combined with neural nets will be used to create an AI controller. See below papers for further details:
Monotonic networks.
Convergence and Crossover.
Combining Genetic Algorithms and Neural Networks.
A Machine-Learning Approach to Computer Go.
Co-Evolving a Go-Playing Neural Network.
Training Feed-Forward Neural Networks with Monotonicity Requirements.

3D GO

Once 19x19 has a skilled AI controller the rendition of 3D games will be added to the project. Starting with capture GO. Next, I hope to train a 7x7x7 AI controller. Since a 19x19 board has 361 intersections, 7x7x7 is roughly the same size at 343 intersections, therefore its feasible that; if the neural network can handle 19x19, it can handle 7x7x7. Although, testing its tactical prowess (against myself) might be quite the challenge.

Below are screenshots of it in action:


The above images are debug output for region detection (the same region as referred to in Benson's algorithm).

Key:
Red squares are external region intersections that belong to black.
Red ovals / rounded shapes are internal region intersections that belong to black.
Blue squares are external region intersections that belong to white.
Blue ovals / rounded shapes are internal region intersections that belong to white.
Yellow squares are disputed regions which we are unable to conclude an owner at this time.

Below are close ups of the GO stones (these are squished spheres):