Author |
Topic: Evolving a bot (Read 8959 times) |
|
FireBorn
Forum Guru
Arimaa player #1832
Gender: 
Posts: 123
|
 |
Evolving a bot
« on: Oct 27th, 2009, 11:25am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
Simon
Forum Guru
Arimaa player #1198
Gender:
Posts: 125
|
|
Re: Evolving a bot
« Reply #1 on: Oct 27th, 2009, 11:51am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #2 on: Oct 27th, 2009, 1:47pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Evolving a bot
« Reply #3 on: Oct 27th, 2009, 2:08pm » |
Quote Modify
|
on Oct 27th, 2009, 1:47pm, FireBorn wrote:| One thing I am worried about, though, is swamping the games archive with a lot of bad games. Any suggestions? |
|
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!
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #4 on: Oct 27th, 2009, 3:21pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
nycavri
Forum Senior Member
Arimaa player #2416
Gender:
Posts: 44
|
|
Re: Evolving a bot
« Reply #5 on: Oct 28th, 2009, 11:10am » |
Quote Modify
|
Fascinating. Keep us posted . . .
|
|
IP Logged |
|
|
|
SpeedRazor
Forum Guru
Skepticism is the Immune System of Science
Gender:
Posts: 72
|
|
Re: Evolving a bot
« Reply #6 on: Oct 28th, 2009, 3:25pm » |
Quote Modify
|
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...
|
| « Last Edit: Oct 28th, 2009, 3:52pm by SpeedRazor » |
IP Logged |
|
|
|
chimaera
Forum Full Member
Arimaa player #4560
Gender:
Posts: 16
|
|
Re: Evolving a bot
« Reply #7 on: Oct 29th, 2009, 2:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Evolving a bot
« Reply #8 on: Oct 29th, 2009, 2:50pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #9 on: Oct 29th, 2009, 3:33pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
SpeedRazor
Forum Guru
Skepticism is the Immune System of Science
Gender:
Posts: 72
|
|
Re: Evolving a bot
« Reply #10 on: Oct 29th, 2009, 4:39pm » |
Quote Modify
|
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?
|
| « Last Edit: Oct 29th, 2009, 4:49pm by SpeedRazor » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Evolving a bot
« Reply #11 on: Oct 29th, 2009, 6:54pm » |
Quote Modify
|
on Oct 29th, 2009, 4:39pm, SpeedRazor wrote:| Strange, how the 2000 game called Breakthrough is so similar to Arimaa. |
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Evolving a bot
« Reply #12 on: Nov 5th, 2009, 8:17am » |
Quote Modify
|
on Oct 29th, 2009, 4:39pm, SpeedRazor wrote:| 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? |
|
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/
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #13 on: Mar 18th, 2010, 9:26am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Evolving a bot
« Reply #14 on: Mar 27th, 2010, 7:08am » |
Quote Modify
|
Ken, how about some links to some of the languages you are considering.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print