Author |
Topic: Reversible problem (Read 1502 times) |
|
haizhi
Forum Senior Member
Arimaa player #350
Gender: 
Posts: 45
|
 |
Reversible problem
« on: Jun 25th, 2005, 3:30am » |
 Quote  Modify
|
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!
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Reversible problem
« Reply #1 on: Jun 25th, 2005, 8:59am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Reversible problem
« Reply #2 on: Jun 25th, 2005, 2:06pm » |
Quote Modify
|
on Jun 25th, 2005, 8:59am, jdb wrote: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.
|
|
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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Reversible problem
« Reply #3 on: Jun 25th, 2005, 6:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Reversible problem
« Reply #4 on: Jun 25th, 2005, 7:20pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Reversible problem
« Reply #5 on: Jun 25th, 2005, 7:28pm » |
Quote Modify
|
on Jun 25th, 2005, 6:16pm, 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)
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Reversible problem
« Reply #6 on: Jun 25th, 2005, 7:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Reversible problem
« Reply #7 on: Jun 25th, 2005, 8:14pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
haizhi
Forum Senior Member
Arimaa player #350
Gender:
Posts: 45
|
|
Re: Reversible problem
« Reply #8 on: Jun 25th, 2005, 10:26pm » |
Quote Modify
|
on Jun 25th, 2005, 8:14pm, 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,
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print