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

        Arimaa >> Bot Development >> Arimaa at Boardspace.net
        
(Message started by: ddyer on Nov 24th, 2010, 3:50pm)
Title: Arimaa at Boardspace.net
Post by ddyer on Nov 24th, 2010, 3:50pm
I've got Arimaa about ready for Boardspace.net, but I'd like to enlist a few experienced players to check for rules correctness and make suggestions for my weak robot.
Title: Re: Arimaa at Boardspace.net
Post by qswanger on Nov 24th, 2010, 5:35pm
Holy Cow! This is awesome news. Boardspace is an EXCELLENT gaming site. Count me in!
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Nov 24th, 2010, 11:05pm
It's there.  Let me know what you find.
Title: Re: Arimaa at Boardspace.net
Post by clojure on Nov 24th, 2010, 11:45pm
Hi, I tried to put pieces from the right most stack for the initial setup but before I got to the end of the stack, there was some error, which prevented me to continue.

Here are the messages.


Code:
Lobby: Welcome to BoardSpace client, version 3.1
Error: in game main loop java.lang.Error: rabbit count matches{LastParsed:
    Reset}java.lang.Error: rabbit count matches
Error: in game main loop java.lang.Error: rabbit count matches last message was 211
    trackMouse on 84 66 -3 {LastParsed: Pick B 6 13}java.lang.Error: rabbit count
    matches
Error: in game main loop java.lang.Error: rabbit count matches last message was 211
    trackMouse on 1010999 21000 13 {LastParsed: Dropb B 2}java.lang.Error: rabbit
    count matches
Error: in game main loop java.lang.Error: rabbit count matches{LastParsed: Pick B 6
    13}java.lang.Error: rabbit count matches
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Nov 25th, 2010, 11:09am

Thanks for the rapid feedback - this is fixed now.
Title: Re: Arimaa at Boardspace.net
Post by omar on Nov 25th, 2010, 10:25pm
Thanks for adding Arimaa to Boardspace.net. I tried it out and it looks pretty good. I didn't have time to finish the game since the bot was taking a while to move. On the setup move the bot was thinking after placing each piece. You might want to use some predefined setups on the first move to speed it up. I didn't run into any errors.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Nov 25th, 2010, 11:29pm
The lookahead is essentially meaningless in the initial setup
phase, so trimming it back ought to be fine.  I also plan to
add a "place the rabbits" button for humans to use after
the first 8.
Title: Re: Arimaa at Boardspace.net
Post by omar on Dec 9th, 2010, 8:43am
I was able to play test it out more today. I noticed that the bot made a move which did not change the board position. It was move 29 and 31 in the game. It moved the elephant, but brought it back to the square it was originally on.
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 9th, 2010, 8:31pm

on 12/09/10 at 08:43:59, omar wrote:
I was able to play test it out more today. I noticed that the bot made a move which did not change the board position. It was move 29 and 31 in the game. It moved the elephant, but brought it back to the square it was originally on.

Which is significant since that is an illegal move...
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 9th, 2010, 9:34pm

on 12/09/10 at 20:31:59, Fritzlein wrote:
Which is significant since that is an illegal move...


re: AA-Dumbot-omar-2010-12-09-1412

(a) it's not an illegal move to cause 3 repetitions,
it's a LOSING move.  There is a difference.

(b) In the case in point, the elephant walks in a circle,
but this is not yet even one repetition.  After the gold
elephant walks in a circle, silver has a new position
he has never before confronted.  


-- not to claim perfection, if the applet sees three repetitions, it declares a draw rather than a loss.
I'll fix that.
Title: Re: Arimaa at Boardspace.net
Post by Janzert on Dec 9th, 2010, 10:37pm
Hmm, looking up the rule I guess it is rather ambiguous. I think this is the relevant sentence in the rules:

Quote:
A player can pass some of the steps, but at least one step must be taken on each turn to change the game position.


I guess this can be taken to mean that since the elephant circled around, it had changed the game position during the turn. I believe Omar's intent and the arimaa community interpretation has always been that the game position has to be changed at the end of the turn from what it started as. Even just swapping the position of say two dogs has been clarified as illegal in the past.

Janzert
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 9th, 2010, 11:48pm
When I learned Arimaa, I was also confused by the "at least one step must be taken" rule, which is (as you point out) not completely clarified by adding "to change the position".  When the rules state that a player is required to change the position, that requirement is made unclear by expressing it in terms of having to take at least one step.  The rule as stated invites the misinterpretation that Dave just made.

It might be better to say, "A player may not pass his turn or make a move equivalent to passing."  Then the need to take at least one step is an obvious corollary instead of a misleading introduction.  The full sentence might read, "A player may pass some of the steps, but may not pass the whole turn or make a move equivalent to passing."  Does this strike folks as being less open to misinterpretation?
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 9th, 2010, 11:51pm

on 12/09/10 at 21:34:50, ddyer wrote:
(a) it's not an illegal move to cause 3 repetitions, it's a LOSING move.  There is a difference.

There is indeed a difference.  Actually, this rule has been changed.  It used to be a losing move to create a third repetition, but now it is an illegal move instead.  Where are the rules that you are referencing that call it a losing move?  We need to bring those rules up to date.  (The Arimaa rules on Wikipedia were updated with this change on July 5, 2008)



on 12/09/10 at 21:34:50, ddyer wrote:
(b) In the case in point, the elephant walks in a circle,
but this is not yet even one repetition.  After the gold
elephant walks in a circle, silver has a new position
he has never before confronted.

That's correct, it is not even yet one repetition, but the "no passing" rule is in addition to the "no three-fold repetition" rule.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 10th, 2010, 12:24am

I haven't seen the "equivalent to passing" language anywhere official - I'll wait for it to appear.

I propose that no matter what rule is in effect, it will
be possible to construct board positions where reasonable players will disagree if the result is "fair" or not.
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 10th, 2010, 1:20am

on 12/10/10 at 00:24:30, ddyer wrote:
I propose that no matter what rule is in effect, it will be possible to construct board positions where reasonable players will disagree if the result is "fair" or not.

Certainly.  I don't like the official rules myself.  It is as it is because that's how Omar decided it should be, and it turns out I can live with it.  :)
Title: Re: Arimaa at Boardspace.net
Post by rbarreira on Dec 10th, 2010, 3:10am

on 12/09/10 at 23:48:17, Fritzlein wrote:
The full sentence might read, "A player may pass some of the steps, but may not pass the whole turn or make a move equivalent to passing."  Does this strike folks as being less open to misinterpretation?


I agree that this would make the rules clearer.
Title: Re: Arimaa at Boardspace.net
Post by omar on Dec 16th, 2010, 10:11am
Thanks for that suggestion Karl. That does make it more clear and sounds less wordy. I've updated the rules page.

Feel free to suggest other wording changes.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 17th, 2010, 5:26am

on 12/16/10 at 10:11:00, omar wrote:
Thanks for that suggestion Karl. That does make it more clear and sounds less wordy. I've updated the rules page.

Feel free to suggest other wording changes.


I suppose only Omar gets a vote, but I still get an opinion.  I don't think this change, or the previous change to forbid "3 repetitions" is a good idea.

The "equivalent to a pass" wording change is not a neutral change that only outlaws meaningless moves.  Case in point the "elephant walks in a circle" situation.  The elephant "stepped away" in pursuit of some goal the robot saw, but the emergent behavior that dominates the position is that the elephant is guarding the trap.  The depth thresholds on the search were perfectly aligned so it saw no harm in stepping away, but once committed to the step-away, the need to step back became visible over the horizon.

Consequently, with the step back forbidden, the camel will be lost.

Similarly, in situations where the robot "naturally" would play infinite repetitions, forbidding the repetition just forces it to do something else that is poorly motivated, resulting in weaker play and tedious near-repetition that goes on forever - or at least until some move randomy pertubs the loop or the game is lost on time.  When the robot is strategically bankrupt, forbidding repetition doesn't make it any smarter.  A smart robot would offer (and accept) an agreed draw.  Allowing it to just play a draw is good alternative.  

Title: Re: Arimaa at Boardspace.net
Post by rbarreira on Dec 17th, 2010, 6:57am
There was no change, omar just clarified the rules. Moves which don't change the board haven't been legal for a long time (if ever).
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 17th, 2010, 10:51am

on 12/17/10 at 05:26:07, ddyer wrote:
The "equivalent to a pass" wording change is not a neutral change that only outlaws meaningless moves.

Nobody claims the rule is meaningless, or that it doesn't make a difference what the rule is.  You are right, it isn't neutral.  But it isn't a rule change; it is a wording change to make clear what the rule has always been here on arimaa.com.


on 12/17/10 at 05:26:07, ddyer wrote:
When the robot is strategically bankrupt, forbidding repetition doesn't make it any smarter.  A smart robot would offer (and accept) an agreed draw.  Allowing it to just play a draw is good alternative.

Yes, the "natural" outcome between two strategically bankrupt bots is often a draw if neither one is programmed to advance against opposing traps.  Omar was fully aware, however, that allowing draws by repetition logically mandates allowing agreed draws as well.  With an eye to human players rather than bots, he very much wanted to forbid agreed draws.  The point is that, unlike chess draws, Arimaa draws are not natural outcomes between players who are strategically aware.  Indeed, there has yet to be a single documented human vs. human game of Arimaa which "should" have been drawn with correct play on both sides.  There have only been a small handful of instances in which the player with the superior position misunderstood and thought that repeating moves was the best he could do.  Therefore Omar's decision to ban agreed draws has been justified by the absence of "natural" draws in actual play.

It is possible (according to Mark Steere, inevitable) that someday some two human players will drag on a game of Arimaa indefinitely, not because they misunderstand the position, but rather because there is legitimately no way for either to win, at which time Omar's repetition rule will look awkward and wrong.  Until that happens, however, forbidding draws by repetition is only a problem for dumb bots.  Humans that want to repeat position need to learn better.

Of course, Omar's attempt to control the gaming experience can always be thwarted by gamers themselves.  Any game community can insist on their inalienable right to agree to draws, their right to repeat position, and for that matter their right to play with no cats, three dogs, and a turkey instead of the standard set of pieces.  That's the wonderful thing about the way games evolve; ultimately the game designer is not the only one who gets a vote.  A modern example of this is Sid Sackson's game Lines of Action, which he intended to be drawless, but which is played by all serious human players with alternate rules that permit draws.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 17th, 2010, 11:33am
It's certainly should be possible to construct positions where it's clear that the game is locked into a draw.  I haven't done so, but I'd start a construction around the idea of both players protecting their last rabbit from a trap.

In that case, with one or two extra (weak) pieces each, you'd have a situation where a virtually infinitely long game could occur before the repetition rule would force a resolution.

In any case, the only alternative to an agreed draw in human to human play is time limits, which is not a very satisfactory resolution either.  Imagine Omar's chagrin if the programming challenge is eventually won by a program that plays for a draw and then wins on time.
Title: Re: Arimaa at Boardspace.net
Post by Janzert on Dec 17th, 2010, 12:59pm
Sorry if my initial reply about the ambiguity of the rule led anyone to believe the actual use by the Arimaa community wasn't completely settled as a "no pass" rule. Here are a few past conversations surrounding this rule that might help show its status:

In the 2008 rule change thread (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1213818953;start=15#17), Omar lists the order of end game checks which start with "3rd time repetition and moves which don't change the board position are rejected". A few posts later a discussion starts around dropping the "no pass" rule.

In November 2006 (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1164468121;start=8#8) Fritzlein considers the importance of the rule.

In March 2006 (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1142809371;start=1#1) Ryan Cable mentions that swapping two identical pieces still falls under the rule and is illegal.

Janzert
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 17th, 2010, 1:10pm

on 12/17/10 at 11:33:57, ddyer wrote:
It's certainly should be possible to construct positions where it's clear that the game is locked into a draw.

Correct.  We can construct such positions.  The simplest is to put all rabbits of each player on his fourth rank, with his other pieces behind.


Quote:
you'd have a situation where a virtually infinitely long game could occur before the repetition rule would force a resolution.

Correct.  But such a situation has never arisen in any real game.


Quote:
Imagine Omar's chagrin if the programming challenge is eventually won by a program that plays for a draw and then wins on time.

Yes, that's theoretically possible, and it would be very embarrassing.  But so far even humans who are better than the best bots have had no luck at all playing for a draw.

As soon as we have one game, just one, the first one in the history of Arimaa, where there is no good alternative to an essentially infinite deadlock, then Omar will have to decide whether he likes his current rule of imposing a time cutoff and awarding the win to the player with more pieces, or to Silver if there have been no exchanges.  I will probably think that his "unnatural" imposition of a win for one player is a worse solution than allowing the game to be drawn, but maybe I won't think that, depending on how the deadlock came to pass.  In any case, for now it is purely hypothetical what would be the best alternative to allowing a draw, or whether allowing draws would itself be best, because the situation simply hasn't come up.
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 17th, 2010, 1:37pm

on 12/17/10 at 12:59:52, Janzert wrote:
Here are a few past conversations surrounding this rule that might help show its status:

Thanks for the links, Janzert.  I note with amusement that by 2008 I had forgotten that JDB had already in 2006 demonstrated mutual-zugzwang endgame positions.  Has there ever been a case of zugzwang (even one-sided) in an actual human vs. human game?  I can't recall any, but clearly my memory is not reliable.  ;-)

Zugzwang is a separate issue from the handling of repetition, but it is similar in that intuitions will vary, and that some players will feel wronged that they are not allowed to pass even when passing would be better than any available move.  Chess players probably won't object to the Arimaa rules, since they are used to a lifetime of zugzwang, but I can see the case that it is somehow unnatural to give a win to player who couldn't make progress in the face of passes, but can win when his opponent is forced to move.

On the other hand, the entire theory of games developed by John Conway et al in Winning Ways For Your Mathematical Plays is based on zugzwang, so they would probably be opposed to a campaign to allow passing in all games. :P
Title: Re: Arimaa at Boardspace.net
Post by omar on Dec 20th, 2010, 10:39am

on 12/17/10 at 13:10:40, Fritzlein wrote:
As soon as we have one game, just one, the first one in the history of Arimaa, where there is no good alternative to an essentially infinite deadlock, then Omar will have to decide whether he likes his current rule of imposing a time cutoff and awarding the win to the player with more pieces, or to Silver if there have been no exchanges.  


Even if that occurs one would have to show that it was a game with perfect play by both sides and there was no other alternative. But even if this started happening on a regular basis with non-perfect, non-cooperative play, it would become a problem. Fortunately we're not there yet.

Interestingly in Havannah also it is possible to construct drawn positions, but they never occur with normal non-cooperative play.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 30th, 2010, 1:21pm
I've installed another significant upgrade at Boardspace.  Please throw rocks.
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Dec 30th, 2010, 8:22pm

on 12/30/10 at 13:21:09, ddyer wrote:
I've installed another significant upgrade at Boardspace.  Please throw rocks.

Nice interface, but [rock] the bot averaged over four minutes per move, which is waaaaaay too slow. [/rock]  Thanks again for getting Arimaa up on boardspace!
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 30th, 2010, 9:11pm
I agree about the speed.  I've backed off to a weaker
version that runs a lot faster.
Title: Re: Arimaa at Boardspace.net
Post by Hippo on Dec 31st, 2010, 4:43am

on 12/30/10 at 21:11:58, ddyer wrote:
I agree about the speed.  I've backed off to a weaker
version that runs a lot faster.

Even now it's really, really slow... I have resigned after capturing camel and cats ... [rock]I miss an option to undo a move[/rock]
Title: Re: Arimaa at Boardspace.net
Post by DonEsteban on Dec 31st, 2010, 7:52am
Very nice implementation of the game board, ddyer! I hope this will help recruiting more players for Arimaa (already worked for me).


on 12/16/10 at 10:11:00, omar wrote:
Feel free to suggest other wording changes.

You may consider those as nitpicking, but you kind of asked for it ;)

"But (like pawns in chess) the rabbits cannot move backward."

Moving the part in parenthesis removes any doubt if pawns in chess can move backward or not.

"A push or pull is considered atomic as if the two pieces are moved simultaneously. Thus it is possible for the pulling (or pushing) piece to step into a trap and be removed from the game while completing the pull (or push). "

Adding the text in bold to the above passage should prevent any unnecessary confusion.
Title: Re: Arimaa at Boardspace.net
Post by DonEsteban on Dec 31st, 2010, 8:39am

on 12/09/10 at 23:51:02, Fritzlein wrote:
There is indeed a difference.  Actually, this rule has been changed.  It used to be a losing move to create a third repetition, but now it is an illegal move instead.  Where are the rules that you are referencing that call it a losing move?  We need to bring those rules up to date.

Sorry for the double posting, but I've just remembered this: http://en.labs.wikimedia.org/wiki/Arimaa/Playing_The_Game was one instance of outdated rules. I've already corrected that page, but please feel free to check if I have missed anything.
Title: Re: Arimaa at Boardspace.net
Post by Hippo on Dec 31st, 2010, 10:37am

on 12/31/10 at 07:52:51, DonEsteban wrote:
"A push or pull is considered atomic as if the two pieces are moved simultaneously. Thus it is possible for the pulling (or pushing) piece to step into a trap and be removed from the game while completing the pull (or push). "

Adding the text in bold to the above passage should prevent any unnecessary confusion.


While pushing you first pust the opponent's piece so the push is finished before the stone could vanish in the trap. So only for pull this should be mentioned.
Title: Re: Arimaa at Boardspace.net
Post by lightvector on Dec 31st, 2010, 12:40pm

on 12/31/10 at 04:43:22, Hippo wrote:
Even now it's really, really slow... I have resigned after capturing camel and cats ... [rock]I miss an option to undo a move[/rock]


Agreed, the bot is still almost unplayably slow. =(

I attempted to play a game. In the beginning, it still seems to average around 2 min/move. After only 15 moves on each side, the bot had spent a total of an hour and a half in thinking time, which means an average of 6 minutes per move.
Title: Re: Arimaa at Boardspace.net
Post by Janzert on Dec 31st, 2010, 2:23pm
If you like I would be glad to help you use OpFor (releases are here (http://arimaa.janzert.com/opfor/)). The biggest potential hurdle is probably that setting up the required D language build environment can be rather difficult. This should also mean that you could then easily switch to another AEI engine in the future.

Janzert
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Dec 31st, 2010, 7:46pm

on 12/31/10 at 14:23:33, Janzert wrote:
If you like I would be glad to help you use OpFor (releases are here (http://arimaa.janzert.com/opfor/)). The biggest potential hurdle is probably that setting up the required D language build environment can be rather difficult. This should also mean that you could then easily switch to another AEI engine in the future.

Janzert


I'd love to get D running.  I downloaded the eclipse
environment for it but couldn't get it to work.

On the other hand, I made a few final tweaks that have both improved the dumbot's play and made it able to lose a full game in 30 minutes playing time.  The biggest change that those patient souls who played previous versions will notice is that it now plays the entire sequence from the first search, instead of conducting a new search for each step.
Title: Re: Arimaa at Boardspace.net
Post by Janzert on Jan 1st, 2011, 2:05pm

on 12/31/10 at 19:46:36, ddyer wrote:
I'd love to get D running.  I downloaded the eclipse
environment for it but couldn't get it to work.


I've never used an IDE with D (or much of anything else really). Included with the OpFor source is a simple script (build.py) that will compile the bot once the correct D compiler setup is added to the path.

Unfortunately for opfor2009 I also used the even more obscure, and now seemingly unmaintained, tangobos library. There doesn't seem to be a published link anymore but the linux package for tangobos including the dmd compiler can be downloaded from http://downloads.dsource.org/projects/tango/0.99.7/tango-tangobos-0.99.7-bin-linux-dmd.1.033.tar.gz.

Depending on the distribution I could probably provide you with a pre-built binary if you just wanted that as well.

Janzert
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Jan 2nd, 2011, 6:18pm
The bots at Boardspace have to be pure java as they run as java applets, so code in any language other than java is pretty useless.    

I'd welcome an arimaa expert to collaborate on algorithms and elements for the evaluator in my robot.
Title: Re: Arimaa at Boardspace.net
Post by Janzert on Jan 3rd, 2011, 1:20am
Ahh, I didn't realize the bots ran client side. Jdb is certainly the expert in implementing Arimaa in Java (bot_clueless). For overall algorithm details Fotland had an excellent series of posts on the internals of Bomb in February of 2007 in this forum. I'm sure you're already completely familiar with the details of alpha-beta and such but you might find his eval specifics interesting.

I'll probably be using most of my spare time trying to polish OpFor up in the next two months, but I'd be glad to try and answer any specific questions  or problems you run into. I'm sure others would join in if you post them here.

Janzert
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Jan 3rd, 2011, 12:16pm
My usual technique for polishing robots is to look for examples of obviously inferior play, investigate why, and think of how to fundamentally influence better play.   It's a slow process, but heavy on innovation and light on optimizing existing code and tuning existing parameters.

The raw materials for this are examples and ideas.  Feel free to join in.
Title: Re: Arimaa at Boardspace.net
Post by Fritzlein on Jan 3rd, 2011, 1:53pm
I tried again.  The bot made 25 moves in 23 minutes.  That was vastly more enjoyable.


on 01/03/11 at 12:16:31, ddyer wrote:
The raw materials for this are examples and ideas.  Feel free to join in.

The bot missed a goal in one turn on the last move of my game.  As I understand it, static goal detection is a pain to implement, but fast and useful.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Jan 3rd, 2011, 3:27pm

on 01/03/11 at 13:53:00, Fritzlein wrote:
I tried again.  The bot made 25 moves in 23 minutes.  That was vastly more enjoyable.

The bot missed a goal in one turn on the last move of my game.  As I understand it, static goal detection is a pain to implement, but fast and useful.


This was  a simple bug - I intended that the bot see all wins in one.
Title: Re: Arimaa at Boardspace.net
Post by ddyer on Jan 8th, 2011, 2:01pm
I've made another major improvement to the evaluation function, so give it another shot if you like.


Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.