Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> New Challenge Pledge
        
(Message started by: Fritzlein on Sep 19^th, 2013, 10:23am)

Title: New Challenge Pledge
Post by Fritzlein on Sep 19^th, 2013, 10:23am

Great news about the new pledge to the Arimaa Challenge! I wonder how Leo Broukhis got interested in Arimaa. I don't see a player account for him; perhaps he is more interested in the computer science aspect than in game play?

Title: Re: New Challenge Pledge
Post by supersamu on Sep 19^th, 2013, 12:59pm

I wondered about this as well when I read the Announcement in the gameroom.
Maybe Omar can tell us how he got contacted by Leo Broukhis and how he stumbled upon Arimaa.

Title: Re: New Challenge Pledge
Post by leob on Sep 19^th, 2013, 1:29pm

on 09/19/13 at 10:23:57, Fritzlein wrote:

I don't remember when or how I first learned about Arimaa. It must have been at least 5 years; when I saw http://xkcd.com/1002/ I was already well aware if it to appreciate the comic. The relative position of the Arimaa and Go arrows seemed correct at the time, but I'm not so sure about it today. :)

A recent XKCD comic http://xkcd.com/1263/ prompted me to add a little to the challenge prize.

Personally, I'm more of a puzzle person rather than a game person; chess never interested me enough to play it better than being able to move the pieces according to the rules. :) So you're right, the computer science aspect is what I'm after.

Title: Re: New Challenge Pledge
Post by browni3141 on Sep 19^th, 2013, 2:58pm

This page looks a little out of date: http://arimaa.com/arimaa/challenge/prize.html
How are people supposed to know what the current prize is?

Title: Re: New Challenge Pledge
Post by Fritzlein on Sep 19^th, 2013, 10:56pm

on 09/19/13 at 14:58:20, browni3141 wrote:

This page looks a little out of date: http://arimaa.com/arimaa/challenge/prize.html
How are people supposed to know what the current prize is?

Good question, browni. I continue to go year-by-year. I'm in for $1000 again for the 2014 Challenge, but as always I think that I might not be around the year after.

Title: Re: New Challenge Pledge
Post by Fritzlein on Sep 19^th, 2013, 11:14pm

Hi, Leo. Thanks for the pledge and thanks for the introduction too!

on 09/19/13 at 13:29:04, leob wrote:

The relative position of the Arimaa and Go arrows seemed correct at the time, but I'm not so sure about it today. :)

I'm quite unsure as to the relative "intrinsic" computer-resistance of Go and Arimaa. If humans studied both games equally hard and programmers put equal effort into writing engines for each game, which game would have the larger advantage for humans? I can make a case for either game.

As for the actual gap given actual interest on each side of each challenge, it seems to me humans still have a greater margin in Go. For Arimaa to take over the spot of being more computer-resistant in practice, I believe there would have to be a surge of interest in Arimaa on the part of human gamers. I believe the small population of human Arimaa players is holding us back from deep strategic discoveries that would leave computers spinning their wheels for at least another decade. But absent a surge of new humans learning Arimaa, the Arimaa Challenge could well fall by 2020.

That is to say, I think your pledge is not a safe gesture by any means. That makes it all the more magnanimous and welcome. :)

Title: Re: New Challenge Pledge
Post by leob on Sep 20^th, 2013, 1:39am

Fritzlein,

Thank you for the warm welcome; I realize that the challenge may fall before 2020; this makes it even more interesting. However, the restrictions of the challenge preclude using highly parallel CPU-intensive methods like Monte-Carlo making me feel safer. :)

How do you estimate the odds that an unbeatable "silver bullet" strategy exists for Arimaa?

Title: Re: New Challenge Pledge
Post by Hippo on Sep 20^th, 2013, 8:35am

on 09/20/13 at 01:39:07, leob wrote:

How do you estimate the odds that an unbeatable "silver bullet" strategy exists for Arimaa?

We are still beginners. There are positions where we are really unsure who has the advantage and even with almost perfect play it lasts much longer than are alphabeta bot's search abilities. A lot should be done with evaluation as well as with search (and prunning) ... . In any cases bot_briareus does very well in the postal mixer.

We are very far from knowing which color wins in perfect play, and we expect that if a player wants to play active, the game will not last forever. Current feeling is that the active player has an advantage. I hope this is good reasoning for nonexistence of a silver bullet strategy
(in the context of both players playing according it).

Title: Re: New Challenge Pledge
Post by Fritzlein on Sep 20^th, 2013, 11:05am

on 09/20/13 at 01:39:07, leob wrote:

the restrictions of the challenge preclude using highly parallel CPU-intensive methods like Monte-Carlo making me feel safer. :)

I would be more afraid of highly parallel alpha-beta search. As far as I can tell, Monte Carlo methods add nothing to the playing strength of Arimaa bots. My limited understanding is that Monte Carlo tree search won't be effective unless a random move by each side leaves the position value roughly the same as before on average. In Arimaa, random moves are quite often drastically favorable to one side or the other. In particular, the attacking player benefits greatly from a bad move by the defender, whereas the defender benefits only slightly from a bad move by the attacker, so Monte Carlo methods favor blindly attacking. Correct Arimaa play, in contrast, often favors the defender.

Quote:

How do you estimate the odds that an unbeatable "silver bullet" strategy exists for Arimaa?

Since Arimaa is drawless, there is a 100% chance there is an unbeatable strategy, although it is about 50-50 in my mind whether it is Gold or Silver who has this unbeatable strategy.

Finite two-player perfect-information games are inherently broken: they must either be a forced win, forced loss, or forced draw. The relevant question is how good players can get at a game without busting it. For some games (e.g. Abalone, Quarto, Teeko) the game is only fun if you are a beginner or mediocre-level player. Once you become expert the game is broken.

As Hippo said, we are not even close to breaking Arimaa. In this year's Postal Mixer, I encountered several positions I simply don't know how to evaluate strategically. For example my game against ChrisB (http://arimaa.com/arimaa/gameroom/comments.cgi?gid=276035), around move 9 or 10. It is EMHH vs. EHH on one wing with the M the strongest free piece on the other wing. Who does that favor and why? I have no idea. A computer will not help resolve the question, as there are no forced tactics. But I believe that

1) Some future grandmaster of Arimaa will be able to simply look at the position and quickly say who is winning, why, and what the immediate objectives of each player should be.
2) That future grandmaster of Arimaa will not have busted Arimaa, but will have new strange positions occurring in his games against other grandmasters about which he is still confused.

In short, I believe that Arimaa has much strategic depth that has yet to be plumbed.

The bad news is that I also believe nothing can prove me right (or wrong) other than a large and dedicated population of Arimaa players studying the game. When you try to get good at a game, you might accidentally bust it instead, and when you try to bust a game, you might accidentally get good at it instead. It is impossible to know in advance which will happen. All we can say is that Arimaa is showing no early warning signs of being busted, i.e.

1) No discernable color advantage
2) No drawn-out stalemate-like positions where neither player can progress
3) No herding toward a single playing style that dominates all others

I am rather more confident that Arimaa is a great game than I am confident it is computer-resistant.

Title: Re: New Challenge Pledge
Post by leob on Sep 20^th, 2013, 10:18pm

Fritzlein, Hippo,

If my understanding of what Fritzlein is saying is correct, what I mean by "silver bullet" is the same as what he means by "busted": not just a theoretical proof of existence of a forced win for one of the sides, but a demonstrably constructive way to win.

Title: Re: New Challenge Pledge
Post by Fritzlein on Sep 21^st, 2013, 1:01am

on 09/20/13 at 22:18:35, leob wrote:

...a demonstrably constructive way to win.

Sure. You just need to clarify what you mean by asking whether the silver bullet "exists". In some sense it must exist, right? So you are really asking how close we are to figuring out what it is, given that it must be there? But perhaps there is a different shade of meaning to your question; feel free to set me straight.

At any rate, top-level games of Arimaa are still very dramatic and unpredictable, which is amazing given how many ranks above beginner the top-level players are.

Title: Re: New Challenge Pledge
Post by RiEvEr on Sep 21^st, 2013, 8:58am

Well, I only just discovered the game, but am looking forward to getting my teeth into it and coming up with a new way to teach a computer to play it.

I've ordered a set from America (it'll take about 3 weeks to get here) and already grabbed Fritz Juhnke's "Beginning Arimaa" book.

My wife has encouraged me to do this because I have apparently not had a real interest in life since I quit Games AI coding 10 years ago, owing to her ill health.

It's going to take me a month or two to get back into the swing of coding again, but I already have some ideas for how to teach the PC to play like a human.

If nothing else, I am headed for interesting times.

(My background: I started AI coding in around 1981 on a Commodore PET 1000 improving the ELIZA program and then creating text adventure games.

Around 1983 I moved on to Tic-Tac-Toe and then Chess coding. I got various qualifications over the years in coding and computer science, I was already an Electronics Engineer before I picked up my first C compiler and had worked in Hex on 8 bit processors during my time in the Armed Forces.

My final 'work' was bot AI for FPS games like Quake, Quake 2, Kingpin, SiN, etc., and I wrote the arcade conversion for SiN which I named "SiN: ReDeMpTiOn" - the alt caps is just how we used to roll back then. :P

I had to invent 'Artificial Stupidity' routines for the bots so that humans stood a chance against them - I also taught them to find their paths through the levels by observing human players and creating dynamic node mapping. It was a blast, and I've missed it...

Sorry for the wall of text ) ;D

Title: Re: New Challenge Pledge
Post by rbarreira on Sep 21^st, 2013, 11:51am

Lots of good news in this thread - great to hear about the new pledge.

on 09/21/13 at 08:58:11, RiEvEr wrote:

Well, I only just discovered the game, but am looking forward to getting my teeth into it and coming up with a new way to teach a computer to play it.

Always nice to see new bot developers, in the past year (or more) there hasn't been much progress in bot development.

on 09/21/13 at 08:58:11, RiEvEr wrote:

It's going to take me a month or two to get back into the swing of coding again, but I already have some ideas for how to teach the PC to play like a human.

Interesting that you put it that way, because as far as I know attempts to make computers play like humans are usually not very successful at making strong bots (for example in chess).

on 09/21/13 at 08:58:11, RiEvEr wrote:

My final 'work' was bot AI for FPS games like Quake, Quake 2, Kingpin, SiN, etc., and I wrote the arcade conversion for SiN which I named "SiN: ReDeMpTiOn" - the alt caps is just how we used to roll back then.

Awesome stuff, I remember reading the source code for Quake's Reaper bots and maybe others. In the case of those bots, making them play like humans can pay off (not in terms of strength but to make enjoyable opponents).

Title: Re: New Challenge Pledge
Post by RiEvEr on Sep 21^st, 2013, 12:27pm

on 09/21/13 at 11:51:26, rbarreira wrote:

That is what I prefer. I know how to make strong Chess bots, for instance, but they're not 'fun' to play against. I'd rather code a bot with some 'personality' so people feel more like they're having an actual game with a friend (or enemy).

For example, I prefer the old Fritz Chess to more clinical modern offerings as his vocal commentary (and jibes) always makes me smile.

I also sometimes enjoy playing against the AI players in Chessmaster who have their little biographies telling you what type of play to expect.

Games are about fun, for me anyway, so it will be interesting to see if others receive my efforts with the same attitude *grins*

Also, who knows, I may discover something in my approach that mimics the way a human can play the game well, with all their faults, which negates the need for full width alpha-beta minmaxing. There's always a chance... ;)

Title: Re: New Challenge Pledge
Post by supersamu on Sep 21^st, 2013, 12:53pm

Quote:

That is what I prefer. I know how to make strong Chess bots, for instance, but they're not 'fun' to play against. I'd rather code a bot with some 'personality' so people feel more like they're having an actual game with a friend (or enemy).
[...] I also sometimes enjoy playing against the AI players in Chessmaster who have their little biographies telling you what type of play to expect.

Yes, I think I know what you mean. I had a portable chesscomputer when I was a kid. He commented on game moves if they were exceptional.(2-4% of the moves)
He either said "Uh-oh" or "wow, good move!".
I loved playing chess against people when the computer was commentating. I can still remember that one time when the computer said "wow, good move" for two of my turns in a row.
He also had different playing modes, one of which was labeled "tactical playing style" and I just for fun put it on the highest level for that Style and played against it.
He made some really cool moves and I gleefully lost.

Title: Re: New Challenge Pledge
Post by Fritzlein on Sep 21^st, 2013, 1:19pm

on 09/21/13 at 12:27:33, RiEvEr wrote:

It's great that we have bots with different personalities on the bot ladder so that new players working their way up get exposed to many different styles of play. Perhaps the most idiosyncratic is bot_Loc, with some human-looking moves but also some huge blind spots, since is was coded without full-width alpha-beta search. (Or am I thinking of bot_Rat, by the same author?)

In the long run, though, an opponent won't be fun unless it is about the same level as you are. It is boring to lose every game or win every game. So making a bot that is fun for top players requires you to get within a few hundred Elo of winning the Arimaa Challenge itself. I hope you are up to it!

The balance of power in the Arimaa Challenge depends on the intrinsic nature of Arimaa itself, but also depends very much on the population of people committed to contesting the Challenge. Every time an enthusiastic new gamer joins, the balance tips a little towards the humans, but every time an enthusiastic new developer joins, it tips a little bit towards the bots. Since I am rooting for humans to win, I must hope you aren't too good at AI programming. :)

Are you with me, Leo? Or are you offering your prize money (like Omar) halfway hoping that you will lose, as long as you lose in an interesting way?

Title: Re: New Challenge Pledge
Post by RiEvEr on Sep 21^st, 2013, 6:18pm

on 09/21/13 at 13:19:01, Fritzlein wrote:

Since I am rooting for humans to win, I must hope you aren't too good at AI programming. :)

Funnily enough, I hadn't really considered the money aspect of the challenge, but there's time to beat that once I'm happy with the initial fun code.

I am a very good AI programmer. I tend to make intuitive leaps in my imagination that quickly turn into completed subroutines under my fingers.

I am really looking forward to getting back to creating once again ;D

"We are the music-makers,
And we are the dreamers of dreams,
Wandering by lone sea-breakers,
And sitting by desolate streams.
World-losers and world-forsakers,
Upon whom the pale moon gleams;
Yet we are the movers and shakers,
Of the world forever, it seems. "

(Arthur William Edgar O'Shaughnessy)

Title: Re: New Challenge Pledge
Post by leob on Sep 21^st, 2013, 7:17pm

on 09/21/13 at 13:19:01, Fritzlein wrote:

Are you with me, Leo? Or are you offering your prize money (like Omar) halfway hoping that you will lose, as long as you lose in an interesting way?

Looking at the Arimaa Challenge results and trends, I estimate my (and Omar's) odds of losing at around 30%. And, of course, if I lose, I'd prefer to lose in an interesting way, not due to a technicality (like if nobody from the top 10 players was able to participate).

Title: Re: New Challenge Pledge
Post by RiEvEr on Sep 22^nd, 2013, 4:09am

on 09/21/13 at 19:17:19, leob wrote:

I agree with that. If I were to enter a bot in the challenge I would want it to play the best Human opponents or the result would be meaningless.

Obviously, some number-crunching super-computer running the best of the current bots would stand a chance even now, but that solution would not be elegant.

I played a few more games of Arimaa last night (Android) and can already see that the game holds the same potential for beautiful moves and combinations that first drew me to chess over 40 years ago.

I have always loved games and mainly got into AI coding because I couldn't find regular friends to play with once I was an adult and computers provided me with the opportunity to create opponents of my own. In some ways, this puts me on the side of the Humans, like Fritz, but I am never satisfied with my coding efforts and have always striven to improve each iteration of my 'bots' in any game; thus I would never hold back so the humans could win, either. *chuckles*

I would also take into account the fact that the prize money would let me buy a top of the range PC and no gamer is going to turn down a chance like that. ;D

Title: Re: New Challenge Pledge
Post by Arimabuff on Oct 17^th, 2013, 7:42am

If I am not mistaken "silver bullet" refers to werewolves, right?