tag:blogger.com,1999:blog-61785244605223550632024-02-21T08:16:27.651+00:00CharlieAIThis is a project I started a few years ago; an experiment to create AI that can learn to play board games, and play them well, without at first even knowing the rules.Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-6178524460522355063.post-692369260611560412013-07-05T23:00:00.002+01:002013-07-05T23:00:50.603+01:00Connection EstablishedFor a while I've been working on a GGP agent that can connect to the <a href="http://tiltyard.ggp.org/">Tiltyard hosting server</a> and I've finally got it working. It uses the framework from <a href="http://cadia.ru.is/wiki/public:cadiaplayer:main">cadiaplayer</a> for the web server part, my own custom message handler to govern the central message loop and the <a href="http://www.general-game-playing.de/downloads.html">KIF parsing framework from Dresden University</a> to parse and reason about the games.<br />
<br />
To test things, this agent is just picking the first valid move it comes across. It doesn't apply strategy or move evaluation of any sort. Still, it is great to see it play valid moves for a wide range of games without knowing the rules ahead of time.<br />
<br />
It first tells the server it's ready to play, then the server sends it the rules for a game, informs it of other players' moves and my agent sends back valid moves. When the game is over, the server starts a new game with a different set of rules.<br />
<br />
In testing it, my agent played through the games of Peg Jumping, Knight's Tour, Tic Tac Toe, 3-player Chinese Checkers and Bomberman! Below is a screenshot of it playing Chinese Checkers (my agent played Red).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPsLM7Ykucb7TJRqI3LRdGw7iI65zpxWRsG97QpmOb-8DthmmgioyGQe50KuM2Wg2cwxSeMGFnpCQeK3k3aDasFl3rfh2G_mMQjV8qV0fKeyTXhlUnEQaOtp5a2_EMld-648DPV3RVRJ-u/s1600/Screen+Shot+2013-07-04+at+22.12.53.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgPsLM7Ykucb7TJRqI3LRdGw7iI65zpxWRsG97QpmOb-8DthmmgioyGQe50KuM2Wg2cwxSeMGFnpCQeK3k3aDasFl3rfh2G_mMQjV8qV0fKeyTXhlUnEQaOtp5a2_EMld-648DPV3RVRJ-u/s320/Screen+Shot+2013-07-04+at+22.12.53.png" width="320" /></a></div>
<br />
<br />
Next step is to integrate <a href="http://charlieai.blogspot.co.uk/2013/05/monte-carlo-tree-seach.html">my Monte Carlo Tree Search algorithm</a> - I will report back :)<br />
<br />
<br />Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-15794584332497504242013-06-29T07:35:00.000+01:002013-06-29T07:37:52.449+01:00General Game Playing Platforms<div>
For several years, a community of people generating and competing with AI to play games has existed. In recent years this community has expanded considerably, mainly due to the projects at the <a href="http://logic.stanford.edu/">Stanford Logic Group</a>, so I wanted to give a summary of the field as it stands now.</div>
<div>
<br /></div>
<div>
<a href="http://en.wikipedia.org/wiki/General_game_playing">General Game Playing (GGP)</a> is the art of making AI that can play a diverse range of games well without being hand-programmed for any specific game. Rules are described <a href="http://en.wikipedia.org/wiki/Game_Description_Language">in a formal language called GDL</a> and agents parse the game descriptions, infer the valid moves at any given time and apply a strategy to win.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9BxA90NjZLPubdW-csyoDROIG7I9Xv6Bb78mplNbvqFvfXJ54tQcaXdW2mMuCdk_ExhPuJQ6fFkhmUUbEOtTNPXeKsUPHrpoCQp7rWmxOL16auGQhBubup8UtYoh8-LYaoVg_6izkpj92/s1600/Screen+Shot+2013-06-25+at+21.14.06.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="276" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9BxA90NjZLPubdW-csyoDROIG7I9Xv6Bb78mplNbvqFvfXJ54tQcaXdW2mMuCdk_ExhPuJQ6fFkhmUUbEOtTNPXeKsUPHrpoCQp7rWmxOL16auGQhBubup8UtYoh8-LYaoVg_6izkpj92/s400/Screen+Shot+2013-06-25+at+21.14.06.png" width="400" /></a></div>
There are multiple Game Manager hosts, which developers can register their agents with. The main two ones are <a href="http://130.208.241.192/ggpserver/">Dresden GGP Server</a> and <a href="http://tiltyard.ggp.org/">Tiltyard</a> which provide <a href="http://www.ggp.org/view/tiltyard/games/">large game databases</a> played by <a href="http://www.ggp.org/view/tiltyard/players/">registered agents</a>. Matches are automatically hosted between agents, across the Internet, and participants are awarded scores and ratings. The time between an agent getting to know the rules and having to play the game is typically less than a minute, so the AI must be truly general-purpose to play well across the large variety of games.</div>
<div>
<br /></div>
<div>
Every year a world cup with prizes is held for the very best agents. Fluxplayer, Ary and Turtleplayer have been strong in the past, but <a href="http://cadia.ru.is/wiki/public:cadiaplayer:main">Cadiaplayer</a> from Reykjavik University has won most world cups and is also the current champion.</div>
<div>
<br /></div>
<div>
The <a href="http://www.inf.tu-dresden.de/index.php?node_id=2195">slides from a previous course at Dresden University</a> are a good introduction on how to get started. Several existing frameworks and reference players help to get up to speed quickly. There is also <a href="https://www.coursera.org/course/ggp">an online course starting in September at Coursera</a> that will teach all the relevant theory and practical knowledge to participate.<br />
<br />
My next step is to put together a framework that can parse GDL and communicate to the Game Manager via the established protocol, and then start plugging in my previous AI algorithms. Exciting times ahead! :)</div>
Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-70988351535666705302013-05-27T17:06:00.001+01:002013-06-20T09:31:42.769+01:00Connect Four Embedded, Too<div style="text-align: center;">
<div style="text-align: left;">
And here is the Connect Four player available for you to play against (on Mac OS X and Windows). Again, let me know if you manage to beat it.</div>
<div style="text-align: start;">
<div style="text-align: left;">
<br /></div>
</div>
</div>
<div style="text-align: center;">
<iframe height="320" src="http://unitygadgets.gayasoft.ch/WebContainer/UnityWebContainer_2_0.php?url=https://dl.dropboxusercontent.com/u/83880716/connect4.unity3d&width=300&height=300" width="320"></iframe></div>
Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com2tag:blogger.com,1999:blog-6178524460522355063.post-72074312654082544202013-05-27T15:24:00.003+01:002013-05-27T15:46:10.240+01:00Tic Tac Toe EmbeddedI managed to put together a simple interactive application for the Tic Tac Toe player, and embed it here. Unfortunately it only supports Mac OS X and Windows, so apologies if you are viewing this from some other operating system.<br />
<br />
Let me know if you manage to win! :)<br />
<div style="text-align: center;">
<br /></div>
<div style="text-align: center;">
<iframe height="320" src="http://unitygadgets.gayasoft.ch/WebContainer/UnityWebContainer_2_0.php?url=https://dl.dropboxusercontent.com/u/83880716/web.unity3d&width=300&height=300" width="320"></iframe></div>
Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com2tag:blogger.com,1999:blog-6178524460522355063.post-36506468361545416032013-05-26T07:37:00.000+01:002013-06-20T09:39:24.355+01:00Does it play Connect Four? Yes, it does.<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdlVICTkHy_-Qa7or2ulfgpuCmyHee_PaF2Pr9xuqitSgTPSXPvr4Om8iXVPDj3s3K80lBRVOZKQmHqbhDQqDjfdV4WphdL4Ub8uhcPn48romWtOCKFRAXENUNd9ZEVuEs94M7qTmuuHVw/s1600/connect4.gif" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="222" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhdlVICTkHy_-Qa7or2ulfgpuCmyHee_PaF2Pr9xuqitSgTPSXPvr4Om8iXVPDj3s3K80lBRVOZKQmHqbhDQqDjfdV4WphdL4Ub8uhcPn48romWtOCKFRAXENUNd9ZEVuEs94M7qTmuuHVw/s320/connect4.gif" width="320" /></a></div>
Based on how well my <a href="http://charlieai.blogspot.co.uk/2013/05/monte-carlo-tree-seach.html">Monte Carlo Tree Search agent played Tic Tac Toe</a>, I wanted to move onto Connect Four.<br />
<br />
Because the algorithm is domain independent I merely had to add the logic to list valid moves and determine a win, loss or draw outcome. One half-hour commute later and I had it playing Connect Four!<br />
<br />
And it plays well, in fact really really well. Despite me trying my very best and with help from my wife, who happens to beat most of our family and friends at this game, we cannot beat the AI, when it plays first. Connect Four has been fully solved by MinMax searches and it can be shown that the first player can always force a move. This is exactly what my MCTS agent does. It will setup various potential win cases at the higher level slots and then eventually force you into playing moves that will allow it to win.<br />
<br />
<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJTdaVxqS361MD94eI5gc-O9U-mBb1_iAApT8R4w-sau-_wQavwsl-DLiSGAg9DpFwC8JHCT8rzr1gPIHgRMhOKy0srnHKYUCQI8kJDCFYk5JeCQKk2yYxZ_zAjA7YX9xC-QFBLz25DvaP/s1600/Screen+Shot+2013-05-26+at+07.31.33.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgJTdaVxqS361MD94eI5gc-O9U-mBb1_iAApT8R4w-sau-_wQavwsl-DLiSGAg9DpFwC8JHCT8rzr1gPIHgRMhOKy0srnHKYUCQI8kJDCFYk5JeCQKk2yYxZ_zAjA7YX9xC-QFBLz25DvaP/s1600/Screen+Shot+2013-05-26+at+07.31.33.png" /></a>The other nice thing about the playing style you get from MCTS is that even if you play the same moves against it, due to its random sampling of the search tree, it will typically come up with slightly varied responses - ultimately leading to a win of course! :)<br />
<br />
What's next? I'm currently deciding on whether to move onto 9x9 Go, some other intermediate step, or perhaps spend a bit of time making simple web-based GUIs for the Tic Tac Toe and Connect 4 agents, as my current UI is a bit lacking...see insert :)<br />
<div>
<br /></div>
Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-24766001267790316022013-05-25T16:26:00.001+01:002013-05-25T16:26:46.504+01:00Monte Carlo Tree SeachRecently I have made great progress on my AI project, so today I will attempt to wake this sleepy blog from hibernation.<br />
<br />
While I had heard about the success of Monte Carlo Tree Search applied to Go and other games a few years ago, it was only about a month ago that I became aware that in its basic form the algorithm is domain independent. It is therefore very suitable for my goal of making general game playing AI that doesn't need to be taught the rules of the games played.<br />
<br />
For the necessary background knowledge and a great introduction to the algorithm and its variations, <a href="http://www.cameronius.com/cv/mcts-survey-master.pdf">"A Survey of Monte Carlo Tree Search Methods"</a> is a great resource. This paper also includes pseudo-code for the basic algorithm.<br />
<br />
In essence, MCTS plays thousands of games to completion taking random moves to get there. The resulting win, loss or draw of each game then informs the algorithm which parts of the search tree to explore further. This combination of random moves and statistical analysis makes the algorithm applicable to a large range of domains and also means it scales well to harder problems - the more CPU time you give it, the better the result will be.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRzGn7WNcJJnQSyE0zZGubR_GN7VvEReIon5tMLQIgEAAVserE2nFRI9jR3h8ezBvFqEIwk3nJljogJyOMix0YSPXFMSduBQ90mC5Ej1Ep5wd9UxhHfZBsAAWpzxp68vAjHbPmVeWgo-A3/s1600/mcts.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgRzGn7WNcJJnQSyE0zZGubR_GN7VvEReIon5tMLQIgEAAVserE2nFRI9jR3h8ezBvFqEIwk3nJljogJyOMix0YSPXFMSduBQ90mC5Ej1Ep5wd9UxhHfZBsAAWpzxp68vAjHbPmVeWgo-A3/s1600/mcts.png" /></a></div>
<br />
<br />
Because the algorithm plays the games to completion, it only needs to be informed about which moves are valid for each turn and whether the game resulted in a win, loss or draw at the end. No other domain-specific knowledge is required.<br />
<br />
Is this the end of my genetic programming approach? Quite the opposite, I will be exploring combining the two approaches in the near future.<br />
<br />
To try out MCTS, I implemented the basic algorithm and applied it to Tic Tac Toe. After a couple of hours of coding I was ready to play against it...and...it plays extremely well! If the agent starts, it appears impossible to win against it. It sets up clever double win strategies so the best a human opponent can hope for is a draw. I was very impressed!<br />
<br />
It is time to move on to the slightly more complex game of Connect 4...Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-17472756597303097152011-10-08T19:24:00.000+01:002011-10-08T19:24:11.045+01:00Objective Score for Good Move Algorithm<div style="text-align: justify;">I wanted to get an idea of what a relatively strong Tic-tac-toe player would score with the objective measure. So instead of using an evolved player, I measured the Good Move algorithm. As mentioned before it looks for 2 pieces in a row with an empty square at either end and then plays there or blocks accordingly. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Here are the scores from ten tests and the average score computed:</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">967, 975, 844, 968, 1021, 917, 992, 1059, 1051, 986 => 978.0</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Now, this algorithm doesn't look ahead more than one move so it will not play perfectly, but it will be relatively strong. If I can somehow evolve something as strong as that, using co-evolution, it would certainly be a worthy opponent.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-5989245962665140162011-10-07T22:38:00.002+01:002011-10-08T12:23:24.900+01:00Initial Objective ScoresI completed the <a href="http://charlieai.blogspot.com/2011/10/tic-tac-toe-yardstick.html">objective scoring function that I mentioned earlier</a> and wanted to document some initial results. I did 10 evolution runs against each opponent type, until a perfect fitness case was found, and calculated the average objective score:<br />
<br />
Random Move: 124, 180, 108, 132, 366, 160, 108, 72, 198, 108 =>155.6<br />
Good Move: 310, 344, 882, 138, 273, 1172, 150, 518, 128, 246 => 416.1<br />
<br />
The Random Move opponent simply just picks a random, valid, move each turn.<br />
<br />
Good Move picks a winning move if there is one move that makes 3 in a row, and blocks the opponent if there is a chance for them to play one piece to get 3 in a row. Otherwise it just picks a random, valid, move.<br />
<br />
The setup was as follows:<br />
<br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><td><b>Function nodes</b></td><td><i>+, -, *, /, IfThenElse, =, >, <, And, Or, MakeMove</i></td></tr>
<tr><td><b>Terminal nodes</b></td><td><i>0, 1, 2, Ephemeral Constant (0-10), SQ_00...SQ_22 </i></td></tr>
<tr><td><b>Crossover probability</b></td><td><i>90%</i></td></tr>
<tr><td><b>Reproduction probability</b></td><td><i>9%</i></td></tr>
<tr><td><b>Mutation probability</b></td><td><i>1%</i></td></tr>
<tr><td><b>Mutation depth</b></td><td><i>2</i></td></tr>
<tr><td><b>Max tree size (number of nodes)</b></td><td><i>100</i><br />
</td></tr>
<tr><td><b>Max tree depth</b></td><td><i>30</i><br />
</td></tr>
</tbody></table><br />
Of course, this was more teaching the AI how to play as opposed to letting it evolve from scratch, so the true test would be with co-evolution. However, I needed to do some more groundwork to get that up and running in my new environment...Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-11083017273392536502011-10-02T21:18:00.000+01:002011-10-05T15:56:04.695+01:00A Tic-tac-toe Yardstick<div style="text-align: justify;">After getting a new laptop and installing Linux on it (after some experimentation I settled with <a href="http://www.ubuntu.com/">Ubuntu</a>), I now have a better system to continue experimentation on. I have been spending some time converting my existing code to make use of some of the new <a href="http://en.wikipedia.org/wiki/C%2B%2B11">C++11</a> features and its new standard library. The GP system now relies very little on the Boost library (purely for timing functions) and is thus much more portable.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;"> </div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgC3VQA0eySwPMKkbBCPLzjx-XKiTgJichObEDIA6qRGsu5SXJL-_QjrAsKxCH7VNeugF-aySe7d3xk9X_ginXb-Z_HzSMr2APY7R6HkLgEW0BTzJKrJ9xn6Vly_agAA2Wp1lqSjMVNw658/s1600/Yardstick-500x375.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="150" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgC3VQA0eySwPMKkbBCPLzjx-XKiTgJichObEDIA6qRGsu5SXJL-_QjrAsKxCH7VNeugF-aySe7d3xk9X_ginXb-Z_HzSMr2APY7R6HkLgEW0BTzJKrJ9xn6Vly_agAA2Wp1lqSjMVNw658/s200/Yardstick-500x375.jpg" width="200" /></a></div><div style="text-align: justify;">So now the focus is on what I can do to evolve something that successfully plays Tic-tac-toe. Something I have been wanting to introduce for a long time is a yardstick - a way to objectively measure how good my Tic-tac-toe players are. You cannot really do good science without one - how else do you know when you have improved the system or by how much?</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Fortunately, for a simple game like Tic-tac-toe it should be possible to make the yardstick something that systematically plays all possible game permutations against the evolved players. An upper bound for the number of permutations can be computed by observing that the first move can be any of 9 possible moves, then 8, then 7 etc. reaching a total of 9! = 362880 permutations. Considering that often a winner is determined before the game is played that far, the actual number of games to play through will be a lot lower. Thus, the yardstick should not be too cpu-intensive and can probably easily be applied at the end of each run to give it an objective score: The number of wins against the yardstick player, which tries out each each possible permutation.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-82369320888257035792011-08-05T21:03:00.001+01:002011-10-02T20:36:20.059+01:00Fibonacci Sequence<div style="text-align: justify;">I wanted to test my GP framework with a more challenging problem. So a few weeks ago I decided to use my newly found <a href="http://charlieai.blogspot.com/2011/05/cloud-computing-to-rescue.html">computing resource</a> to try and evolve a program that can output the first 30 numbers of the <a href="http://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci sequence</a>.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">My initial setup was similar to the one used in <a href="http://charlieai.blogspot.com/2011/05/loops-in-genetic-programming.html">the search for even numbers</a> - only the fitness function differed. This time it did not result in a perfect solution however. Elaborate approximations were evolved but at no point was a simple iterative solution, keeping track of the last two numbers output and adding these up, evolved.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I thought there may have been some subtle bug in my system preventing that kind of program to be constructed, so I tried manually creating one using the function nodes available to the simulation. That worked fine, so somehow the probability of evolving an equivalent program was just very unlikely. That led me to experiment with other pseudo-random number generators (I ended up using Boost's Mersenne twister implementation). Still no perfect solution.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I had been using a fixed seed for my random number sequences so the final thing I tried was to change the system to use the system clock as seed in order to get variation in successive runs. I ran the final setup with large populations and hundreds of generations ten times over. Still no perfect solution. Still just very good approximations.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I finally concluded that the simulation is very likely to generate a good approximate solution early on and thus gets stuck in a local maximum, where progressive improvements do not move the population in the direction of a perfect solution, and where the distance to the perfect solution is so vast that arriving at it is extremely improbable.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">The experiment underlined how important it is to provide an environment with gradual selection pressure if one wants to succeed with genetic programming. </div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-28631251038317955142011-05-29T20:24:00.000+01:002011-05-29T20:24:41.764+01:00Cloud computing to the rescue<div style="text-align: justify;">I've been playing with the thought of getting a fast, reliable computer for my experiments for a while, and a couple of weeks ago I found the perfect solution: <a href="http://aws.amazon.com/ec2/">Amazon Elastic Compute Cloud</a>. You basically launch computer instances on a need by need basis and within a few seconds they are up and running with whatever OS and software you have configured on them.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">It is relatively cost-effective compared to buying your own hardware and maintaining that. I only need computing power from time to time, but most often a lot of it, and this way I can launch as many cores as I need whenever I need! :)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Their Linux instances are the most powerful, so I've spent some time porting my GP code, as a few components were not as portable as I would have liked (was using Windows-based threads and timers). It's now all <a href="http://www.boost.org/">Boost</a> based and today I got it all running so I can't wait to try some more experiments on fast CPUs.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-56055416888979759522011-05-07T21:35:00.000+01:002011-05-07T21:35:34.376+01:00Loops in Genetic Programming<div style="text-align: justify;">Dealing with loops and other iterative constructs in GP is far from trivial. You have to deal with closure and you have to avoid infinite or lengthy fitness evaluations. It only takes a few nested loops of a million iterations each in your individuals to grind everything to (nearly) a halt.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">This is perhaps why loops have not seen much use in the GP field. <a href="http://goanna.cs.rmit.edu.au/%7Exiali/pub/cec04.exploops.pdf">Experiments with Explicit For-loops in Genetic Programming</a> by Vic Ciesielski and Xiang Li provides good coverage of related work.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I ended up using a binary variant of protected for-loops where the first sub tree provides the number of iterations, and the second sub tree, the body of the loop, is then iterated. I did not restrict the number of loop nodes per program, but instead enforced an overall limit of 1000 iterations per program.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">To give the programs something to work with, I also introduced a few variable nodes to read and write the variables X and Y. X was always set to the current iteration of a loop.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">This allowed me to evolve a perfect solution to the "100 First Even Numbers" sequence in just 8 generations amongst a population of 10,000! :) The run parameters as well as the tree of the perfect solution can be seen below:</div><div style="text-align: justify;"><br />
</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><td><b>Function nodes</b></td><td><i>Add, Subtract, Multiply, Divide, SetX, SetY, OutputNumber, Loop</i></td></tr>
<tr><td><b>Terminal nodes</b></td><td><i>0, 1, 2, Ephemeral Constant (0-10), GetX, GetY </i></td></tr>
<tr><td><b>Crossover probability</b></td><td><i>90%</i></td></tr>
<tr><td><b>Reproduction probability</b></td><td><i>9%</i></td></tr>
<tr><td><b>Mutation probability</b></td><td><i>1%</i></td></tr>
<tr><td><b>Mutation depth</b></td><td><i>2</i></td></tr>
<tr><td><b>Max tree size (number of nodes)</b></td><td><i>30</i></td></tr>
<tr><td><b>Max tree depth</b></td><td><i>10</i></td></tr>
</tbody></table><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_nT3C71XNXNdZw475qlReM5SX44C_5tLgVF4WAJ6ZggA7fkoJuy_0zxREDRYSl3jSsihW7LZR491nZvezyr_kI8hrZmAdutJ39w5jLhtCKhIvyy1LzX0MkvT0oA6RMFoBsYMSA4_kKFGb/s1600/2timestable_8gen_10000.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="396" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg_nT3C71XNXNdZw475qlReM5SX44C_5tLgVF4WAJ6ZggA7fkoJuy_0zxREDRYSl3jSsihW7LZR491nZvezyr_kI8hrZmAdutJ39w5jLhtCKhIvyy1LzX0MkvT0oA6RMFoBsYMSA4_kKFGb/s400/2timestable_8gen_10000.gif" width="400" /></a></div><div style="text-align: justify;"><br />
</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com2tag:blogger.com,1999:blog-6178524460522355063.post-9491896228461644242011-05-03T18:49:00.004+01:002011-05-04T13:00:50.494+01:00Sequences<div style="text-align: justify;">I wanted to do some experiments with simpler problems, so last night I experimented with evolving individuals that can generate a sequence of numbers. Fitness is then based on how many of these numbers match a predefined sequence. Conceptually, sequences of numbers are a bit like board games, which in a way just boil down to sequences of moves...<br />
<br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><td><b>Function nodes</b></td><td><i>Add, Subtract, Multiply, Divide, SetX</i></td></tr>
<tr><td><b>Terminal nodes</b></td><td><i>0, 1, 2 </i></td></tr>
<tr><td><b>Crossover probability</b></td><td><i>90%</i></td></tr>
<tr><td><b>Reproduction probability</b></td><td><i>9%</i></td></tr>
<tr><td><b>Mutation probability</b></td><td><i>1%</i></td></tr>
<tr><td><b>Mutation depth</b></td><td><i>2</i></td></tr>
<tr><td><b>Max tree size (number of nodes)</b></td><td><i>300</i></td></tr>
<tr><td><b>Max tree depth</b></td><td><i>100</i></td></tr>
</tbody></table><br />
I experimented with the sequence of even numbers. The system struggled to evolve large sequences correctly, but produced perfect solutions for up to the first 6 even numbers: 2, 4, 6, 8, 10, 12 after a few minutes of computation. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Note that the "index" was not provided to the population - the programs simply had to add numbers to a list, with a SetX function node, and then the list was examined in full afterwards. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">At first I limited the tree depth to 30, which turned out to be too stringent. Expanding the limit to 100 was sufficient up to the first 6 digits. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">After examining the trees containing perfect solutions, I'm starting to see why the trees need to be so deep. Personally, if I coded the program tree manually, I would not be able to create a much shallower tree with the function nodes provided; I would need a Loop node. So I will try to add that next.<br />
<br />
But that got me thinking about the Tic-tac-toe experiment. I had avoided adding a Loop node in order to not make the search space too large. In my mind, the solution I had expected to evolve was a giant if-then-else-if-else-if... block with all the possible positions to block against. But considering the number of possible "near-wins" for the opponent there are quite a few: 3 horizontal, 3 vertical and 2 diagonal lines, each of which can have two pieces in 3 different ways, so 24 moves to block against. The Sequence experiment struggled with anything higher than 6 numbers of a sequence, so it's not surprising that the Tic-tac-toe opponents couldn't cover most winning strategies.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">So a Loop function node may actually help quite a lot. Alternatively, a FunctionList node may do the trick...i.e. something with high arity that calls a number of sub trees in turn, similar to calling a function in procedural programming languages (making the tree wide instead of deep). Automatically-Defined-Functions would also be interesting to add, to improve reuse of code.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">But first things first, so I will try with Loops initially.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-65958852947013652862011-05-02T16:38:00.001+01:002011-05-06T16:38:04.261+01:00Tic-tac-toe with Charlie<div style="text-align: justify;">I first attempted the Tic-tac-toe experiment, using Charlie, with the same setup as the symbolic regression experiment, along with a MakeMove function node and terminal nodes to represent the status of each square on the board:</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><td><b>Function nodes</b></td><td><i>Add, Subtract, Multiply, Divide, MakeMove</i></td></tr>
<tr><td><b>Terminal nodes</b></td><td><i>0, 1, 2, EphemeralConstanct(0,10), SQ_00, SQ_01, SQ_02, SQ_10, SQ_11, SQ_12, SQ_20, SQ_21, SQ_22</i></td></tr>
<tr><td><b>Crossover probability</b></td><td><i>90%</i></td></tr>
<tr><td><b>Reproduction probability</b></td><td><i>9%</i></td></tr>
<tr><td><b>Mutation probability</b></td><td><i>1%</i></td></tr>
<tr><td><b>Mutation depth</b></td><td><i>2</i></td></tr>
<tr><td><b>Max tree size (number of nodes)</b></td><td><i>unlimited</i></td></tr>
<tr><td><b>Max tree depth</b></td><td><i>unlimited</i></td></tr>
</tbody></table><br />
<div style="text-align: justify;">That didn't produce very good results. This was as expected as there were no conditional function nodes. So I introduced If-Then-Else, Equals, Greater-Than, Less-Than, And and Or operators and immediately got more promising results. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">However, it was still very easy to beat the evolved opponents, so I went ahead and made various performance optimisations including making the simulation multi-threaded. Still not very good results. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I then tried running the setup with huge populations, on a 64-bit OS with lots of RAM, for several weeks but still the best opponents were mediocre and very easy for humans to beat. They frequently made large blunders and you didn't have to be particularly careful to ensure a win against them.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">All in all, very similar results to the <a href="http://charlieai.blogspot.com/2011/03/hall-of-fame-archives.html">initial Beagle experiment</a>, so quite disappointing. That brings my journal up to the present. Yes, I'm stuck with this current issue of the simulation getting stuck before strong players are evolved. I'm going to try and think of some new approach or tweak to the setup to improve things. Do let me know if you have any suggestions!</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-54745803071666178702011-04-11T18:15:00.001+01:002011-04-12T14:16:01.775+01:00Symbolic regression results<div style="text-align: justify;">An important role of this blog is to act as a journal of my experiments. Onwards from now I will seek to document my experiments with enough detail to allow others to compare results, and so that I can compare results myself at a later date. So here we go...</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I managed to dig out some notes from my early Charlie tests - at first I experimented using the following setup: </div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><td><b>Function nodes</b></td><td><i>Add, Subtract, Multiply and Divide</i></td></tr>
<tr><td><b>Terminal nodes</b></td><td><i>0, 1, 2 and x</i></td></tr>
<tr><td><b>Crossover probability</b></td><td><i>90%</i></td></tr>
<tr><td><b>Reproduction probability</b></td><td><i>9%</i></td></tr>
<tr><td><b>Mutation probability</b></td><td><i>1%</i></td></tr>
<tr><td><b>Mutation depth</b></td><td><i>2</i></td></tr>
<tr><td><b>Max tree size (number of nodes)</b></td><td><i>unlimited</i></td></tr>
<tr><td><b>Max tree depth</b></td><td><i>unlimited</i></td></tr>
</tbody></table><br />
<div style="text-align: justify;">Below is a table of experiments I made with the above configuration. The function that I was trying to evolve is on the left. Population size and maximum generations are also listed along with some comments on the results:</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><th>Function</th><th>Population Size</th><th>Generations</th><th>Result</th></tr>
<tr><td>7.2x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution and struggling.</td></tr>
<tr><td>7x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 16 generations</td></tr>
<tr><td>7x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 1 generation</td></tr>
<tr><td>7.2x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution. Best fitness score: ~442</td></tr>
<tr><td>7.2</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution</td></tr>
</tbody></table><br />
<div style="text-align: justify;">I was surprised that the system struggled to generate a sub tree equal or close to 7.2. It seemed to evolve integers just fine but struggled with fractions. I therefore tried introducing two further terminal nodes: the constants 4 and 8 in the hope of guiding the evolution to the right ballpark figures. I repeated the last experiment above, but still got no perfect or even approximate solution:</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><th>Function</th><th>Population Size</th><th>Generations</th><th>Result</th></tr>
<tr><td>7.2</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution</td></tr>
</tbody></table><br />
<div style="text-align: justify;">I got desperate and decided to introduce ephemeral constants, which was on my to-do list anyway. I also removed constants 4 and 8 to reduce the search space a bit again. This resulted in the following figures:</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><th>Function</th><th>Population Size</th><th>Generations</th><th>Result</th></tr>
<tr><td>7.2</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution, but very close (~0.0001)</td></tr>
<tr><td>7.2x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution but no longer struggling.</td></tr>
<tr><td>7x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution.</td></tr>
<tr><td>7x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 1 generation</td></tr>
<tr><td>7.2x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution. Best fitness score: ~13</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">100000</td><td style="text-align: center;">43</td><td>No perfect solution but very close</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">10000</td><td style="text-align: center;">100</td><td>No perfect solution. Best fitness score: ~12</td></tr>
<tr><td>sqrt(x)</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution. Best score: ~34</td></tr>
<tr><td>7x+x<sup>2</sup>-3x+x<sup>3</sup></td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 6 generations.</td></tr>
</tbody></table><br />
<div style="text-align: justify;">The results were better but by no means amazing. I then came across a subtle bug that meant some arguments were not forwarded to sub trees, and after fixing that I got the following results:</div><br />
<table border="0" bordercolor="#ffcc00" cellpadding="3" cellspacing="3" style="background-color: #cccccc; width: 500px;"><tbody>
<tr><th>Function</th><th>Population Size</th><th>Generations</th><th>Result</th></tr>
<tr><td>7.2</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution, but very close (~0.00001)</td></tr>
<tr><td>7.2x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution but no longer struggling.</td></tr>
<tr><td>7x<sup>3</sup>+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 12 generations.</td></tr>
<tr><td>7x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 1 generation</td></tr>
<tr><td>7.2x+x<sup>2</sup>-3x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution, but very close (~0.0001)</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution, but very close: ~10e-6.</td></tr>
<tr><td>7.2x</td><td style="text-align: center;">100000</td><td style="text-align: center;">31</td><td>No perfect solution but very close: ~10e-6.</td></tr>
<tr><td>sqrt(x)</td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>No perfect solution. Best score: ~0.036</td></tr>
<tr><td>7x+x<sup>2</sup>-3x+x<sup>3</sup></td><td style="text-align: center;">10000</td><td style="text-align: center;">50</td><td>Perfect solution in 3 generations.</td></tr>
</tbody></table><br />
<div style="text-align: justify;">That was more like it! :) It was time to try the Tic-tac-toe experiments with Charlie...</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-37354083963620508922011-03-08T22:21:00.000+00:002011-03-08T22:21:57.489+00:00Introducing Charlie<div style="text-align: justify;">A few years ago I decided that to fully understand the dynamics of genetic programming, I would have to implement my own framework. <a href="http://charlieai.blogspot.com/2011/02/open-beagle.html">Beagle</a> had proved incredibly useful, but I required full control of the entire software design, down to minute details, so I had to write my own.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Named after a dog we had when I was a kid, and after a certain pioneer in the field of evolution, I called my new framework Charlie (if you were wondering why this blog was called CharlieAI, you now have your answer!)</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I will spare you the implementation details and instead list the feature set I ended up with:</div><div style="text-align: justify;"><br />
</div><ul><li>Tree-based genomes</li>
<li>Cross-over, mutation and re-selection operators</li>
<li>Node and sub-tree mutation</li>
<li>Tournament-based selection</li>
<li>Ephemeral random constants</li>
<li> Population statistics</li>
<li>Lisp-style and graph in .gif file output (Graphviz)</li>
<li>Multi-threaded evaluation</li>
<li>Single and co-evolution</li>
<li>Hall-of-fame archives</li>
</ul><div style="text-align: justify;"></div><div style="text-align: justify;"><br />
This was all built over six months or so, but I only had a few hours of time to devote every week so the whole thing could easily have been done in something like two weeks of full-time work. I must admit, though, that it was nice to have ample thinking time between implementation steps, to ensure it all fitted well together and performed efficiently.<br />
<br />
Next I will cover the results I got from running symbolic regression experiments with this framework. In the meantime, if you would like any more details on any of the above features or any aspects of the software, do let me know and I will attempt to cover it in a future post.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-64975816781592083982011-03-03T21:46:00.001+00:002011-03-04T07:50:26.669+00:00Hall-of-fame archives<div style="text-align: justify;">To solve the problem with <a href="http://charlieai.blogspot.com/2011/03/strategy-loops.html">strategy loops</a>, I implemented a hall-of-fame archive - a collection of the best individual from each generation that led to a new "champion". Generations that did not beat the opposing population were ignored.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Fitness was then measured as an individual's performance against the opposing population's entire archive. Only if all members could be beaten, would a new champion emerge and get added to its population's archive. Thus, loops were made impossible and only definite progress was allowed.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">One issue with this approach was the increasing CPU costs of evaluating individuals as the archives expanded, but this is the approach I still use today. It would be interesting to try only using the e.g. ten most recent, and therefore strongest, members of the archive as that would still make progress likely, although not guaranteed, at a much reduced CPU cost.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Using hall-of-fame archives resulted in much stronger Tic-tac-toe players than previously achieved. At first a new champion would be evolved every few generations, but after about a few dozen members in the archive the time between new champions increased, seemingly exponentially, and thus stagnated - even if I left the simulation running for weeks.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">While the evolved programs were much stronger than any I had previously evolved, they were still not as strong as I had expected. If I played certain patterns they would block well and eventually win, but they were playing far from perfectly and were still pretty easy to beat.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I was under no illusion that my search space was not huge, but I had thought that for a game as simple as Tic-tac-toe it would not be unrealistic to evolve a perfect player, so that the game would always end in a draw or a win for the AI.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I thought there must be something I could do to improve things, but didn't know exactly what; it was back to the drawing board...</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-21875830724049784822011-03-02T19:12:00.001+00:002011-03-02T19:19:51.466+00:00Coevolutionary PrinciplesBefore I continue my project log, I wanted to point you at an excellent chapter that I came across today:<br />
<br />
<a href="http://people.cs.uu.nl/dejong/publications/nchb-coev.pdf">Coevolutionary Principles (PDF)</a><br />
<br />
The chapter is an extensive overview of co-evolution and a summary of progress made in the last two decades.<br />
<br />
It is by Popovici, E., Bucci, A., Wiegand, P. and De Jong E.D. and from <a href="http://www.springer.com/computer/theoretical+computer+science/book/978-3-540-92911-6">Handbook of Natural Computing, Springer-Verlag</a>, which will be out later this month.Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-22143471546364016352011-03-01T18:19:00.006+00:002011-03-01T18:19:00.207+00:00Strategy loops<div style="text-align: justify;">After close examination of the tactics employed by the best individuals from successive generations, I noticed that strategies that were the best in early generations got superseded, as you would expect, but then reappeared several generations later!</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">While this at first was somewhat puzzling there turned out to be a logical explanation: If program x is always beaten by program y, and y by program z, then that does not mean that x cannot beat z. In practice it was more like this:</div><div style="text-align: justify;"><br />
</div><ol style="text-align: justify;"><li>program a from population A is randomly selected</li>
<li>program b from population B beats a</li>
<li>c from A beats b</li>
<li>d from B beats c</li>
<li>e from A beats d</li>
<li>f from B beats e</li>
<li>g from A beats f</li>
<li>...</li>
<li>m from A beats l</li>
<li>n, equivalent to f, from B beats m</li>
<li>repeats from step 7.</li>
</ol><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">So this was why the simulation never produced strong players.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Next, I will describe how I solved this problem, but I'd be interested to hear from you if you have any suggestions.</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-83855966581189040052011-02-27T19:14:00.000+00:002011-02-28T22:30:29.810+00:00Co-evolution<div style="text-align: justify;">The main reason for introducing co-evolution was to provide gradual selection pressure. Instead of just evolving one population against a fixed fitness measure I instead setup two populations, A and B, each initialised with random individuals. I then picked a random individual from A and evolved B until it produced a player that could beat the individual from A. This individual, now the strongest from B, was used to evolve A. Once some player from A could beat it, I swapped again and so forth:</div><div style="text-align: justify;"></div><ol style="text-align: justify;"><li>Select random individual from A, Best of A, to get things started.</li>
<li>Evolve B until it can beat Best of A and thus select Best of B.</li>
<li>Evolve A until it can beat Best of B and thus select Best of A.</li>
<li>Repeat from step 2.</li>
</ol><div style="text-align: justify;">This meant that small steps were continually taken to improve the AI and, in theory, I should have ended up with much stronger players than when evolving against Mr Random, as per my <a href="http://charlieai.blogspot.com/2011/02/rule-inference.html">previous post on rule inference</a>. That was not the case however - when playing against the best individuals it was evident that they were pretty poor, not much stronger than the ones evolved against Mr Random.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">I tried much larger populations and leaving it running for several days on more powerful PCs but to no avail, so I decided to analyse the evolution process and the individual generations in more detail...</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-16429995807709141872011-02-26T17:38:00.001+00:002011-02-28T22:30:29.810+00:00Rule inference<div style="text-align: justify;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnjnSy4r5Un9vCf24D3MaM7wxkiw7rpPC_q2nE5iQNdKIeAKjAEnKaPHPLo9x4WyzDGEaQdf-UsODLoLi5masNF5vjNiN2hoJ4nSOaliFDEmCbEfgo3QZinnsPbki6fEBeT9NXs08WIShP/s1600/tictactoe.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="190" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnjnSy4r5Un9vCf24D3MaM7wxkiw7rpPC_q2nE5iQNdKIeAKjAEnKaPHPLo9x4WyzDGEaQdf-UsODLoLi5masNF5vjNiN2hoJ4nSOaliFDEmCbEfgo3QZinnsPbki6fEBeT9NXs08WIShP/s200/tictactoe.jpg" width="200" /></a>At that point I was ready to start on the board game AI, and I decided to experiment with a Tic-tac-toe player first; once I had evolved a strong player of this game, I could then move onto more complex games. And since I was going to include only minimal game-specific code, the system would be easy to apply to other games. Individuals playing one game could even be used in evolution of players for other games.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">But how exactly do you do that? You could program a very simple individual by hand that just makes very simple, but valid, moves and then use that as the starting point for the evolution run. I decided that was not general enough and had the potential to send the search in the wrong direction, especially for more complex games like Go.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Instead I decided to just expose a function to get the status (blank, black or white) of an individual board square at position (x, y) and another to make a move at a particular square at position (x', y'). It should then be possible to evolve programs that could examine the state across the board, apply some logic, and then make a move accordingly. In the first generation of a run, all programs were initialised completely randomly.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">If a program tried to read the status outside the boundaries of the board it would just return blank, and if it tried to make a move outside the boundaries or where another piece was already placed, it would simply have no effect. The analogy is a natural environment where e.g. fish that mutate and evolve to swim into rocks simply just get stopped in their way (and ultimately die of hunger and become an extinct species). So all I was providing was a set of "laws of nature" for a game environment, in which individuals could be evolved with any conceivable strategy.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">As a fitness measure, individuals would at first play against a dumb training agent, Mr Random, which I wrote that would simply just make random valid moves. They would each play 3 times as white and 3 times as black and the proportion of games won was a direct measure of an individual's fitness.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Early generations would mostly make invalid moves, so consequently they didn't do very well, even against random play. After numerous generations, however, I observed the fittest individuals at play and, as I had hoped, they had learned to play by the rules! This was a simple side effect of only rewarding individuals that happened, by chance, to play valid moves. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">When I tried playing against the fittest individuals it did of course turn out to be very easy to beat them, as the hardest opponent they had ever met was Mr Random. Thus, the next step was to implement co-evolution...</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-38760734673198860712011-02-25T07:44:00.003+00:002011-04-04T21:40:25.814+01:00Open BEAGLE<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjf2WzcGUyzxMkbtQhWIOTNDQ9ClUrPP7ytMJuA0qfk85Lp2w3y7_H1DDNBjQLymAKTJsSJrWXCm0Ofk4qVTW7Op5VPy0fQKjDWp-m8k-qNxSpHnAs2TU_TWRam_xRl68mLjehLS9cf0tH2/s1600/bealge_logo.jpg" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjf2WzcGUyzxMkbtQhWIOTNDQ9ClUrPP7ytMJuA0qfk85Lp2w3y7_H1DDNBjQLymAKTJsSJrWXCm0Ofk4qVTW7Op5VPy0fQKjDWp-m8k-qNxSpHnAs2TU_TWRam_xRl68mLjehLS9cf0tH2/s1600/bealge_logo.jpg" /></a></div><div style="text-align: justify;">When I first started on my project, a few years ago, I decided to save time by making use of an existing tree-based GP system. I did some research into the various alternatives and by far the best framework I came across was Christian Gagné's <a href="http://beagle.sourceforge.net/">Open BEAGLE</a>. It is well-designed, flexible, easily extendable and very efficient.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">Open BEAGLE also has a <a href="http://tech.groups.yahoo.com/group/openbeagle/">Yahoo mailing list</a> offering help and support along the way.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">As an initial test of the system, and my understanding of it, I played around with symbolic and numerical regression, where the input and output to a mathematical function is known but the function itself must be evolved.</div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">All you need to do is loop over a series of input data (e.g. the integers 1 to 100), run some function (e.g. x<sup>2</sup>+x+1) on the input, store the output for fitness evaluation, and then provide only the input data to your population along with some basic operators (e.g. addition, subtraction, multiplication and division). Fitness is determined as the negated magnitude of the error when comparing an individual's output with the known output - the closer the error is to zero, the fitter the individual. Thus, if the error is exactly zero, you have a perfect fitness case. </div><div style="text-align: justify;"><br />
</div><div style="text-align: justify;">If everything works you will end up with a program that matches the function exactly, after a few generations of evolution, e.g. for x<sup>2</sup>+x+1:</div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivJTpuggCcruNNu3zKaGe5ODD1FM_0qKnBRfTMrqHmvnmmPc7M2neaIy0wwoFeuMq6moY6NYNLyIsSDzJnWLF3rYZhvzRTlLc5_WMvontHvS9ItXS9CAllhwjSyx9auzwIZf8pyOyOWhOb/s1600/individual.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEivJTpuggCcruNNu3zKaGe5ODD1FM_0qKnBRfTMrqHmvnmmPc7M2neaIy0wwoFeuMq6moY6NYNLyIsSDzJnWLF3rYZhvzRTlLc5_WMvontHvS9ItXS9CAllhwjSyx9auzwIZf8pyOyOWhOb/s320/individual.gif" width="209" /></a></div><br />
<div style="text-align: justify;">Next, I tried if this system could evolve more elaborate functions like 4x<sup>3</sup>+2x-27. I played around with how many generations were required and how large a population was necessary to get exact solutions. I also tried using a square root function without exposing a square root operator to the GP system, and was amazed when the GP system found very good approximate solutions within a few dozen generations of a few thousand individuals!</div>Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-68983666553092128402011-02-24T07:40:00.000+00:002011-02-28T22:30:29.811+00:00Introduction to genetic programmingAs a taster of genetic programming, there are some excellent slides from a course at University of Edinburgh, which covers a lot of theory behind genetic algorithms and, more specifically, genetic programming:<br />
<a href="http://www.inf.ed.ac.uk/teaching/courses/gagp/index0910.html">"Genetic Algorithms and Genetic Programming 2009-10"</a>. <br />
<br />
My favourite book on the subject is <a href="http://www.amazon.co.uk/gp/product/155860510X">"Genetic Programming: An Introduction" by Banzhaf et al.</a> It is a well-written and concise introduction that will give you a sound grounding in all the theory necessary to evolve your own GP populations.<br />
<br />
Once you are ready to either tweak existing GP systems or write your own from scratch, <a href="http://www.amazon.co.uk/Field-Guide-Genetic-Programming/dp/1409200736/ref=pd_sim_b_1">"A Field Guide to Genetic Programming" by Poli et al</a> is a priceless resource. It is also <a href="http://www.lulu.com/product/file-download/a-field-guide-to-genetic-programming/2502914">available for free as pdf</a>.<br />
<br />
After reading through these slides and books (as well as some that turned out to be less helpful), I decided on a tree-based GP approach, where the programs evolved are Lisp-like structures. Below is a simple example from a Tic-tac-toe player. The program's output, in this case, are the MAKEMOVE nodes and each node computes its value based on any subtrees it may have, including the current board state read from SQ_X_Y nodes.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEireToNo5WKiojRxjjDMYfSwSwH9LI9FgsnEz0GRbdOF6pkpBiLTqaFXIuCAELp6WBOw3qLAgh9ei4iEBdBsaKIh992434giU08-9bYEfN0OB77IYKVZqi35VFaIVFdPCZ5nb6kVacZ4bk6/s1600/individual.gif" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEireToNo5WKiojRxjjDMYfSwSwH9LI9FgsnEz0GRbdOF6pkpBiLTqaFXIuCAELp6WBOw3qLAgh9ei4iEBdBsaKIh992434giU08-9bYEfN0OB77IYKVZqi35VFaIVFdPCZ5nb6kVacZ4bk6/s400/individual.gif" width="337" /></a></div><br />
But first some more info on how I got to the stage where I could generate programs like the one above...Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-88956096597622316192011-02-23T18:39:00.000+00:002011-02-28T22:32:02.561+00:00The Blind Watchmaker<a href="http://www.amazon.co.uk/gp/product/0141026162" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgvZvbrA1RVuedS161dC2BMGufwKmmR8a0ZUivQcrAuWxkJjlwrw158CFa8REs4tbkx8mBuP-6cflHFYYOhXqIvRmogoXVjS5o5Y8df9Vx1M30X-3RWNd6hB3ywq8WWnc1FMYhFy7QvTYrR/s1600/watchmaker.jpeg" /></a>Before I move on to more technical resources, if you want to know exactly why evolution works from a biological point of view, <a href="http://www.amazon.co.uk/gp/product/0141026162">Richard Dawkins' "The Blind Watchmaker"</a> is an excellent introduction.<br />
<br />
Genetic programming is a simulation of biological evolution, and of course a simplified one, but it doesn't hurt to know how nature does it.<br />
<br />
One of the pieces from this book that proved most useful, later on in my project, is how gradual selection pressure is achieved via co-evolution of species and sub-species. More on that later on...Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com0tag:blogger.com,1999:blog-6178524460522355063.post-85697328972962939572011-02-22T18:55:00.001+00:002011-02-28T22:30:29.811+00:00The beginning...It all started with the notion that to play board games like Tic-tac-toe, Connect Four, Checkers, Chess, Shogi and Go, the strategy to play each game may not be obvious, yet there are patterns that repeat across all these games.<br />
<br />
In the case of Tic-tac-toe a simple min-max search may do well. Similarly, in Chess, if we apply min-max along with a host of extra heuristics to guide the search for the best move, we can end up with very strong play. However, for games like Go we know that the search space is too vast for a pure min-max approach to be practical.<br />
<br />
Yet, when humans play these games there are often more abstract lessons learned in one game that can be applied in others. With application-specific approaches to AI these lessons are not easily transferable from one game to another.<br />
<br />
I've always been a big fan of genetic algorithms and amazed at the novel solutions found in nature employed by Darwinian evolution. One particular variant in particular, genetic programming, where actual computer programs are evolved, is of special interest to me.<br />
<br />
As opposed to application-specific search algorithms like min-max or machine learning algorithms like neural networks for pattern recognition, genetic programming is particularly applicable when relatively little is known about the problem domain, or when very little is known about what kind of shape a good solution would take. For example, it may be that a neural network may give us a somewhat good solution but without further degrees of freedom we will never know if for example a stochastic approach combined with a neural network would give us an even better solution.<br />
<br />
Genetic programming has the potential to evolve any existing AI approach or combination of such and even to evolve brand new algorithms. In a sense genetic programming is the super set of all learning algorithms.<br />
<br />
So I decided to start a hobby project where I used a genetic programming approach to evolve computer programs that can play board games without domain-specific logic or application-specific AI.<br />
<br />
In a future post I will go into what exactly is being evolved and how the system teaches itself the rules. But for anyone just starting out with genetic programming, I will first cover some of the resources that helped me out enormously when learning about all this.Stig Petersenhttp://www.blogger.com/profile/02245544831641536759noreply@blogger.com2