Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Public Domain bot code
        
(Message started by: omar on May 27^th, 2004, 12:05am)

Title: Public Domain bot code
Post by omar on May 27^th, 2004, 12:05am

Many thanks to Don Dailey who has contributed a sample Arimaa bot written in C. It is available in the Download section. It provides a good starting point for anyone wanting to get started with creating their own bot, but are not too familiar with writting game programs.

Omar

Title: Re: Public Domain bot code
Post by 99of9 on Jun 29^th, 2004, 5:35pm

I can confirm that it's pretty good!

I've found 3 bugs in it, so don't download until Don submits a revised version. But I can say that the corrected version plays pretty well, similar to arimaazilla and better than Gnobot (after searching for equivalent times to each of them).

Omar I've got one request and one gripe.

The request: is there any chance of getting the 2004CC Occam online like the other two? It would be at a nice level to test this new bot against.

The gripe: the arimaa scoring function is terrible!! I think it WAY overvalues advanced rabbits. Have a look at the game bot_firsttry played against bot_Gnobot2004CC. That game was decided by score after 8 hours (fair enough!), but the wrong bot was given the game as far as I'm concerned. Firsttry had only lost one dog. Gnobby on the other hand had only 4 pieces left... elephant, camel and 2 advanced rabbits.

Ok sure, we could all program our bots to push the opposing rabbits back when we get to 7 hours and 50 minutes... but that would just be silly, and counter to the idea of developing great game playing ai. Instead I think you should change the scoring function (a lot). I understand that it's good to incentivise pushing rabbits forward, because it gets the game going... but I think this amount is excessive, and I don't think any of the current bots are deliberately trying to play silly stalemate arimaa.

If that result had happened in the bot championships I would be pretty annoyed! (no matter which bots it was that were playing) What do other people think?

Title: Re: Public Domain bot code
Post by Haxe on Jul 9^th, 2004, 9:49am

Omar has once made the very good suggestion to simply give the win to the player with the most time left instead of evaluating to position. As he pointed out, this will not only be more fair than an arbitrary evaluation, but will probably also influence the behaviour of the players so that games are less likely to be ended by time at all.

I think this would be really great. Please give it a second thought, and, if applicable, introduce this new rule as soon as possible, before people get used to the scoring thing.

Title: Re: Public Domain bot code
Post by omar on Aug 14^th, 2004, 4:37pm

Hi Toby,

Can you email me the version of the code where
you have fixed the bugs. I will make that available.

Occam2004CC was not statically linked and so it
runs only on Linux v9; but I don't have
that system anymore. I checked with Don and
did not save the source of Occam2004CC and
has since modified it. If someone has v9 I can
provide the binary. Or eventually I will be moving
the arimaa.com site to a newer system and at that
time will be able to run it.

I will start a new topic to discuss the Arimaa
scoring function.

Omar

Title: Re: Public Domain bot code
Post by 99of9 on Aug 16^th, 2004, 8:08am

Hmm, I don't think I still have that version. Basically I've just kept developing it and just let Don know of the bugs at the time. I'll have a better look later.

Title: Re: Public Domain bot code
Post by omar on Aug 16^th, 2004, 10:17pm

If you could find that email you sent to Don and recall
what the bugs were I could try to fix it and post a new
version.

Omar

Title: Re: Public Domain bot code
Post by 99of9 on Aug 21^st, 2004, 7:18am

Hi Omar,

Here's a list of the 3 changes I suggested, and Don's responses. The first two are easy to correct, the third should perhaps be left as an excercise for the reader? :-)

Anyway, here are the bugs:

#1) (HUGE bug)
Toby Says:
In the function: begin_search
It should return cur_main instead of main_line

Don Says:Good catch, I think you are right!

The basic idea is that main_line can't be trusted if the search was aborted, that's why I keep track of cur_main which is the last one known to be good! But then after all that bookeeping we returned main_line anyway. Woops!

#2) (TINY bug)
Toby Says: One more teeny bug:

u64 adv[8][2] =
{ {0xff00000000000000ULL, 0x00000000000000ffULL},
{0x00ff000000000000ULL, 0x000000000000ff00ULL},
{0x0000ff0000000000ULL, 0x0000000000ff00ffULL},
{0x000000ff00000000ULL, 0x00000000ff000000ULL},
{0x00000000ff000000ULL, 0x000000ff00000000ULL},
{0x0000000000ff0000ULL, 0x0000ff0000000000ULL},
{0x000000000000ff00ULL, 0x00ff000000000000ULL},
{0x00000000000000ffULL,0xff00000000000000ULL];

Notice that in the 3rd line, 2nd column, you have ff occurring twice in the string. Just a copy-paste error I'd say. I think this caused the one loss against arimaazilla.

Don Says:I told you there were probably other bugs!

In computer chess it's well known that program bugs are a major factor in the stength and success of your program. You have discovered 2 bugs, both of which probably caused lost games!

#3) (Big Bug)
Toby Says:
I found one more bug, but it's much more subtle than the other ones:

(and it's not a bug that could ever occur in computer chess!)

It's to do with iterative deepening and complex moves (pushes or pulls... those that take 2 steps).

Imagine this situation:
You're leading by far, and find a good depth 4 (steps) search. Then you try a depth 5 search, and find that there's a way in 4 steps of blocking all the opponent's pieces in, so that it is impossible for him to make any
SINGLE step reply. That depth 5 search then returns a GAME WON value, so you don't bother searching any further. The problem is, it's possible that although the opponent doesn't have any single step replies, he may well have some 2 step replies (eg pushing the pieces surrounding his elephant).
If we'd searched to depth 6 we would have found these!

I found this because it actually happened in a game against arimaazilla - and arimaazilla won because of it!!!

(In theory I think it's also possible to set up a situation where your opponent cannot make any moves of length 1, 2, or 3, but does have a move of length 4. This occurs when you force him to push your rabbit onto the win line, and then pull it back off in the same move. But I think this situation is so rare that a bot playing to win would never construct
such a situation.)

As far as fixing it goes: I've got a 4 line fix, but it only works for the 2 step case, not the 4 step case - and it really is a hack (you end up doing searches with -1 depth... hmm...) I can send it to you if you like - but I think you'd probably prefer to fix it more elegantly, in line with the rest of the code.

Don Says:
There needs to be a test at the exact point where the program wants to score a loss for not having a possible move. If this is the first step for one side, the program should just call the evaluator instead of scoring a loss. OR you could in this one case call the 2 step generators just to see if there is at least 1 two step move possible. If not, score the loss, if so call the evaluator.

The only thing this wouldn't handle is the bizarre 4 move case, which is truly bizarre and I think can be ignored. (I can see it now, one of is playing for the 10,000 dollar challenge and winning, then the 4 step case comes up and we throw the game! )

Title: Re: Public Domain bot code
Post by omar on Aug 26^th, 2004, 7:32pm

Thanks for posting this Toby. I fixed the first two bugs and made a README file for the third one. I uploaded the new version to the downloads area. So it should OK now for
people to start using.

Omar

Title: Re: Public Domain bot code
Post by 99of9 on Aug 27^th, 2004, 5:59am

Yes, I think with that first bug fixed people can already start playing with their evaluation functions and producing pretty nice bots. Unless they make the changes required for bug 3 they will of course come across occasional blunders when smothering the opponent is a possibility.

Title: Re: Public Domain bot code
Post by BlackKnight on Aug 31^st, 2004, 7:11am

I guess a quite tiny bug:
for (i=6; i>0; i++) // should be i--
if (p->bd[e][i])
{
be = i;
break;
}
in the evaluation function.
But if the opponent "e" doesn't have an elephant anymore for some reason, the program might cause some problem (will loop forever??).

Gerhard

Title: Re: Public Domain bot code
Post by 99of9 on Aug 31^st, 2004, 6:43pm

Well spotted, I hadn't seen that one.

I don't think it would loop forever because it is checking memory locations outside the array, so would soon find a non-zero one.

But definitely a good bug to remove!

Title: Re: Public Domain bot code
Post by 99of9 on Aug 31^st, 2004, 6:46pm

By the way, anyone who has played Firsttry in the last few months - I found another bug in it today (smallish), one that I'd stupidly introduced. I don't think it'll play that differently, but if you notice any difference in play, it may be due to that.

I'm also experimenting with some different parametrization of my eval function - you can get amazingly different bots with just a little tweaking!

Title: Re: Public Domain bot code
Post by omar on Sep 21^st, 2004, 4:26pm

Thanks for posting that BlackKnight. I just fixed it in the code.