Welcome, Guest. Please Login or Register.
Dec 4th, 2024, 9:10am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Evolving a bot »


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Evolving a bot
« Previous topic | Next topic »
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Evolving a bot  (Read 8973 times)
FireBorn
Forum Guru
*****



Arimaa player #1832

   


Gender: male
Posts: 123
Evolving a bot
« on: Oct 27th, 2009, 11:25am »
Quote Quote Modify 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 Wink, 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 Smiley
 
Thanks,
Ken
IP Logged
Simon
Forum Guru
*****



Arimaa player #1198

   


Gender: male
Posts: 125
Re: Evolving a bot
« Reply #1 on: Oct 27th, 2009, 11:51am »
Quote Quote Modify 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: male
Posts: 123
Re: Evolving a bot
« Reply #2 on: Oct 27th, 2009, 1:47pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Evolving a bot
« Reply #3 on: Oct 27th, 2009, 2:08pm »
Quote Quote Modify 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: male
Posts: 123
Re: Evolving a bot
« Reply #4 on: Oct 27th, 2009, 3:21pm »
Quote Quote Modify 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: male
Posts: 44
Re: Evolving a bot
« Reply #5 on: Oct 28th, 2009, 11:10am »
Quote Quote Modify Modify

Fascinating.  Keep us posted . . .
IP Logged
SpeedRazor
Forum Guru
*****




Skepticism is the Immune System of Science

   
Email

Gender: male
Posts: 72
Re: Evolving a bot
« Reply #6 on: Oct 28th, 2009, 3:25pm »
Quote Quote Modify 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: male
Posts: 16
Re: Evolving a bot
« Reply #7 on: Oct 29th, 2009, 2:18pm »
Quote Quote Modify 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: male
Posts: 1003
Re: Evolving a bot
« Reply #8 on: Oct 29th, 2009, 2:50pm »
Quote Quote Modify 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: male
Posts: 123
Re: Evolving a bot
« Reply #9 on: Oct 29th, 2009, 3:33pm »
Quote Quote Modify 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 Smiley
IP Logged
SpeedRazor
Forum Guru
*****




Skepticism is the Immune System of Science

   
Email

Gender: male
Posts: 72
Re: Evolving a bot
« Reply #10 on: Oct 29th, 2009, 4:39pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Evolving a bot
« Reply #11 on: Oct 29th, 2009, 6:54pm »
Quote Quote Modify 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: male
Posts: 1003
Re: Evolving a bot
« Reply #12 on: Nov 5th, 2009, 8:17am »
Quote Quote Modify 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: male
Posts: 123
Re: Evolving a bot
« Reply #13 on: Mar 18th, 2010, 9:26am »
Quote Quote Modify 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 Smiley
IP Logged
omar
Forum Guru
*****



Arimaa player #2

   


Gender: male
Posts: 1003
Re: Evolving a bot
« Reply #14 on: Mar 27th, 2010, 7:08am »
Quote Quote Modify Modify

Ken, how about some links to some of the languages you are considering.
IP Logged
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.