Author |
Topic: Evolving a bot (Read 8718 times) |
|
FireBorn
Forum Guru
Arimaa player #1832
Gender: 
Posts: 123
|
 |
Re: Evolving a bot
« Reply #15 on: Mar 28th, 2010, 1:04am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #16 on: Mar 30th, 2010, 10:48am » |
Quote Modify
|
Hehe:
src: http://www.xkcd.com/720/
|
| « Last Edit: Mar 30th, 2010, 10:48am by FireBorn » |
IP Logged |
|
|
|
starjots
Forum Full Member
Arimaa player #5147
Gender:
Posts: 20
|
|
Re: Evolving a bot
« Reply #17 on: Mar 30th, 2010, 7:30pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #18 on: Mar 30th, 2010, 11:15pm » |
Quote Modify
|
Yes, actually, that's what I'm going to do now that I have Chimaera. Are you evolving a bot too?
|
|
IP Logged |
|
|
|
starjots
Forum Full Member
Arimaa player #5147
Gender:
Posts: 20
|
|
Re: Evolving a bot
« Reply #19 on: Mar 31st, 2010, 9:39am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #20 on: Mar 31st, 2010, 10:46am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #21 on: Jun 15th, 2010, 4:55pm » |
Quote Modify
|
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:
- determine if the current move is a setup move or not (by move number), in order not to break its setup move. This involves comparisons and control flow code.
- determine its color (I'm considering a tweak to remove this requirement)
- find the coordinates of one of its own pieces on the board (initially it would probably evolve to have one of the squares that we know contains a piece from the setup move "hardcoded" into it rather than dynamically selected)
- and it would have to pick a valid direction to move it in.
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #22 on: Jun 22nd, 2010, 9:21am » |
Quote Modify
|
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:
R R R R R R R R
E M H H D D C C
|
|
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:
c c d d h h m e
r r r . . . . .
. . x . . x . .
R R R r r r r r
. . . R R R . .
. . x . . x . .
. . . . . . R R
E M H H D D C C
|
|
..before an illegal move was made.
Pretty exciting lol 
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Evolving a bot
« Reply #23 on: Jun 22nd, 2010, 9:42am » |
Quote Modify
|
Very nice, this may be the farthest anyone has come in developing an evolutionary bot ?
|
|
IP Logged |
|
|
|
starjots
Forum Full Member
Arimaa player #5147
Gender:
Posts: 20
|
|
Re: Evolving a bot
« Reply #24 on: Jun 22nd, 2010, 10:16am » |
Quote Modify
|
This is indeed interesting - so you are making the bots actually learn the rules of the game? that's pretty cool!
|
| « Last Edit: Jun 22nd, 2010, 10:18am by starjots » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Evolving a bot
« Reply #25 on: Jun 26th, 2010, 5:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #26 on: Jun 27th, 2010, 1:35pm » |
Quote Modify
|
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.
|
| « Last Edit: Jun 27th, 2010, 1:43pm by FireBorn » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Evolving a bot
« Reply #27 on: Jun 27th, 2010, 11:57pm » |
Quote Modify
|
on Jun 26th, 2010, 5:30am, omar wrote:| It would have been easier to just evolve the evaluation function |
|
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.
|
| « Last Edit: Jun 27th, 2010, 11:59pm by Fritzlein » |
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Evolving a bot
« Reply #28 on: Jun 28th, 2010, 12:26am » |
Quote Modify
|
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).
|
| « Last Edit: Jun 28th, 2010, 12:30am by rbarreira » |
IP Logged |
|
|
|
FireBorn
Forum Guru
Arimaa player #1832
Gender:
Posts: 123
|
|
Re: Evolving a bot
« Reply #29 on: Jun 28th, 2010, 9:40am » |
Quote Modify
|
on Jun 28th, 2010, 12:26am, rbarreira wrote:| 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. |
|
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:| 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. |
|
If they play hundreds or thousands of games a day, they might be able to get there
Quote:| 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). |
|
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
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print