Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> New idea for a bot
        
(Message started by: toby1kenobi on May 24^th, 2010, 6:36pm)

Title: New idea for a bot
Post by toby1kenobi on May 24^th, 2010, 6:36pm

I've come up with a crazy(?) idea for a bot, that I may develop if I've got time.

It's based on an economy. Each of the bot's pieces is essentially a independent thinking agent, plus there is one "economy master". The economy master decides on certain short term goals that it wants achieved, (such as freeing or capturing opponent pieces) and decides on how many "credits" it will reward for each. The economy master can also reward negative credits for unfavourable outcomes.

Next each piece thinks about how it it can move to achieve goals to earn max credits. Pieces can also offer credits to other friendly pieces to do something that helps them achieve what they want to do. For example the silver rabbit might notice that if the silver horse were to move one step to the right it would be able to move to a position where it is a goal threat. The rabbit knows that getting a goal threat is worth 1000 credits it asks the horse how much it would cost to move one step right. The horse knows that moving one step right would put it in next to an undefended trap which is awarded negative 600 credits so it tells the rabbit the cost of the move is 600 credits. The rabbit sees that in spending the 600 credits it can earn 1000 so the total profit would be 400 credits for that sequence of steps.

Each piece then reports back to the economy master what are the steps that get max credit for each of: 1 step, 2 steps, 3 steps and 4 steps. The economy master then chooses the combination of these that get the max credits. For example a rabbit might say it can earn 400 credits with a 4 step sequence or 250 credits with a 2 step sequence, and a dog says it can earn 300 with a 2 step sequence. The economy master would take the two step sequence from the rabbit and the 2 step sequence from the dog (total: 550 credits) rather than the 4 step sequence from the rabbit (total 400 credits)

The whole process would have to be done X times each turn for an X ply bot (I think - on second thoughts it might not easily extend beyond 1 ply)

The advantages of this are that it would be really easy to put into parallel processing. Also it allows for some interesting pruning based on pieces, for example it might be advantageous to let the Elephant think further ahead than a rabbit, etc. This would have to be tested.

What do others think of this?

Title: Re: New idea for a bot
Post by 722caasi on May 24^th, 2010, 8:18pm

What will you do with situations of false protection, for instance, where pieces must work in concert?

Title: Re: New idea for a bot
Post by toby1kenobi on May 24^th, 2010, 9:29pm

can you give a simple example of what you mean?

Title: Re: New idea for a bot
Post by FireBorn on May 24^th, 2010, 10:02pm

An example of false protection is if the opponent has two pieces protecting a trap, and you have stronger pieces next to both of those pieces. In one turn, you can push/pull one piece onto the trap and the other piece away from the trap, scoring a capture.

I think it is a very creative idea, but I'm more concerned with the ability for economics to serve as a good model for cooperative play. For example, the economy master would have to do a lot of calculations that other bots already do just to figure out how much to pay for each move.

Title: Re: New idea for a bot
Post by rabbits on May 25^th, 2010, 1:58pm

I really like this idea. It is crazy enough that it just might work ;)

Title: Re: New idea for a bot
Post by toby1kenobi on May 25^th, 2010, 3:01pm

In the situation of false protection as in any situation where two pieces must work in concert - one piece may notice that it can capture an opposing piece by pushing it into the trap if it "pays" another piece to pull away the opponent's other piece next to the trap.

I realise this involves pieces not only thinking about what they can do, but also what other pieces can do, and so there needs to be limits set to prevent every piece from doing all the thinking for every other piece.

These would be the limits:
* For a 1 step sequence each piece can only think about where it can step to.
* For a 2 step sequence each piece is allowed to think about one of those two steps being by another piece if the other piece is equal to or weaker than itself.
* For a 3 step sequence each piece is allowed to think about one of those three steps being by another piece.
* For a 4 step sequence each piece is allowed to think about one of those four steps being by another piece stronger than itself, or two of them if the other piece is equal to or weaker than itself.

You'd still get some overlap for equal strength pieces thinking about sequences with an even number of steps, but that can be overcome by numbering the pieces.

Another problem I foresee would be that the economy master might select a combination of sequences to play that are mutually exclusive. This would have to be checked for and somehow resolved. - any help?

I am worried that the economy master would be doing a lot of thinking that may double up on thinking done by the pieces, but I haven't work out how much that would be the case.

Title: Re: New idea for a bot
Post by megajester on May 26^th, 2010, 6:45am

Maybe you could just start out with a fixed price list and worry about the economy master later. Focus on getting the pieces to talk to each other.

Title: Re: New idea for a bot
Post by Manuel on May 26^th, 2010, 11:57am

on 05/24/10 at 18:36:56, toby1kenobi wrote:

The whole process would have to be done X times each turn for an X ply bot (I think - on second thoughts it might not easily extend beyond 1 ply)

I think you should first think more about how to extend it beyond 1 ply. Otherwise it is not of much use, i am afraid.

Title: Re: New idea for a bot
Post by toby1kenobi on May 26^th, 2010, 3:43pm

on 05/26/10 at 11:57:50, Manuel wrote:

I think you should first think more about how to extend it beyond 1 ply. Otherwise it is not of much use, i am afraid.

You may be right.

BTW, how is 2 ply defined anyway?
Is it thinking about what you could do on this turn and then what your opponent cud do on their turn?
Or is it thinking about what you could do on this turn and also on your next turn after your opponent has moved?
Or is it thinking about what you could do if you had 8 steps instead of 4?

Title: Re: New idea for a bot
Post by omar on May 26^th, 2010, 5:05pm

Interesting approach. I would encourage you to try it even though I don't think it will immediately be better than the conventional approach. But regardless of how it performs you should write up your results in a technical paper so that others will know what was tried and possibly try to improve on it. The current best bots are making use of about 50 years of experimentation and incremental improvements, so it make it difficult for radically new approaches to compete.

A full two ply search means to evaluate all the positions that occur after you make a move and your opponent makes a move.

Title: Re: New idea for a bot
Post by Fritzlein on May 26^th, 2010, 7:27pm

on 05/26/10 at 15:43:07, toby1kenobi wrote:

BTW, how is 2 ply defined anyway?
Is it thinking about what you could do on this turn and then what your opponent cud do on their turn?

Yes, that is two ply. One turn for each player.

I think David Fotland (bot_Bomb), who used a step-based search, started a bad habit of referring to thinking ahead 8-steps as an 8-ply search, when it should really be called a 2-ply search to be consistent with other games. I guess since bots usually finish 2 ply and often don't finish 3 ply, it is convenient to have a more fine-grained measure of search depth than "finished 2 ply but not 3 ply". To distinguish those, I recommend using steps of depth, e.g. 11 steps of search depth as opposed to 10 steps.

Title: Re: New idea for a bot
Post by Hippo on May 26^th, 2010, 11:55pm

I don't thing this approach would be much successful. There are big dependencies among the pieces goals and their synchronisation problem would be almost as difficult as "standard search".

But I could be wrong. Try it and report the results.

Title: Re: New idea for a bot
Post by rbarreira on May 30^th, 2010, 11:07am

If I've learned anything from trying to design new algorithms it is that an apparently good idea can have very simple and basic flaws.

So when you have a new idea which is not quick to implement, you should think about simple cases and prove whether your idea would work or not for those. In this case I think you should think about a few simple endgames, and see if your algorithm would be able to solve them or not.

On the other hand, if the idea is easy/quick to implement, you might as well try it without much preliminary testing and in the end, you could even find out that it might be useful with a few changes.