Neural Networks and Go

Neural networks (or NNs) are an artificial intelligence technology inspired by the workings of organic brains. They have been found particularly suited to pattern matching and evaluation and have been used to create go-playing systems (AlphaGo) of superhuman ability.

Table of contents Sketch of the principles of neural networks Go-playing neural networks Discussion Links to related Papers Comments on papers

Sketch of the principles of neural networks

Neural networks consist of many small components (“neurons”) which receive and transmit signals according to rules with adjustable parameters. In a typical application, some neurons are fed with input to be processed, these send signals via intermediate (“hidden”) neurons to a set of output neurons which produce a result for use outside the network.

For go, one could have as input a position on the board and as output an estimate of the prospective scores or a proposal for one or more moves for consideration.

By adjusting the parameters based on the quality of the output, networks can be “trained” to produce better results. This requires a way of evaluating the results.

For go, this could be how well the estimated score or suggested move match opinions of professional players; this is the way AlphaGo Master was trained.

A more ambitious way of evaluating the result is simply to let a system using the network play another version of itself and see how well it scores; this is the approach of AlphaGo Zero.

Go-playing neural networks

Neural networks (NNs) have been successfully implemented for dan-level programs (notably Hira, Dark Forest, Zen, and AlphaGo) since 2015.

Zen reached KGS 7d in early 2016 after implementing DCNN. http://computer-go.org/pipermail/computer-go/2016-January/008541.html

Discussion

Does someone know if neural networks have been used with Go ?

AGiss: (By "neural networks", I mean the computer's tool to solve problems, that has merely nothing to do with the things within everybody's brain!) While neural networks can be a big failure with Go, we can't know if NNs are well suited to Go or not unless we try it.

Ybac? It seems AlphaGo just demonstrated that NNs work.

As I think I'm not a genius or even someone who has good ideas before others, I think some other people have already tried to use that concept. But I have no reference of such research. Does someone has a clue or URL ?

My idea would be to use the 19x19 intersections as 19x19 input (values 1, 0, -1) and 19x19 outputs (that's huge) values -1 or 1 for (bad move or illegal move) / (good move)

A good move is a move that at pro has already done on the board.

I don't have a big pro database to try such a project!

That would take a lot of time/CPU/memory to make that, but if it really works, that would make an incredibly fast Go program. -- AGiss

WinHonte: from the Jellyfish people uses neural networks in part of the game engine. As I understand it they haven't tried to teach one big neural network to play the game as described above. Rather, they have a conventional architecture for a Go-playing program, except that where most programs have a hand-made database of patterns for suggesting local moves, WinHonte uses a neural net trained from professional games.

Kungfu (3k* IGS):

I have some questions and comments about this. First of all, from what that cached page says, the NeuroGo program was a *success*. It seems that after 4500 games against itself, it was able to beat Manyfaces at a reasonably strong playing level. So the failures of NeuroGo have really only been attributed to the computational resources available to it and not (like the other programs) entirely on the expert knowledge they have hardwired into them.

1. What are the resources required to play at the 5 dan amateur level on a 9x9 board?

2. Are the computational resources necessary to play as 1 dan on a 19x19 board greater or lesser than those required for a Many Faces / GNU Go style program?

gonzo: Part of the problem is that neither GNU Go nor Many Faces can play at a 1 dan amateur level. Many Faces claims to be able to play around 8 kyu at its strongest level. If anything can play at a 1 dan level with reasonable (polynomial) resources, I am sure someone would come up with the computing power!

3. What is the limit of strength for a given network "size"?

4. More web resources on this!!

Comment: It then seems obvious from what we know of computer Go that a hybrid approach needs to be used. A large if not complete database of things like shapes, joseki, whatever, needs to be connected to such a neural network.

Experiments should be done! If it needs one day to come up with a pro or high level amateur move using distributed computing, then so be it. Let's do it. At least we'll only be a few hundred years behind the times of the human players ;)

Links to related Papers

kierancommanda: Move Evaluation In Go Using Deep Convolutional Neural Networks

SAS: There's an article called The Integration of A Priori Knowledge into a Go Playing Neural Network. (Also available here. There's also a PostScript version.)

SAS: Another paper on the subject is Co-Evolving a Go-Playing Neural Network.

Note: Link did not work for me. You can find the full paper here

Comments on papers

ilan: In my opinion these papers exactly show the weakness of the neural network approach. They tackle the classical artificial intelligence questions (the ones based on making machines do difficult things that people usually consider a representation of "intelligence") instead of following the scientific approach of first solving simple and well understood questions. In particular, a good first problem for a neural network would be to solve integer arithmetic (addition and multiplication). Note that this is in fact necessary to play go (you need to know how to count and how to add to play go)! Of course, the reason for all of this is that you don't get grants or promotions if you study addition and multiplication because these don't require "intelligence".

Bildstein: Firstly, I think there is a fundamental difference between arithmetic and go. The first is a solvable problem, while the second is almost certainly not. We don't need a neural network to do arithmetic, because we can write a program to do it. On the other hand, you may have a point about biting off more than we can chew when we try to use neural networks to solve go. I know I did.

Second, in my opinion, the primary obstacle to the neural network approach to go is that it tends not to take into account the symmetry of the game. How rediculous is it to think that you could train a neural network to solve a tsumego problem in one corner of the board, but when faced with the same problem in a different corner, or with colours reversed, or mirrored along the diagonal, it gets it wrong. They've done okay with neural networks on 7x7 boards, but in my opinion, these solutions are simply not scalable. In fact, I'm not aware of any applications of neural networks that have anywhere near the number of inputs you'd need if you wanted to scale these solutions up to 19x19.

Trontonic: How would using MoGo for training a neural network work out? Pro games are probably good allright, but they contain few responses to "stupid" moves. This could even be a distributed project, for increased CPU per move.

Harleqin: I think that the application of neural nets to go has a fundamental problem in how to represent the game state, i.e. how to feed the game until now into the net's input layer. The simple idea of giving a matrix the size of the board where own stones are marked as 1, opponent's stones as 0, and empty intersections as 1/2, is flawed because cycles cannot be detected (this would mean that it cannot play ko!). Marking ko bans with a special value is also difficult because the net would need to specially process the input in a way that has a high learning barrier since ko are not frequent enough. There would also be no way for the net to detect longer cycles. So, basically, you have to feed all the moves until now into the input layer, but how? One idea would be to sequentially fire the board states or moves from the start into the input layer, and rely on the net having some memory (i.e. backpropagation) to synthesize this into a working game state. However, this introduces new problems: how to tell that the net has completed its calculation, and how to apply a learning algorithm. I think that this means that a neural net suitable for go has to be magnitudes more complex than the currently published neural net applications.

Bamboomy The problem of 'remembering' past moves could get solved by differentiating the input. In stead of using 'bare' values as 1, 0 and 1/2 you could differentiate the input. For example: if an own stone is removed you could change the value from 1 to 3/4 in stead of 1/2 and let the network learn how to deal with this kind of differentiation. This should at least solve the 'ko' problem. Longer cycles would get more difficult to deal with because of their subtlety but at least the input wouldn't be the exact same. The memory wouldn't be in the network but in the input. On a related note I think a network should have (much) more middle layers. My original design was a network that was as 'deep' as the size of the board but with the nodes only connected to their nearest neighbors. The rationale behind that design was that all of the information that is feeded to the input layer eventually ends up in the output layer. Does anyone has some working java code for this problem? I'd like to spent quite some computer time (both coding as cpu) on this... (spam3_at_bamboomy_dot_tk (with the 3, and the _at_ and _dot_ changed into @ and .)).

TestPlay09: hi, what about a neural network of neural networks? each net would be specialized for one type of processing and data crunching, giving formatted output on the input of master net.. not only that, why not make a difference engine out of several master nets each specialized in one type of style.. maybe even make nets dynamic in terms of mutable and evolving and have some process if not another net in charge of that! everything proposed here thus far just seems to me insultingly plain and simple. making an decision based on situation at hand and previous experience is a much more complicated process. thanks for the inspiration though.. definitely will try to implement some form of my idea on small scale.. at first that is :D

TestPlay09: read some more... intelligence is a bi#%h to reproduce =_= however, it will be done!

MrMormon: Harleqin's referring to recurrent neural networks, which include their output in the input of the next thinking step. It's easy to tell when a calculation is complete: 'still thinking' could be a move choice. And they have learning algorithms. However, I'm unsure whether they can learn general superko from a realistic number of games (possibly with itself).

Lukas?: If you use MoGo to train the network, the quality of the network will never become better than MoGo. The only way to train it to become better than anything else, is to let it train against itself using some sort of genetic algorithm.

Shain?: It would be very wise to train it against something like MoGo in the early generations. Once it is trained to 15k-20k it can start training against its brethren(?) and with selective mutation a stronger NN will emerge. One could also use goproblems to train NN and simply apply an algorithm which feeds in a single problem multiple times with every variation of rotation/mirroring/color swap, that way a NN capable of solving a problem will do this all the times, not just in that one corner.