Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Reversible problem
        
(Message started by: haizhi on Jun 25^th, 2005, 3:30am)

Title: Reversible problem
Post by haizhi on Jun 25^th, 2005, 3:30am

Arimanator suggest me to put all my questions at the forum, so here I am.

I just found my bot almost falls into a stuck situation in every game it played. It uses 3 step to make a pull, and the opponent use 3 step to reverse the board. This will repeats handreds times. The "repeat situation lost" rule doesn't help much, for both sides can use the extra 1 step to make the board a little different.

Fotland start a topic about "3-1 and 4-2" reversible problem before, my bot detect and remove those moves, I belive the chance of killing a good move is very small, althought it exists ( Fritzlein found at least one case).

I can enhance that pruning function to remove the "3-3" moves as also, and it will solve the problem. But I am not sure it is a good idea, cause taking the responsiblility of breaking the repetitions might hurt big.

99 pointes out that searching deepper will help, but I am testing and tuning the evaluation function, and I belive the fixed 8-step search is the best for that.

Any suggestion? Thanks!

Title: Re: Reversible problem
Post by jdb on Jun 25^th, 2005, 8:59am

Clueless prunes "3-1" "4-2" and "3-3" moves. However it only does this at the root. Deeper in the search, they are permitted.

Quote:

I can enhance that pruning function to remove the "3-3" moves as also, and it will solve the problem. But I am not sure it is a good idea, cause taking the responsiblility of breaking the repetitions might hurt big.

There are so many playable moves in a given position, that it is highly unlikely that a "3-3" move will be the best one. One could initially prune the "3-3" moves, and only try them later if no other reasonable move is found. Clueless only tries "3-3" moves if its going to lose the game otherwise.

Title: Re: Reversible problem
Post by haizhi on Jun 25^th, 2005, 2:06pm

on 06/25/05 at 08:59:04, jdb wrote:

I belive the chance of "3-3" being the best is pretty high, especilly in a defencive situation. If the enemy want pull my small piece forward, I have to draw it back, and to do so I have to advance another small piece to provide support, so I need to move it back afterward...It may be the only solution without sacrifice position.

As a human player of cause I avoid making "3-3" moves in the games, but sometimes the sacrifice is noticeable.

Thank you for your seggestion, it is reasonable, I guess I can set a penalty value for all "3-3" moves, that will help.

Title: Re: Reversible problem
Post by jdb on Jun 25^th, 2005, 6:16pm

You have a good point. Somehow I missed the case of using a "3-3" move in a defensive manner. ??? I will have to think about this some more. If a player uses a "3-3" as a defensive move, the game could still end up in an endless loop, like we have seen recently.

Suppose the defending player is not willing to accept the loop. I wonder what methods are available for breaking out of the loop. The pace of the game on the rest of the board slows to 1 step per turn, so any plan could take a very long time to execute.

Title: Re: Reversible problem
Post by haizhi on Jun 25^th, 2005, 7:20pm

Emm, then we should prune the "3-3" moves only when we are winning and the sacrifice (if there is any) is acceptaple. The plan will be:

if ( eva(the best nomal move)>=0)
// maybe put a delta here to be more aggressive?
return the best nomal move; // prune "3-3"s
else
return the best move; // no matter "3-3" or not

The implementation maybe not that easy, but we can see the point.

My question is: is this problem very common in the games played by bots, or just my bot's with 2-ply search? I doubt that playing in a fixed time and a deeper searching can completely (or almost) solve this problem, although in the computer tounament it didn't happen.

Title: Re: Reversible problem
Post by haizhi on Jun 25^th, 2005, 7:28pm

on 06/25/05 at 18:16:08, jdb wrote:

Suppose the defending player is not willing to accept the loop. I wonder what methods are available for breaking out of the loop. The pace of the game on the rest of the board slows to 1 step per turn, so any plan could take a very long time to execute.

I think the responsiblility of breaking the loop should goes to the winer. To the defending side, an ugly draw is much better than a beautiful lose.

And to play with the humans, I will turn off the "3-3" prunning function for sure.

HiaHiaHiaHia....(my devil laugh)

Title: Re: Reversible problem
Post by haizhi on Jun 25^th, 2005, 7:47pm

Another reason for me to solve this problem: I am planning using TD(lamda) to automaticlly tune weights, it will be ruined by this problem.

The only case that we should keep "3-3"s is that without using a "3-3" move the situation will be so desperate, that the loop is our only hope to avoid lose.

So I do think we should put a big delta value in the first line of my pseudo code:

if( eva(best normal move)>-0.5) // assume 1st rabbit worth 1.0
.....

Notice that "eva()" is not the static evaluation function, it is the result of dymatic search.

Title: Re: Reversible problem
Post by jdb on Jun 25^th, 2005, 8:14pm

One possible complication to keep in mind is that transposition tables do not work with path dependant evaluation.

If the same position occurs in two places, where one path used a "3-3" move and the other path did not, the transposition table will cause problems.

That's one of the reasons I only prune these types of moves at the root.

Title: Re: Reversible problem
Post by haizhi on Jun 25^th, 2005, 10:26pm

on 06/25/05 at 20:14:03, jdb wrote:

One possible complication to keep in mind is that transposition tables do not work with path dependant evaluation.

I think you are mention the values stored in the TT may not be consistant. That shouldn't be a problem, since I won't change the value, instead, I just set a flag for the "3-3" moves.

You are right, do it on the root is sufficient.

In fact, to make it simple, I am planning just pruning all the "3-3"s for now. I will go back to the above method.
if further research shows it is really necessary,