genetic go bot

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
phillip1882
Posts: 95
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

genetic go bot

Postby phillip1882 » Tue Feb 24, 2015 11:45 pm UTC

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.
bitcoin address: 1B73mjAguoK9ATwVjGcy2LasyfG9xtLGsq

User avatar
Xanthir
My HERO!!!
Posts: 5228
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: genetic go bot

Postby Xanthir » Wed Feb 25, 2015 12:10 am UTC

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.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: genetic go bot

Postby Lopsidation » Sun Mar 01, 2015 3:34 pm UTC

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.

flownt
Posts: 70
Joined: Sat Feb 09, 2013 5:24 pm UTC

Re: genetic go bot

Postby flownt » Thu Mar 05, 2015 11:38 pm UTC

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.

User avatar
Mat
Posts: 414
Joined: Fri Apr 21, 2006 8:19 pm UTC
Location: London

Re: genetic go bot

Postby Mat » Fri Mar 06, 2015 10:23 pm UTC

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.

User avatar
You, sir, name?
Posts: 6974
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: genetic go bot

Postby You, sir, name? » Thu Mar 12, 2015 7:36 pm UTC

Yeah, I think MCTS is favored for go AIs.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Mat
Posts: 414
Joined: Fri Apr 21, 2006 8:19 pm UTC
Location: London

Re: genetic go bot

Postby Mat » Sun Mar 29, 2015 9:12 am UTC

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


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests