Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> The fall of Bomb
        
(Message started by: Swynndla on May 3^rd, 2011, 11:04pm)

Title: The fall of Bomb
Post by Swynndla on May 3^rd, 2011, 11:04pm

In 2009 bot_clueless beat Bomb, and wikipedia says several bots surpassed Bomb that year. What was the reason that several bots suddenly got better than Bomb that year, ending Bombs five year reign? Was that because of some break-through?

Title: Re: The fall of Bomb
Post by 99of9 on May 4^th, 2011, 2:26am

Gnobot beat bomb by copying a game that one of the other bots played against bomb. Determinism was bomb's Achilles heel...

... but also, that was the year that many bots became parallel, and 4 processors vs 1 processor is a pretty big handicap.

Title: Re: The fall of Bomb
Post by Swynndla on May 4^th, 2011, 4:53am

99of9 - are you saying that Gnobot copied the whole game, or just an opening pitfall?

Also, are you saying that if bomb was parallelized, that it might have still been on top that year (if also maybe some randomness was introduced into bomb)? ... or I guess you're saying that at least it might not have been overtaken by so many others.

Title: Re: The fall of Bomb
Post by UruramTururam on May 4^th, 2011, 5:57am

The games:

Bomb vs Clueless: http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=98924&s=w

Bomb vs GnoBot: http://arimaa.com/arimaa/games/jsShowGame.cgi?gid=99124&s=w

An exact copy.

Title: Re: The fall of Bomb
Post by 99of9 on May 4^th, 2011, 6:27am

For Gnobot's opening book, the "opening" continues until a position has never been seen before in the games database. So as long as bomb kept following its losing path, gnobot was happy to follow as well.

It's hard to say how good a parallel bomb would play, but I'd guess that bomb would certainly have placed in the top two.

But if I remember right, Opfor was not parallel either that year, and got a win over bomb... So maybe the gradual coding of human strategic knowledge had finally overwhelmed bomb's superb design.

Title: Re: The fall of Bomb
Post by rbarreira on May 4^th, 2011, 7:25am

Actually Opfor had already beaten Bomb in one game of the 2008 computer championship. So at least Opfor gave its warning in the previous year.

Clueless seems to have greatly improved between 2008 and 2009.

Title: Re: The fall of Bomb
Post by Janzert on May 4^th, 2011, 1:02pm

To confirm the above, OpFor was not parallelized until 2010.

Also from 2006-2008 it seemed there was very little bot development going on by anybody. Since 2008 it has been great to see continual growth in the amount of development done by an ever expanding number of people.

Janzert

Title: Re: The fall of Bomb
Post by Swynndla on May 4^th, 2011, 6:21pm

Those Bomb vs Clueless & Bomb vs GnoBot games were days apart. 99of9, did you do a last minute update before Gnobot played, or did it have access to finished games as they happened?

Also, bomb really did seem to be left behind that year (as OpFor wasn't parallel, so it wasn't just that), and even more so in 2010 & 2011. Is the general reason because of better position evaluation, or better pruning techniques? (or a combination of both?)

Speaking of parallel, if Sharp is parallelized for next year, then it will be even stronger than it is now. It's probably possible to work out how much stronger in terms of rating points, assuming nothing else changes (and assuming the hardware remains the same next year)?

Title: Re: The fall of Bomb
Post by 99of9 on May 4^th, 2011, 7:02pm

on 05/04/11 at 18:21:21, Swynndla wrote:

Those Bomb vs Clueless & Bomb vs GnoBot games were days apart. 99of9, did you do a last minute update before Gnobot played, or did it have access to finished games as they happened?

:D The only time bomb had played on that hardware was in the CC itself - so those were the games most likely to be repeatable. So yes, I needed to update the opening book automatically before every game. It provided endless annoying little tasks for omar, but since machine learning is allowed and encouraged, I figured it was ok to push him in this direction. The finished games database had already been accessible live via the web for a couple of years before I put this in.

Title: Re: The fall of Bomb
Post by Swynndla on May 4^th, 2011, 7:17pm

Interesting.

But tweaking the actual code of the bot wouldn't be allowed between games right? What about changing a material weights table in a file because the developer saw that the bot was losing because it valued its camel too much? ... or tweaking an evaluation table in a file because the bot was falling for an opening pitfall? I guess these things aren't allowed, but Gnobot already had the learning coded, and it just needed access to the games played. Is that technique still used? ... or are the bots too randomized these days?

(Apologies for all my questions.)

Title: Re: The fall of Bomb
Post by 99of9 on May 4^th, 2011, 7:59pm

The developer isn't allowed to do anything once the CC starts. Any changes have to be automatic (Omar is willing to run a script before each game, and the bot can run its own script after the game.)

A developer would not be allowed to maintain an external website which the bot looked up for extra code or evaluation weightings. (This is against the rules but I don't think there's any technical prevention.)

So yes, Gnobot had to do it all by itself.

As far as I know, this year none of the bots were adaptive. Gnobot can only use it for the opening book. Since most other competitive bots have randomized, it is no longer so useful for game copying. An adaptive opening book also helps a bot not to fall into opening traps like baiting. It also gives a more interesting experience for humans playing regularly against the same bot, because it would change its behaviour based on past wins and losses. But since the server version of the bots are frozen, this last benefit never really played out.

Title: Re: The fall of Bomb
Post by Fritzlein on May 4^th, 2011, 10:11pm

on 05/04/11 at 18:21:21, Swynndla wrote:

Speaking of parallel, if Sharp is parallelized for next year, then it will be even stronger than it is now. It's probably possible to work out how much stronger in terms of rating points, assuming nothing else changes (and assuming the hardware remains the same next year)?

Not exactly. Parallelization of alpha-beta searching will be inefficient; the only question is how inefficient. Going from one core to four cores does not give two doublings of speed; maybe only one and a half.

Also it is up for debate how many rating points are gained per doubling. A good guess seems to be between fifty and one hundred.

Thus an extreme optimist might expect sharp to gain 200 rating points from parallelization, but it might well be only 75 points. I personally think the latter is more realistic. Do we have direct evidence on this score? I'm curious to know how much other bots gained from going parallel, specifically clueless, GnoBot, and OpFor, which all were originally designed to be single-threaded.

Title: Re: The fall of Bomb
Post by UruramTururam on May 5^th, 2011, 12:49am

on 05/04/11 at 19:59:49, 99of9 wrote:

A developer would not be allowed to maintain an external website which the bot looked up for extra code or evaluation weightings. (This is against the rules but I don't think there's any technical prevention.)

A well-configured firewall allowing the bot server to contact only specified IP-s perhaps?

Note that if a bot contacts an external website it may not only update its evaluation table but it can effectively re-download itself and change dramatically. (Not too probable in fact.)

Title: Re: The fall of Bomb
Post by Swynndla on May 5^th, 2011, 1:31am

Quote:

Also, bomb really did seem to be left behind that year (as OpFor wasn't parallel, so it wasn't just that), and even more so in 2010 & 2011. Is the general reason because of better position evaluation, or better pruning techniques? (or a combination of both?

I've asked so many questions - if I may, I wanted to ask this again in case it got missed. (The answer may very well be "it's not as simple as that")

Title: Re: The fall of Bomb
Post by rbarreira on May 5^th, 2011, 2:26am

on 05/05/11 at 00:49:07, UruramTururam wrote:

In the extreme case, even just allowing a bot to read the record of Arimaa games already allows the developer to communicate with the bot (although it would be a low-bandwidth channel). Among other possible methods of mischief...

Title: Re: The fall of Bomb
Post by UruramTururam on May 5^th, 2011, 3:23am

on 05/05/11 at 02:26:11, rbarreira wrote:

In the extreme case, even just allowing a bot to read the record of Arimaa games already allows the developer to communicate with the bot (although it would be a low-bandwidth channel).

Yup, the developer can play a game so that the sequence of moves contains a command for the bot. A very low bandwidth channel indeed... Not wide enough to rewrite the procedures but sufficient for changing tables and/or (de-)activate specific subroutines.

Title: Re: The fall of Bomb
Post by lightvector on May 5^th, 2011, 4:24pm

on 05/04/11 at 18:21:21, Swynndla wrote:

For Sharp, I am using some new pruning methods, but I think really the two major reasons for my bot is better evaluation and better quiescence search.

Getting the qsearch to expand all the necessary tactics properly, but without slowing down the search too much was really critical.

In 2010, I added a trap control function that I spent time tuning to make it, as much as possible, say the same thing that someone like Fritz ;D would hopefully say if you asked "who controls this trap by how much, and how much of an advantage is that worth?". Also, seeing how aggressive Arimaa play was becoming, I shifted the evaluation slightly towards to a framework of "attacking and advancing pieces is always good except when X, Y, or Z", and then tuning X Y and Z. This produces Sharp's current preference for an aggressive style.

It's still fragile though, and can certainly still lose to Bomb, especially if the evaluation gets sidetracked on something really stupid (sigh).

Title: Re: The fall of Bomb
Post by Swynndla on May 6^th, 2011, 1:12am

lightvector, I find what you say very interesting - thanks for sharing!

on 05/05/11 at 16:24:06, lightvector wrote:

In 2010, I added a trap control function that I spent time tuning to make it, as much as possible, say the same thing that someone like Fritz ;D would hopefully say if you asked "who controls this trap by how much, and how much of an advantage is that worth?".

Did you make the bot work out the answers to those questions, or did you answer those questions yourself, or did you give a bunch of positions to someone like Fritz to answer? ;)