|
||||||
|
Title: Evolving a bot Post by FireBorn on Oct 27th, 2009, 11:25am Hi guys, My name is Ken. I'm going to use genetic programming to evolve a bot. I couldn't get matchoffline to work in windows or osx (and I don't have linux), so I hope you don't mind if I use the gameroom to have a pair of bots (that represent any given pair of individuals in a population) play matches against each other over and over again. I have registered two bots, bot_Natural and bot_Selection ;), to serve this purpose. Anyway, I just felt that I should introduce myself and my bot(s). I'll post any updates in here as well. So far I think I have a handle on how I'm going to go about it, but if I run into problems I'll ask for help :) Thanks, Ken |
||||||
|
Title: Re: Evolving a bot Post by Simon on Oct 27th, 2009, 11:51am So the selection is based on victories I imagine? That could take an awful lot of games depending on the sorts of things you're selecting. If you're just tweaking some parameters in an eval function it might not be so bad. Anyway, I imagine that it probably isn't too much strain on the server so long as the bots themselves are on your computer, though I don't really know, perhaps the server takes more resources than I would guess to host a game. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Oct 27th, 2009, 1:47pm Yes, the fitness function will be based on game outcome eventually. But first I have to teach the bots how to make moves and do basic things like push/pull and trap pieces, etc., so those will probably need fitness functions of their own. So yes, it could take very many games before a respectable bot emerges, but I have some ideas about how to speed up the evolutionary process. One thing I am worried about, though, is swamping the games archive with a lot of bad games. Any suggestions? |
||||||
|
Title: Re: Evolving a bot Post by Fritzlein on Oct 27th, 2009, 2:08pm on 10/27/09 at 13:47:49, FireBorn wrote:
If you make the games unrated, they are excluded by people querying to find, for example, piece values or Gold advantage. Therefore, it would be a courtesy for you to make all your evolutionary games unrated. How fast are your bots going to move? If they are supposed to move super-fast, the delay of going through the server would be intolerable to you anyway. But if you are thinking 15 seconds/move, 45 moves/game, around the clock, it comes to 64 games/day. Omar used to host 100 games/day of bots playing each other where both bots were running on the server, so less than that will hardly be a swamp. Good luck on evolution. So far there is only one developer (haizhi) I am aware of who actually evolved an evaluation function (as opposed to just talking about it), and he reported that his evaluation got worse as it departed from the hand-tuned start! |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Oct 27th, 2009, 3:21pm Thanks, Fritzlein. The bots should evolve to move as fast as possible. And they will be playing under the official time control the entire time. How long the games last depends on a lot of things, but I think its fair to say that early generations would (should) go through games faster than later ones. I don't want to evolve an evaluation function specifically. Instead, I want to let the bots come up with their own internal representation of the game. |
||||||
|
Title: Re: Evolving a bot Post by nycavri on Oct 28th, 2009, 11:10am Fascinating. Keep us posted . . . |
||||||
|
Title: Re: Evolving a bot Post by SpeedRazor on Oct 28th, 2009, 3:25pm Yeah, what nycavri said... Strangely, I'm rooting for the humans, AND the AI software - (as Omar's original intent) - evenly. Either way, I figure, humankind can't lose ... plus that's a pretty big check. Good Luck, FireBorn! Off topic (or is it?). I would Hate to see Omar Syed go bankrupt if some genuis fulfilled the requirement before 2020, because of the worldwide bad economy. Weird question: has the prize money been insured? (This has the potential of saving money.) Let me elaborate: an British radio station wagered $1,000,000 if somebody could prove the existence of the Loch Ness Monster - Period. They didn't have the One Million Dollars, so they went to Loyd's of London, who insured them - fools! - in perpetuity, for $1,000. (Suckers! 'Nessie Lives!) Has Omar done the same, seeing how Arimaa isn't likely to be beaten by brute force - even with a modified Moore's Law - but might by AI? Just curious... |
||||||
|
Title: Re: Evolving a bot Post by chimaera on Oct 29th, 2009, 2:18pm Hi Fireborn, I have a fully working Arimaa engine written in C#, which can be run both with and without a GUI (there is a rudimentary working GUI). The engine understands all the rules of Arimaa, including winning conditions, same-turn game position repeat, and the three-repeat rule. It can generate and spit out a list of legal moves, and has an easy-to-use API for setting up and playing a game. I can go through an entire 5MB game archive file, playing thousands of games, in a few seconds. I'm just waiting on a license from Omar and I'll release my Arimaa engine. You may want to wait and see if you can just plug your two bots into my game engine. It will certainly go a lot faster and be more reliable if all the action is happening on your own PC. |
||||||
|
Title: Re: Evolving a bot Post by omar on Oct 29th, 2009, 2:50pm Nice to see someone trying to evolve a bot. At first it will feel as if you are taking a step back compared to the performance of the hand-tuned bots, but I think in the long run this approach should prevail. To run games offline I would suggest using the Arimaa Engine Interface which Janzert has developed. You can find it here: https://launchpad.net/aei Actually you can also use it to interface the bot to the gameroom. This reminds me I need to update the pages to mention AEI as the recommended interface. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Oct 29th, 2009, 3:33pm Chimaera, that sounds EXACTLY like what I need. Please let me know when it's ready. Omar, thanks for the link. I'll look into it. And, by the way, this is a great game you've come up with :) |
||||||
|
Title: Re: Evolving a bot Post by SpeedRazor on Oct 29th, 2009, 4:39pm Strange, how the 2000 game called Breakthrough is so similar to Arimaa. Omar, did you or your son know about it? Personally, I think not; but than I'm led to believe Aamir invented half of this game. Is that true too? |
||||||
|
Title: Re: Evolving a bot Post by Fritzlein on Oct 29th, 2009, 6:54pm on 10/29/09 at 16:39:46, SpeedRazor wrote:
So similar? OK, it's on an 8x8 board and the objective of reaching the other side is the same, but the pieces are different, the movement is different, the number of moves is different, capturing is different, freezing is different, and dislodgement of pieces is different. With the thousands and thousands of games out there, I'm amazed you couldn't come up with something closer for Arimaa to be "so similar" to. |
||||||
|
Title: Re: Evolving a bot Post by omar on Nov 5th, 2009, 8:17am on 10/29/09 at 16:39:46, SpeedRazor wrote:
No I didn't know about Breakthrough. Most of the mechanics used in Arimaa were play tested during 1999. Aamir's main contribution was with helping to name the game and being the inspiration and catalyst for getting me to work on it again after I had given up. You can read more about it here: http://arimaa.com/arimaa/about/ |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Mar 18th, 2010, 9:26am An update. So I've been doing a lot of research trying to decide what programming paradigm to have the individuals in the population (bots) use. I'm trying to decide between imperative, functional, or rule-based (expert system, logical + functional). Originally, genetic programming was done using functional languages, presumably because they are the simplest to implement. However, an imperative language seems to have the advantage of having "junk DNA" (code that doesn't get executed, but may be enabled via mutation) and state, which could save on valuable thinking time by keeping state between moves. But just recently I started researching logical languages and rule-based languages, and they seem very appropriate for representing strategy and tactics in a more direct way. I'm leaning towards using a rule-based language, but any insights on the matter would be much appreciated :) |
||||||
|
Title: Re: Evolving a bot Post by omar on Mar 27th, 2010, 7:08am Ken, how about some links to some of the languages you are considering. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Mar 28th, 2010, 1:04am Sure Well, now that I think about it, I could probably use Python for either functional or imperative genetic programming. As for rule-based, I was looking into Jess: http://www.jessrules.com/ I couldn't find many articles about using a rule-based language for genetic programming, but I think it would fit well for evolving a game-playing bot. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Mar 30th, 2010, 10:48am Hehe: http://imgs.xkcd.com/comics/recipes.png src: http://www.xkcd.com/720/ |
||||||
|
Title: Re: Evolving a bot Post by starjots on Mar 30th, 2010, 7:30pm Why don't you write one program that contains both bots - or however you define it, and let them play each other in your computer. You would get many generational iterations. This is the approach I'm taking, although at this point I'm just starting a move generator, so its premature to claim call it much of an effort yet. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Mar 30th, 2010, 11:15pm Yes, actually, that's what I'm going to do now that I have Chimaera. Are you evolving a bot too? |
||||||
|
Title: Re: Evolving a bot Post by starjots on Mar 31st, 2010, 9:39am Yes, I *hope* to evolve a family of bots. Ten years ago I did a hobby project with what I would call GAs in a subsumption architecture for simple robotics using a C derivative language. The results were very cool and I've been looking for hobby projects to try this sort of approach ever since. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Mar 31st, 2010, 10:46am Cool. I did a similar hobby project a couple years ago using GP on my own artificial-life version of the snake game (huge field, lots of apples, and lots of snakes that could grow and reproduce) and a language called Brainf**k (consisting of 8 commands, turing machine-like). The snakes didn't evolve very well but there was at least speciation, meaning some solutions worked better than others and were being selected for. Ever since then I'd been looking for another game to apply GP to |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Jun 15th, 2010, 4:55pm An update on this: The system is built and running using the Push language and Chimaera (with some tweaks pending). So far I have evolved individuals that can make the setup move, which is not saying much given all the help I've given them to do it (basically, the way I've set it up, a code-less bot would make the setup move fine, and in fact, the more code it has the more likely it is to submit an illegal first move, lol). The next big evolutionary hurdle is to make the first non-setup move, which consists of choosing a piece by coordinates and choosing a direction (the piece type is discovered automatically and trap steps are automatically added to the move string), 1+ times. In order to make a valid 2nd move, an individual would have to:
So as you can see, it is not a small hurdle to pass in one evolutionary leap, and I'll probably have to do some tweaking to make this hurdle easier for the individuals. I'll keep you updated on their progress. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Jun 22nd, 2010, 9:21am Success! So far... In order to get around the previous problem of requiring the individuals to figure out whether or not they were in a setup move, I simply split each individual into two programs. The first program handles the setup move, and the second program handles every move afterwards. They can be thought of as 2 separate chromosomes, or separate genes, in a single individual. Now I am getting individuals that can make more than 2 moves! Some are even making unique setup moves, but these probably won't be selected for/against until a complete game can be made without making illegal moves. The default setup move is: Code:
If you'll notice, this is just about the worst setup move possible, and that's on purpose. This way, if an individual swaps any two pieces, it is likely to improve the position, allowing the population to more completely explore the space of possible setup moves. If an individual submits an illegal move, it loses. To make it easier on the individuals, I made it so they only need to specify a piece (by ID#) and the direction to move it, in order to make a move. Individuals that survive to make the most moves tend to make single-step moves that move rabbits forward until an illegal move is made due to the destination square being occupied. Thus, the next evolutionary challenge for these individuals is to figure out how to avoid stepping onto occupied squares and/or how to push and pull, then hopefully eventually figure out how to trap pieces. The longest game I've seen them play so far ended something like this: Code:
..before an illegal move was made. Pretty exciting lol :) |
||||||
|
Title: Re: Evolving a bot Post by rbarreira on Jun 22nd, 2010, 9:42am Very nice, this may be the farthest anyone has come in developing an evolutionary bot ? |
||||||
|
Title: Re: Evolving a bot Post by starjots on Jun 22nd, 2010, 10:16am This is indeed interesting - so you are making the bots actually learn the rules of the game? that's pretty cool! |
||||||
|
Title: Re: Evolving a bot Post by omar on Jun 26th, 2010, 5:30am Nice work FireBorn. It would have been easier to just evolve the evaluation function, but what you are doing with evolving the move generator as well is more general. Keep us posted on how it goes. |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Jun 27th, 2010, 1:35pm Okay, the individuals still haven't figured out how to assess steps before making them and are still making illegal moves by attempting to move pieces onto occupied squares. The closest I saw one get was to correctly push a camel, but it didn't complete the push by moving the elephant, so it died and its genes were lost. I think it's just too big of an evolutionary step to ask for (i.e. it will take forever for a random mutation to correctly implement this perceptive ability). So what I'm going to do is implement bitboards that the individuals can manipulate. This should make it a lot easier for them to figure out what's going on on the board. Also, they can probably use the bitboards for more complex calculations in the future. The reason I didn't want to evolve just an evaluation function is because I thought there might be a more efficient way to assess positions and make good moves besides using an evaluation function, like how humans use heuristics. |
||||||
|
Title: Re: Evolving a bot Post by Fritzlein on Jun 27th, 2010, 11:57pm on 06/26/10 at 05:30:05, omar wrote:
As long as we are talking about what is an easier way to approach the problem, it is easier to just hand code an evaluation function rather than evolving anything. Traditional chess-inspired approaches to Arimaa have worked best so far, and you yourself admit that anything else is likely to perform worse at first. You expect that trying something different means we will have to take a step backwards before we can make a leap forward. But in this thread Fireborn is taking AI truly to heart and you say, in effect, "I didn't mean for you to take three steps backwards; I only wanted you to take one step backwards!" :) My fondest wish for the Arimaa Challenge is that it will go unclaimed until 2020, at which point a corporate sponsor will step in and make it a million dollar challenge until 2030. Then, when it is no longer your money on the line, I expect you to roll up you sleeves and code your own Arimaa AI. The one defect of the Arimaa Challenge, Omar, is that you can't win it yourself. I am dying with curiosity to know what methods your bot would use if you could direct your efforts towards that instead of towards supporting and promoting Arimaa. Knowing you, you would tinker with all sorts of different approaches rather than getting stuck on any one thing, and would somehow intuitively stir up a witches' brew of various methods that would miraculously bag the million dollar prize for yourself. |
||||||
|
Title: Re: Evolving a bot Post by rbarreira on Jun 28th, 2010, 12:26am My intuition is that a purely evolutionary bot would have to learn from the database of played games in order to reach a good level. Even with a good learning algorithm, I don't think anyone here has access to the computational power that can learn everything humans have learned about Arimaa in so many years, without taking advantage of the results of those humans. That is of course unless someone implements a strong AI (i.e. human-equivalent) which can read everything humans wrote about Arimaa and build on that. But that's not something we can realistically expect someone to achieve in the context of trying to win the Arimaa challenge. Regarding Omar's / Fritzlein's posts I think a good evaluation function is all you need to have a good evolutionary bot. I'm pretty sure that what humans do to play Arimaa can be modelled as tree search plus an evaluation function, as long as we allow the evaluation function to include dynamic weighing of different features throughout the game (which I think any reasonable definition of evaluation function already does). |
||||||
|
Title: Re: Evolving a bot Post by FireBorn on Jun 28th, 2010, 9:40am on 06/28/10 at 00:26:42, rbarreira wrote:
I thought about this too. But the only problem with this approach is figuring out what the fitness function would be for these individuals. Should bots (a.k.a. "individuals") that make moves that the humans made in the game be rewarded a higher fitness? But different people play differently, so the bots wouldn't be able to make the "correct" choice every time. At best, you would evolve a bot that would be able to play like a human, which won't win the challenge anyway. IMO, the strength of genetic programming is its ability to evolve a program that has leveraged its computational nature to its fullest extent, not being held back by things like code readability, structure, or human logical limitations. In other words, I think they should play like computers, not humans. Quote:
If they play hundreds or thousands of games a day, they might be able to get there :) Quote:
That might be one way to go, but I don't want to miss out on potentially good moves by manually choosing the order in which potential moves are evaluated, so I would have to let that "move choosing" function evolve as well. Hmmm...I just realized I'm doing a bottom-up approach, and you're recommending a top-down approach. But I don't think they are mutually exclusive. I might just end up doing both and meeting in the middle. Thanks for the idea |
||||||
|
Title: Re: Evolving a bot Post by thomastanck on Apr 10th, 2011, 7:03am Hey, I think you should try to evolve neural networks though, neural networks are usually better than rule-based ones. Here are a couple links for you to start out: http://en.wikipedia.org/wiki/Artificial_neural_network http://www.youtube.com/watch?v=oU9r64tc7yE Neural networks may take longer to evolve though, I am not very sure myself, but I think you should consider neural networks. |
||||||
|
Title: Genetic ramblings - Very long winded - Post by Quirky1 on Dec 28th, 2011, 9:29pm Is this thread dead or is there some development in this area still going on? --- Here is a question or three and some ramblings, feel free to ignore --- I have a basic question regarding this. How do you make the code mutate? A problem with an answer composed of a known number of parameters you can test, evolve and use a fitness function on, is that you "only" end up fine tuning the order of moves or the values for all the ingoing parameters. But how do you use this against an active opponent and not only a static (or at least predictable with a finite number of possible states) environment? If you had a very large well defined library of good potential rules and a way of prioritizing between them, I guess that priority order could be evolved. But some one has to come up with those rules and hard code them, before we can optimize/evolve the prioritizing order of them, right? I don't under stand how the AI should be able to evolve "new" rules, or strange (out of the box non human) ways of thinking or using hard to follow code?!? Am I missing something basic in Genetic Programming or evolutionary programming? I guess it could be theoretically possible to develop some sort of frame work for coming up with random rules based on a limited (but still quite complex) world like Arimaa and representing those rules in a genetic/binary form. But the work needed would be staggering since there are so many possible types of rules that could (and probably should, if we are to reach a good level of AI) be used. We would need positional rules, material rules, historical rules and most daunting of all - combinatorial rules like; if piece x and piece y are positioned in one of these (n positions) we could respond with this specific move. The combinations of not only specific rules, but also on the types of rules are daunting to say the least. And the memory needed to keep the useless, redundant and obsolete rules "alive" until they are removed by natural selection must be staggering. We really need to have some sort of computational cost in the fitness function, preferably in the meta frame work for every rule, that keeps track how often that rule is actually used, so we can remove dead weight genetically speaking. I still can't wrap my head around this genetical programming in this particular problem domain (Arimaa feels way to complex for this). Maybe if we were limiting the genetical part to an evaluation function, with some goal part, some material gain part and a positional part, with a number of variables for each. And then were planning on letting the genetics find the perfect variant of that evaluation function. That would be doable I guess, but then the answer would be really predictable, since the evaluation function it self would be the real AI part (actually the whole bot) and the fine tuning would only be the finishing touch. But such a bot would never be able to evolve outside that functions parameters or take anything beyond the scope of that specific function into account? And if that, more practical, approach is chosen, why would the bot need to learn how to move the pieces? That should be hard coded in the search tree and evaluation function from the start. In short, I'm amazed you even got the pieces to move more than once and my guess is that you had to hard code that pretty hard. I can see a toddler trying to play chess, getting cattle prodded hard enough to cause amnesia each time he does a wrong move and from that expect him to learn and develop new complex strategies. In short are we expecting too much from this approach or is my knowledge of GP waaaay too shallow and I should shut up and read up on the subject first? The idea is so cool and I really want it to be plausible, but is it? Is there any of the bots that are learning anything new or are they just adjusting some of the parameters in the evaluation function based on statistics from earlier experience or from the game database? ??? What would be interesting though is to create a framework for testing existing bots genetically. Each bot would take a certain amount of in parameters for each material weight constant, for each positional weight constant and maybe some parameters for prioritizing between certain rules when they are in conflict. Maybe the likelyhood of a random non optimal move in order to be non deterministic also could be an in parameter. This particular parameter setup will be the specific genetic code for that type of bot. The framework would then keep track of the different individuals (and their particular set up of constants - dna), their mutations and natural selection will come from playing the original bot (with the constants set to humanly defined optima), then a series of other normal bots, and maybe against the other genetically evolved individuals. Such a frame work should be usefull to all bots and when you start up the frame work, the inparameters should be the definition and numbers of the parameters (dna) the current bot to be tested should use. The frame work doesn't need to differentiate between the parameters, it only needs to know how many, type and lower and upper bounds (but that could be set to to a standard 0.0-1.0 and the bot will hagve to convert it to an appropriate number before the constants are set internally) I assume that today the bots are tested in some sort of frame works (I am very new to this site), but the tuning of the evaluation functions are done manually. Where the coders tweak the rules as well as the constants? Or do we already have a framework for helping with the fine tuning aswell? I read some other post on the relative value of a rabbit and a cat and how the relative value changes over time. In this frame work that relative value would need at least two genes/inparamters, one for the value and one for the change coefficient. The new thing here would be that all bots are not created equal, so there are no subjective answer to the relative value of the two pieces. One bot might be really good at moving rabbits and using them for support all over the place, while the other bot is a cat expert. One is aggressive and seldom runs out of rabbits, while the other plays a slow attrition game whit many exchanges so it almost always comes down to the number of rabbits in the end. With a "genetics" inspired approach one could find a good tuning of the constants for each individual bot and not have to do with the common sense of the forum, statistics from played games in the database or objective truths. In short why value a piece for it's ability to set up an elephant blockade, if your bot doesn't know how to set up one to begin with? One might also consider splitting an evaluation function in two, one for the oponent with one set of constants and one for the bot it self. It means more genes to keep track of, but you can value the bots rabbits in one way and the generic opponent's in another. And the current bots wouldn't need to be reprogrammed in a major way. With one more in parameter, a wraper to recieve the inparameter and set the constant to be tested would be all that is needed to get started. Then the number of constants that gets optimized by the framework could be increased one at a time. It's late and I got a taaaaad long winded, sorry about the ramblings. :) |
||||||
|
Title: Re: Evolving a bot Post by dht on Oct 17th, 2013, 7:06am http://arimaa.com/arimaa/gameroom/comments.cgi?gid=278748 ?? |
||||||
|
Title: Re: Evolving a bot Post by Fritzlein on Oct 17th, 2013, 10:57am How to spot a genetic algorithm... |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |