Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> Win in Two Puzzles
        
(Message started by: MKA on Jan 16^th, 2012, 10:36pm)

Title: Win in Two Puzzles
Post by MKA on Jan 16^th, 2012, 10:36pm

Hi all!

I've started to play around with heuristics for Arimaa as a part of my AI research and of particular interest to me are the win in two puzzles I found in the Games section of the site. How are those puzzles compiled? Are they all chosen by humans? I can't imagine that a poor, hardworking bot is out there slaving over every turn of every game, looking two turns deep into the search tree... or is there? :O

And can someone explain to me why Game 9, 12b is a Win in 2? I'm sure I'm just being stupid and missing something simple, but I haven't been able to understand how that one is a win for silver in two turns. >_<

Thanks!
- MKA

Title: Re: Win in Two Puzzles
Post by rbarreira on Jan 17^th, 2012, 4:47am

It shouldn't be so hard to find goal in 2 puzzles. Almost every bot vs bot game ended by goal should have a goal-in-2 position at the second-from-last ply. Exceptions would be games where a bot allowed a goal-in-1 due to a bug, games where a bot unnecessarily delays its victory (most bots do not do this) and games against P1 bots without static goal detection.

Bots with search extensions and static goal detection can identify goal-in-2 positions almost instantaneously, so one could take all those second-from-last positions of each BvB game and quickly get a list of hundreds / thousands of goal-in-2 positions.

Title: Re: Win in Two Puzzles
Post by Fritzlein on Jan 17^th, 2012, 8:04am

on 01/16/12 at 22:36:17, MKA wrote:

I've started to play around with heuristics for Arimaa as a part of my AI research and of particular interest to me are the win in two puzzles I found in the Games section of the site. How are those puzzles compiled? Are they all chosen by humans? I can't imagine that a poor, hardworking bot is out there slaving over every turn of every game, looking two turns deep into the search tree... or is there? :O

There is a list of human-compiled puzzles here:
http://arimaa.com/arimaa/puzzles/list.cgi

I believe that the list you refer to is here:
http://arimaa.com/arimaa/games/puzzles.txt

The latter was compiled by Omar with the help of bot_Bomb2005. As Ricardo explains, that is not too CPU intensive. (Although combing every game in the database for goal-in-three would be.) Omar's idea was that humans could take this list as a starting point and vet it for good puzzles to add to the human-compiled list. No one followed up on the idea. It turns out that the criterion "There exists a move that forces goal in two" is not a very good indicator of a good puzzle; humans would like the winning move to be at least unique (which Bomb did not guarantee) and hopefully also interesting (subjective and apparently relatively rare).

Quote:

And can someone explain to me why Game 9, 12b is a Win in 2? I'm sure I'm just being stupid and missing something simple, but I haven't been able to understand how that one is a win for silver in two turns.

If we are talking about this game: http://arimaa.com/arimaa/gameroom/opengamewin.cgi?client=1&gameid=9&role=v&side=w
then I don't see the win either. I believe that the only person who can clear up the mystery is Omar, because he created the list and nobody else used it.

Title: Re: Win in Two Puzzles
Post by omar on Jan 17^th, 2012, 10:33pm

Can you give the link to the puzzle that seems to be in error.

I once ran a bot on some of the early games to find puzzles. You can find a list of the puzzles here:

http://arimaa.com/arimaa/puzzles/auto/list.cgi

and a somewhat searchable version here:

http://arimaa.com/arimaa/puzzles/auto/list2.cgi

With all the games we have now I wonder how many such puzzles are out there. Also another interesting thing I've thought about, but never got around to trying is categorizing the puzzles in terms of how difficult they are for humans. I know that some win in two puzzles are much harder than others; at least for me and probably other humans as well. But I am not sure quite what it is that makes them hard. Bot developers might find this an interesting area to explore, since it could make the bot stronger against humans. If the puzzles could somehow be categorized then the very hard ones could be mined from the games archive to automatically generate a list of very interesting puzzles; interesting for humans at least.

Title: Re: Win in Two Puzzles
Post by MKA on Jan 17^th, 2012, 11:36pm

It's the third game listed here: http://arimaa.com/arimaa/games/puzzles.txt. The winning move is apparently to move the silver elephant from e3 to c5. I can see how it would be a good move to make, but does it guarantee a win the next turn? Speaking of which, is that how the bot decides that this is a win in 2 puzzle? By making the "winning move", the player is in such a position that he or she will definitely win the next turn no matter what the opponent does?

I think it would be extremely interesting to study what makes certain puzzles difficult or easy for humans, since it gives an interesting insight into how we think.

Title: Re: Win in Two Puzzles
Post by omar on Jan 19^th, 2012, 11:55am

I don't see goal in two for either player. I don't know how that got into the file. I've manually taken it out. Let me know if you come across any more like this.