Author |
Topic: New Challenge Pledge (Read 5041 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
New Challenge Pledge
« on: Sep 19th, 2013, 10:23am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
supersamu
Forum Moderator
Forum Guru
Arimaa player #7523
Gender:
Posts: 140
|
|
Re: New Challenge Pledge
« Reply #1 on: Sep 19th, 2013, 12:59pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
leob
Forum Newbie
Arimaa player #8939
Gender:
Posts: 4
|
|
Re: New Challenge Pledge
« Reply #2 on: Sep 19th, 2013, 1:29pm » |
Quote Modify
|
on Sep 19th, 2013, 10:23am, Fritzlein wrote:| 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? |
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New Challenge Pledge
« Reply #4 on: Sep 19th, 2013, 10:56pm » |
Quote Modify
|
on Sep 19th, 2013, 2:58pm, browni3141 wrote:
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New Challenge Pledge
« Reply #5 on: Sep 19th, 2013, 11:14pm » |
Quote Modify
|
Hi, Leo. Thanks for the pledge and thanks for the introduction too!
on Sep 19th, 2013, 1:29pm, 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.
|
|
IP Logged |
|
|
|
leob
Forum Newbie
Arimaa player #8939
Gender:
Posts: 4
|
|
Re: New Challenge Pledge
« Reply #6 on: Sep 20th, 2013, 1:39am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: New Challenge Pledge
« Reply #7 on: Sep 20th, 2013, 8:35am » |
Quote Modify
|
on Sep 20th, 2013, 1:39am, 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).
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New Challenge Pledge
« Reply #8 on: Sep 20th, 2013, 11:05am » |
Quote Modify
|
on Sep 20th, 2013, 1:39am, 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, 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.
|
|
IP Logged |
|
|
|
leob
Forum Newbie
Arimaa player #8939
Gender:
Posts: 4
|
|
Re: New Challenge Pledge
« Reply #9 on: Sep 20th, 2013, 10:18pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: New Challenge Pledge
« Reply #10 on: Sep 21st, 2013, 1:01am » |
Quote Modify
|
on Sep 20th, 2013, 10:18pm, 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.
|
|
IP Logged |
|
|
|
RiEvEr
Forum Junior Member
Arimaa player #8933
Gender:
Posts: 6
|
|
Re: New Challenge Pledge
« Reply #11 on: Sep 21st, 2013, 8:58am » |
Quote Modify
|
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. 
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 ) 
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: New Challenge Pledge
« Reply #12 on: Sep 21st, 2013, 11:51am » |
Quote Modify
|
Lots of good news in this thread - great to hear about the new pledge.
on Sep 21st, 2013, 8:58am, 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 Sep 21st, 2013, 8:58am, 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 Sep 21st, 2013, 8:58am, 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).
|
| « Last Edit: Sep 21st, 2013, 11:53am by rbarreira » |
IP Logged |
|
|
|
RiEvEr
Forum Junior Member
Arimaa player #8933
Gender:
Posts: 6
|
|
Re: New Challenge Pledge
« Reply #13 on: Sep 21st, 2013, 12:27pm » |
Quote Modify
|
on Sep 21st, 2013, 11:51am, rbarreira wrote:
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).
...
In the case of those bots, making them play like humans can pay off (not in terms of strength but to make enjoyable opponents). |
|
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... 
|
|
IP Logged |
|
|
|
supersamu
Forum Moderator
Forum Guru
Arimaa player #7523
Gender:
Posts: 140
|
|
Re: New Challenge Pledge
« Reply #14 on: Sep 21st, 2013, 12:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print