Author |
Topic: Avoiding reversable moves (Read 1502 times) |
|
fotland
Forum Guru
Arimaa player #211
Gender: 
Posts: 216
|
 |
Avoiding reversable moves
« on: Dec 7th, 2004, 11:04am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Avoiding reversable moves
« Reply #1 on: Dec 7th, 2004, 12:34pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Avoiding reversable moves
« Reply #2 on: Dec 7th, 2004, 4:47pm » |
Quote Modify
|
on Dec 7th, 2004, 11:04am, 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?)
|
| « Last Edit: Dec 7th, 2004, 4:49pm by 99of9 » |
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: Avoiding reversable moves
« Reply #3 on: Dec 7th, 2004, 10:04pm » |
Quote Modify
|
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 ...
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Avoiding reversable moves
« Reply #4 on: Dec 9th, 2004, 9:45am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Avoiding reversable moves
« Reply #5 on: Dec 9th, 2004, 10:30am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Avoiding reversable moves
« Reply #6 on: Dec 9th, 2004, 10:35am » |
Quote Modify
|
on Dec 9th, 2004, 9:45am, MrBrain wrote:| 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. |
|
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.
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Avoiding reversable moves
« Reply #7 on: Dec 9th, 2004, 8:56pm » |
Quote Modify
|
quiescence search and trap evaluation. No special evaluation about throwing pieces away. It's a well known search horizon effect in other games.
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Avoiding reversable moves
« Reply #8 on: Dec 9th, 2004, 8:58pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print