Arimaa Forum - Print Page


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

        Arimaa >> Events >> State of the Challenge 2010
        
(Message started by: Fritzlein on Jan 3^rd, 2010, 11:07am)

Title: State of the Challenge 2010
Post by Fritzlein on Jan 3^rd, 2010, 11:07am

Despite advances in Arimaa software during 2009, the Arimaa Challege appears quite safe for 2010. Omar will not have to assemble the strongest possible team of Challenge Defenders this year, a luxury he had in 2007-2009 as well. He can comfortably include himself as the alternate and also invite someone outside the top ten humans to test humanity's margin of dominance.

Whether the Arimaa Challenge can stand until 2020, however, remains a wide-open topic for debate. It is possible that the race has reached a turning point, with the human advantage having peaked in 2008. Perhaps from now on the human advantage will shrink year by year, and the only remaining question is how fast the bots will catch up.

The benchmark of bot strength as of the 2009 Arimaa Challenge was clueless. That benchmark has since been surpassed by quad, marwin, and clueless itself as jdb has improved the evaluation. Based on their game records, I estimate that all three bots are 50-100 rating points stronger than clueless was a year ago due to software alone, on top of which the Challenge hardware will surely be incrementally faster than the previous year.

I feel that I continue to learn about Arimaa and improve my game, but it would be a stretch to say that I am 100 rating points stronger than I was a year ago. Even claiming 50 points of learning might be hard to justify. On the other hand, the gap can't be measured solely from me, especially since my aging brain limits my ability in a way that younger players are not handicapped. Chessandgo has passed me, and shows no sign of looking back. Those kids mdk and Tuks are still rising stars with time on their side if they stick with Arimaa. Simon and ChrisB made huge strides through the Postal Mixer. And there is a large crop of brand new players working up the ranks since the release of Arimaa sets in August. Some of them have already bested the bot ladder.

My results over the past few months against the top three bots at fast time controls include several losses. Combining my win percentage in those games with my rough estimate that bots gain 150 points against humans by playing blitz and 100 points by playing fast, I estimate that I will have a strength advantage of a bit more than 400 rating points over the 2010 Computer Champion for games at the Arimaa Challenge time control of two minutes per move.

Two years ago I estimated that I was more than 500 points ahead of Bomb. If my advantage over the best bot shrinks at 100 points every two years, then I will be able to defend the Challenge until 2018 at the latest. Therefore, I hope that I am not humanity's last line of defense, and that the level of top human play is raised by newcomers who take Arimaa skill to new heights. For us to hold out against the bots until 2020 may require someone other than me to carry the torch.

Last year I thought that the quantum leap in bot strength represented by clueless, GnoBot, and OpFor beating Bomb might be a one-year surge that could not be sustained. Now that we have a second straight year of significant improvement in the top bot(s), I am more inclined to believe it is a trend. Also last year I predicted the emergence of a new superstar human player after the release of boxed Arimaa sets gave the game more exposure. That hasn't happened yet, but the commercial release was pushed back to mid-August, much later than I expected, so there hasn't been time yet for anyone joining since then to rise to the top. The new wave of gamers may be coming, but it hasn't matured yet, and in the mean time the new wave of developers is gaining ground.

All things considered, I am more pessimistic than I was last year when I predicted that the human advantage still had room to run. I thought then that we hadn't even reached the turning point. Now I think that perhaps human advantage has crested and we can start plotting a trend until the inexorable machines catch up. I still expect that humanity will hold out beyond 2020, but I no longer feel it is a slam dunk. Let me put a percentage to my intuition: humans have an 80% chance of defending through 2020, while bots have a 20% chance of winning before then.

It is a persistent failure of humans to read too much into short-term trends. When there was no progress in the top bots for three years, we thought progress would be very hard to come by. Now that there has been significant progress in the past two years, we will take the recent rate of progress as a given. The only thing I should feel confident predicting is that the short-term trend will change and that any prediction I make based on it will be wrong!

Title: Re: State of the Challenge 2010
Post by jdb on Jan 3^rd, 2010, 7:54pm

In general I agree with your points, Fritz. Your numerical estimates seem about right.

With regards to the potential improvement in bots, I think there is still plenty of low hanging fruit available. When I review the games that clueless plays, in almost every game, I see a move that I know is clearly wrong. A large percentage of these mistakes only require programmer time to fix. It will be interesting to see how strong the bots are when all the obvious mistakes are fixed. After that point, progress will likely be much slower.

Having said that, I doubt just fixing the obvious mistakes will be enough to win the challenge. When I review the games between top players, the mistakes are not always obvious to me. So there is still an extra level of skill the bots needs after the obvious mistakes are fixed.

Title: Re: State of the Challenge 2010
Post by Nombril on Jan 4^th, 2010, 4:34am

Is there any correlation between bot strength and their developer's strength at playing Arimaa? Have any of the top 3 human players worked on a bot while they were at the top of their game?

I don't know enough about bot development to know what the chances are of a "quantum leap" in bot strength. But at this point I believe incremental bot and hardware improvements will not be enough to overtake human ability. For a bot to win the challenge, I think someone will need to meet one of Omar's original goals and come up with a new way for computers to "think".

Title: Re: State of the Challenge 2010
Post by Fritzlein on Jan 4^th, 2010, 6:20am

on 01/04/10 at 04:34:00, Nombril wrote:

Is there any correlation between bot strength and their developer's strength at playing Arimaa? Have any of the top 3 human players worked on a bot while they were at the top of their game?

Way back in 2004, 99of9 was one of the top three players (actually the top player outright) as well as the developer of GnoBot. David Fotland was not among the top players, yet his bot Bomb crushed GnoBot. At that time, anyway, the correlation between developer rating and bot rating didn't hold.

At some point, though, I expect that a developer would be limited by his own understanding of Arimaa, perhaps when his bot surpassed him by 200 rating points. JBD's method of improving clueless by fixing mistakes will no longer work when JDB can't pinpoint the mistakes.

We have a historical precedent for expert gamers teaming up with expert developers: The IBM team that made Deep Blue was greatly assisted by Joel Benjamin, an American chess grandmaster.

Quote:

For a bot to win the challenge, I think someone will need to meet one of Omar's original goals and come up with a new way for computers to "think".

Depending on your point of view, your second paragraph contradicts your first paragraph. According to Omar, if expert humans manage to encode their Arimaa knowledge into unchanging evaluation formulas, and those fixed formulas plus brute-force lookahead are enough to win the Arimaa Challenge, then the winning bot won't have displayed intelligence. Fifty years ago, hard-coding human knowledge into computers was considered artificial intelligence, but I guess the times have changed.

What Omar wants now is a bot that can learn on its own, train itself, and perhaps ultimately come up with strategies that its developer can't understand. You have the intuition that an Arimaa developer needs to be good at Arimaa, but Omar wants you to be wrong about that. When a developer can no longer understand his program's "thoughts", it makes a stronger case that the program is "thinking".

Title: Re: State of the Challenge 2010
Post by Nombril on Jan 4^th, 2010, 10:47pm

on 01/04/10 at 06:20:02, Fritzlein wrote:

Depending on your point of view, your second paragraph contradicts your first paragraph.

Looks like I left the middle step of logic out of my note - I guess you can't read my mind! ;)

My first paragraph was more of a musing: my intuition is that a good "teacher" would create a stronger bot, and I was wondering if anyone had looked at those statistics. A tangent to that train of thought... Looking at JDB/Clueless and also your example of 99of9/GnoBot, it looks like many of the top tier of bots can't beat their own developer.

The missing paragraph: Assuming a strong human player has already tried to create a bot... and since the defenders have prevailed... then the normal computer advantages of avoiding short sighted blunders (still a problem for me...) and computational speed will not be able to overcome the fuzzy nature of long range Arimaa strategy. If everyone continues to use the same tools, I expect developers and players will both continue to learn more about the game. Something new will be required to upset the balance of power.

Which brought me to my conclusion that the pupil will need to "think", including the ability to learn and develop strategies. I think this type of breakthrough will be required before a bot will beat the top humans, and disagree with your conclusion that incremental hardware/software improvements will eventually help a bot win the challenge.

Title: Re: State of the Challenge 2010
Post by Fritzlein on Jan 5^th, 2010, 7:24am

on 01/04/10 at 22:47:26, Nombril wrote:

Which brought me to my conclusion that the pupil will need to "think", including the ability to learn and develop strategies. I think this type of breakthrough will be required before a bot will beat the top humans, and disagree with your conclusion that incremental hardware/software improvements will eventually help a bot win the challenge.

Nice. I'm glad you disagree with my conclusion. I believe that incremental hardware/software improvements will eventually be enough to win the Arimaa Challenge only because that is what happened with chess. Arimaa could be different. It will be more fun if it is!

Title: Re: State of the Challenge 2010
Post by docreason on Mar 15^th, 2010, 9:03pm

I am wondering if a solution to breakthrough in AI would come from the development of an AI that can play a range of game real well, and not be coded for just a single game.

Title: Re: State of the Challenge 2010
Post by Fritzlein on Mar 15^th, 2010, 9:21pm

on 03/15/10 at 21:03:45, docreason wrote:

I am wondering if a solution to breakthrough in AI would come from the development of an AI that can play a range of game real well, and not be coded for just a single game.

Sure, that would be great. Posing a harder problem may be more likely to result in a breakthrough than posing an easier problem. But an AI that plays a range of games well is a really hard problem. The generalized Zillions game player, for example, is atrocious at Arimaa. By going for a bigger result, you are also more likely to fail completely.

Title: Re: State of the Challenge 2010
Post by aaaa on Mar 15^th, 2010, 11:07pm

on 03/15/10 at 21:03:45, docreason wrote:

I am wondering if a solution to breakthrough in AI would come from the development of an AI that can play a range of game real well, and not be coded for just a single game.

http://en.wikipedia.org/wiki/General_Game_Playing

Title: Re: State of the Challenge 2010
Post by rbarreira on Mar 16^th, 2010, 5:21am

IMHO it's pointless to talk about General Game Playing, as it's very likely equivalent to Strong AI. (i.e. if you can make a program that can play any game well, you have probably achieved Human-level - or above human - general AI that is not just restricted to games)