Page 1 of 1

genetic go bot

Posted: Tue Feb 24, 2015 11:45 pm UTC
by phillip1882
so i'm trying to program a go playing ai that changes its moves slightly every time it loses.
it'd like it to start as a random player and slowly get better. i have the code for a legal game, with scoring at the end. but i'm not quite sure how to code the bot itself.
any advice would be much appreciated.
here's a general outline of what a want.
the move selection algorithm should mostly be a list of probabilities of a particular move being played. this would make it easy to merge two bots doing decent into a new bot that may do better.
the move selection algorithm should use the board state to update move probability "somehow".
my primary problem is that key word.

Re: genetic go bot

Posted: Wed Feb 25, 2015 12:10 am UTC
by Xanthir
Are you familiar with game-playing algorithms in general? The standard way to code them is as minimax algorithms, which should be easy to look up information and tutorials for. The non-trivial bit that you have to supply is the board evaluation function - given a particular board state and a particular player, how "good" is that board for that player? Using that evaluation function, you can use off-the-shelf minimax to create a game-playing bot.

So, your task is to create the evaluation function, and genetic algorithms are a neat way to do so. There area lot of possibilities, but my favorite is to train a neural network, as they're a natural way to turn a bunch of inputs into a single numeric output (the board "goodness"), and it's easy to map them to a genome in a way that has good GA features (small mutations tend to make small adjustments to the result, so you get a smooth fitness landscape) - just have the genome be the neuron weights.

Note, though, that Go is notoriously hard to make a good bot for. We're finally starting to make headway in the last few years, but if you're just starting, you might have better luck with a more easily-botted game, like checkers.

Re: genetic go bot

Posted: Sun Mar 01, 2015 3:34 pm UTC
by Lopsidation
You may enjoy TD-gammon. It's a bot that learned how to play backgammon using a neural net. It worked using an algorithm called temporal difference learning. Two-sentence summary: you have a neural net N that predicts how well you're doing so far. If N says you're doing really well on position P, but then next move it suddenly says you're losing, then you should train it by saying position P is probably bad.

No idea how well this would work for go. It would probably need LOADS of computer time to get to an acceptable playing level.

Re: genetic go bot

Posted: Thu Mar 05, 2015 11:38 pm UTC
by flownt
Xanthir wrote:The standard way to code them is as minimax algorithms, which should be easy to look up information and tutorials for. The non-trivial bit that you have to supply is the board evaluation function - given a particular board state and a particular player, how "good" is that board for that player? Using that evaluation function, you can use off-the-shelf minimax to create a game-playing bot.

So, your task is to create the evaluation function, and genetic algorithms are a neat way to do so. There area lot of possibilities, but my favorite is to train a neural network, as they're a natural way to turn a bunch of inputs into a single numeric output (the board "goodness"), and it's easy to map them to a genome in a way that has good GA features (small mutations tend to make small adjustments to the result, so you get a smooth fitness landscape) - just have the genome be the neuron weights.


This doesn't work for go because the branching factor is ridiculous. Since you have well over 300 legal moves in the beginning, leading to that as a branching factor, you are not going to exactly find the optimal move looking more than a few moves deep (I would guess about 6 would be good already)

I don't know the specifics of go bot writing, but if you want to learn about the "typical" techniques, reversi/othello, checkers and even chess are much better starting points. These games all have branching factors between 10 and 20 typically which means you can search about double as deep.

Re: genetic go bot

Posted: Fri Mar 06, 2015 10:23 pm UTC
by Mat
Another approach could be to aim for something less than winning full games (such as capture go), and then evaluate each position based on the local area instead of thinking about global strategy or reading out branches.

It'll still suck against humans, but could still be interesting if you just want to explore some algorithms. I'd be interested to see what the temporal difference learning method Lopsidation mentioned comes up with on a smaller board.

Re: genetic go bot

Posted: Thu Mar 12, 2015 7:36 pm UTC
by You, sir, name?
Yeah, I think MCTS is favored for go AIs.

Re: genetic go bot

Posted: Sun Mar 29, 2015 9:12 am UTC
by Mat
I stumbled upon an AI the other day that looks interesting: https://github.com/pasky/michi

Michi aims to be a minimalistic but full-fledged Computer Go program based on state-of-art methods (Monte Carlo Tree Search) and written in Python. Our goal is to make it easier for new people to enter the domain of Computer Go, peek under the hood of a "real" playing engine and be able to learn by hassle-free experiments - with the algorithms, add heuristics, etc.


It's based on Pachi, a competitive AI by the same authors, and they link to the thesis as an explanation of MCTS: http://pasky.or.cz/go/prace.pdf