![]()
Visiting guest. Why not sign in?
|
|
GA for Othello Genetic algorithm to play othello | |
GA for Othello
I'm most of the way through implementing GA to learn to play Othello. To play the computer looks at all the possible moves it could make and picks the one with the most points for that turn. So if all squares had the same value then the move that captured the most pieces would be choosen. The winner gets some points that count towards its fitness in that generation. Every member of the generation plays every other (like a league) and the position (and total points) in the league determines the probability of reproduction. Breeding is done using a number of random crossovers (I might add a second chromosone later that has the number and location of cross overs) The starting generation will be seeded with random values and left to its own devices. When it can beat my hand crafted individual I'll try it against myself! Any advice, comments, improvements etc. welcome. Jester |
|
Advice
I've not played around with Othello much myself, but I have played around with GAs a lot. I would advise you to seed the pool with at least one hand crafted GA - this helps "set the bar" for the evaluation. Also, consider using a look-ahead function. Your GA might generate a good evaluation function, but you can't beat a good min/max search. ;) |
|
Cheers
If I seed the pool with my own individuals aren't I possibly cutting off unusual avenus of exploration? Is it better have a large or small population for such a problem? Small population = quicker fixation of genes (both good and bad!) and less diversity. Is this why you suggest hand crafting the initial population? I realise that minimax will take any of individuals to the cleaners but I thought I'd work on the GA bit first (since it interests me more) and them move on to adding lookahead. Do you know any good resources? Cheers for the advice, Jester |
|
Stochastic Elitism
If you seed the pool with a hand crafted, and then always pick the seed, then yes, you will be cutting off avenues of exploration. You need to pick individuals among the best, definitely - that's elitism for those of you that are new to genetic algorithms. But you need to make sure that you don't always pick the same one, hence the stochastic part. Picking randomly among the best helps a lot: the more random, the more variety... so it's a trade of between quick evolution times and potentially better solutions. As you said. The choice of population size also has the same impact, small = fast, large = slower evolution. It sounds corny, but it's best to experiment! Not a lot has been done in pure GA-Othello, so come to your own conclusions. With a fairly straight-forward model like you use, I should think a smallish population of 64 would do the trick nicely. You'll probably have to redesign the representation of the problem when you move on to doing look-ahead, since it's a bit of a different methodology. The GA stuff will generally apply in both cases though. |
|
Sub-optimal convergence
Well, when I said seed the gene pool, I meant throw one or two handcrafted genomes into the mix with the rest being random, not hand craft the whole lot. But, that said, if your having convergence problems, one strategy for avoiding this is to have several isolated gene pools for breeding. Examine the results between sessions, and save effective strategies to use in later runs. |
|
Excluding 'super' seed individuals
Sorry, codemonkey_uk I misread your message. Only after I had posted my reply did I read it properly. I hadn't thought of seeding the pool with some good initial individuals. Do you exclude them from the evolution process, so as not to bias potential solutions? Cheers, Jester |
|
Including Seeds
I wouldn't personally exclude them... just don't select them too often, by adding randomness to the selection. See my post above called 'stochastic elitism' |
|
Look Ahead Search
... is the way to go in my humble opinion. I started work on a NN-GA othello player a while back, and that's the approach I took in the end. But it's good for you to come to your own conclusions. First read up about 'advanced' human tactics, as described in this page: The Strategy to Winning Othello. It puts things into perspective, and gets you thinking about what is needed to allow such complex behaviour. The representation you chose is fairly simplistic, and will not allow these complex othello behaviour - such as mobility for example. IF you need to improve the model, either you can move to an evaluation based player, using GA to evolve the estimation function... or you can use GA all the way to define the rules followed by the player. |
|