Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Avoiding reversable moves
        
(Message started by: fotland on Dec 7^th, 2004, 11:04am)

Title: Avoiding reversable moves
Post by fotland on Dec 7^th, 2004, 11:04am

All bots have the problem that they sometimes make moves that easily reversed by the opponent. If the bot uses 3 steps to pull a piece, and the can move back to its original position in one step, the bot just loses time.

This is a difficult problem to fix.

If the search ends with the opponent to move, the search will discover that there is no forward progress and not make the move. The problem is that most bots are looking about 11 steps deep, so they must evaluate the position without giving the opponent a chance to move away.

It would be easy if all reversible moves were bad, since they are easy to detect, and I could just not make them. The problem is that sometimes a reversible move also exposes some threat, so that the opponent doesn't have time to reverse it.

I could detect a reversible move and extend the search until the opponent has the move, and then extend more to reverse it, but I think that will slow down the search a lot.

I could use some help from stronger players in defining the conditions necessary to prove that a reversible move can be eliminated from consideration.

Any ideas?

Title: Re: Avoiding reversable moves
Post by jdb on Dec 7^th, 2004, 12:34pm

I agree, this is a tricky problem. Just thinking outloud, here are my thoughts on the problem.

Instead of trying to detect a reversible move ahead of time, detect it after the fact. So lets say the search starts with a 4 step move. The player's turn is up, so make a note of the current position. During the next 1,2,3 steps, test if the position has been restored. If nothing extraordinary happens in this sub-tree, it is probable the original move was pointless (reversible without danger). As you mentioned, this won't work deep in the search, but it will work at the root. If the search is 11/12 steps it should also work for the second turn in the search as well.

Title: Re: Avoiding reversable moves
Post by 99of9 on Dec 7^th, 2004, 4:47pm

on 12/07/04 at 11:04:49, fotland wrote:

I could use some help from stronger players in defining the conditions necessary to prove that a reversible move can be eliminated from consideration.

Say we're talking about a move that requires 3 steps but can be reversed in 1 (there's a similar case that requires 4 but can be reversed in 2).

I am willing to make the reversible 3 steps IF AND ONLY IF:
* I feel I can do more with my remaining 1 step than my opponent can do with their bonus 3 steps.

This is only rarely true, but comes up most often in 2 cases:
(1) I have some kind of imminent goal, and my opponent doesn't. The imminent goal is not possible to stop unless my opponent uses a full 4 steps. Therefore I do something reversible that requires the use of at least 1 step to reverse.
(2) The main threat my opponent has is to kill a piece of mine, but it will require 4 steps. On the rest of the board I am dominant - and can fully secure that dominance even using only 1 step per turn. Note this dominance will have to be established by freezing, because I don't have enough steps to push or pull.

I think these are the only 2 cases I've seen, but maybe someone will correct me.

I haven't thought about the case that I do 4 steps and he can reverse in 2. I imagine this is never good except to delay certain death? (or to angle for some kind of repetition?)

Title: Re: Avoiding reversable moves
Post by PMertens on Dec 7^th, 2004, 10:04pm

I haven't thought about the case that I do 4 steps and he can reverse in 2. I imagine this is never good except to delay certain death? (or to angle for some kind of repetition?)

Sure it can be usefull ... just rare.
Imagine a situation where after the situation is undone 3-4 steps would be needed to do harm - and the other free pieces are to weak / malpositioned to be of any interest.

actually I am quite certain you can ignore that.

1 in a million positions might be secured - and all the other positions are slower to ponder ?
Maybe you can keep that move as a last resort if all other moves are bad ...

Title: Re: Avoiding reversable moves
Post by MrBrain on Dec 9^th, 2004, 9:45am

Also, don't just focus on "reversable moves", but also moves that are even worse than reversable. For example, a bot moves a rabbit 4 spaces to go next to a trap and prevent a camel from being trapped in the next move. The human simply traps the rabbit, returning to the same position as before, minus the rabbit. I've seen bots do this a lot.

Title: Re: Avoiding reversable moves
Post by Fritzlein on Dec 9^th, 2004, 10:30am

Well, I finally saw an example of "three steps which can be reversed in one step" which was reasonable. In game 10152 on move 30 I forked speedy's horse. Speedy took 3 steps to create a threat to my horse and one step to bring a second defender closer. I couldn't execute my capture threat after using one step to save my horse, and it wasn't obvious how to use my extra three steps to good advantage. I could have used the steps to secure a horse frame, but that would have required my horse to maintain the frame and left speedy with a spare horse to patrol the rest of the board.

Anyway, the moral of the story might be to concentrate on doing the easy thing first, namely eliminating four steps that can be reversed in two. It's trivial to check after six steps whether the position is the original one, and although speedy now considers three-step moves for itself, that complication is perhaps not insurmountable.

Incidentally, did you allow three-step moves for speedy by calling a null-step on the fourth step legal? Or do your branches perhaps get out of synch, so at depth twelve it could have been either one-and-a-half complete moves of four steps each, or two complete moves of three steps each? Or maybe it is technically more complicated than my poor brain can handle.

Title: Re: Avoiding reversable moves
Post by Fritzlein on Dec 9^th, 2004, 10:35am

on 12/09/04 at 09:45:48, MrBrain wrote:

I've noticed that speedy did this a little when it first came back on line, and then stopped again. You must already have an answer of sorts to this conundrum. Do you mind sharing the outlines? I'm betting it has nothing to do with hashing or checking for near-identicalness of the position.

Title: Re: Avoiding reversable moves
Post by fotland on Dec 9^th, 2004, 8:56pm

quiescence search and trap evaluation. No special evaluation about throwing pieces away. It's a well known search horizon effect in other games.

Title: Re: Avoiding reversable moves
Post by fotland on Dec 9^th, 2004, 8:58pm

I allowed 3 step moves by making pass legal during the ply 4 of the search only. It slows the search down about 10%, but seems worth it.