Arimaa Forum - Print Page


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

        Arimaa >> Bot Development >> Goal line rabbits
        
(Message started by: Janzert on Oct 25^th, 2008, 9:01pm)

Title: Goal line rabbits
Post by Janzert on Oct 25^th, 2008, 9:01pm

In game #86642 (http://arimaa.com/arimaa/gameroom/comments.cgi?gid=86642) Gnobot hung it's elephant on a trap because it didn't understand that the opponent could pull a rabbit onto the goal line then push it back off to capture the elephant and still avoid giving Gnobot the goal. Funnily enough it turns out that Bomb didn't understand it either so the game continues for several moves with the elephant left hanging.

I knew that OpFor handles this correctly at the root but not in the search¹. I had simply figured it would have very little chance of ever causing a problem in an actual game. But this means while OpFor will correctly capture the E at 43s, I was fairly easily able to make a simplification of 43g that OpFor thinks is a forced win for gold while actually being (I think) a forced win for silver.

43w
+-----------------+
8| . . d . . . . . |
7| r r r C . . . . |
6| D m R E . x . r |
5| d H . . . . . . |
4| . . . . . . . . |
3| . . x . . x . . |
2| . . . . . . . . |
1| . . . . . . . . |
+-----------------+
a b c d e f g h

Since it can't see the elephant capture in the search OpFor currently gives:
depth 11
pv Cd7e rc7e Rc6n Ed6w b dc8e dd8w rh6s rh5s w Ce7n rd7e Rc7e Ec6x
log: Sending forced win move in 1.13 seconds.
bestmove: Cd7e rc7e Rc6n Ed6w

Although if it then analyses the resulting position it quickly comes up with this winning line since it can now see the E capture:
depth 16
pv dc8e Rc7n Ec6x Rc8s dd8w w Ce7s Ce6w Cd6w Cc6s b rh6s rh5s rh4s rh3s w Cc5n Cc6s Cc5n
log: Sending forced win move in 2.97 seconds.
bestmove: dc8e Rc7n Ec6x Rc8s dd8w

I'm not sure yet whether it will be worth fixing this in OpFor since I'm not sure there is a simple way to do it that won't hurt overall performance. In any case though it is certainly an interesting position and led to quite a funny ending to the above game.

Janzert

¹ The actual comment in the code is,

Code:

// This is actually technically incorrect as it disallows
// pushing a rabbit onto then back off of the goal line

Title: Re: Goal line rabbits
Post by jdb on Oct 26^th, 2008, 5:38am

This is how Clueless checks if the game is over. It was written before the rules were changed, so it could be simplified. The tests are reasonably fast and it handles temporarily goaling rabbits properly.

The indentation on the code got messed up when I copied it, and I'm not really sure how to fix it.

Code:

// This table tells if the game is over by rabbit goal
// An enemy rabbit can be in the goal, if there are steps remaining!
private static final boolean table_is_game_over[] = {
//G4 G3 G2 G1 S4 S3 S2 S1
FL, FL, FL, FL, FL, FL, FL, FL, // G=F, S=F
TR, FL, FL, FL, TR, TR, TR, TR, // G=F, S=T
TR, TR, TR, TR, TR, FL, FL, FL, // G=T, S=F
TR, TR, TR, TR, TR, TR, TR, TR, // G=T, S=T
};

private static int NA = SCORE_UNKNOWN;
private static int WN = +SCORE_MATE;
private static int LS = -SCORE_MATE;

private static final int table_get_game_result[] = {
//G4 G3 G2 G1 S4 S3 S2 S1
NA, NA, NA, NA, NA, NA, NA, NA, // G=F, S=F
WN, NA, NA, NA, LS, WN, WN, WN, // G=F, S=T
LS, WN, WN, WN, WN, NA, NA, NA, // G=T, S=F
WN, WN, WN, WN, WN, WN, WN, WN, // G=T, S=T
};

/**
* Considers only current gamestate, no previous move required
* @return boolean
*/

private static boolean use_no_rabbits_is_a_loss = true;

/**
* Call this at the root before starting the search
* If both sides have rabbits, use no rabbits is a loss
* If either side is out of rabbits, use no rabbits is NOT a loss
*/
public void determine_rule_set() {
use_no_rabbits_is_a_loss = true;
if ( (piece_bb[0] == 0) || (piece_bb[1] == 0)) {
use_no_rabbits_is_a_loss = false;
}
LogFile.message("Use tournament rules: " + use_no_rabbits_is_a_loss);
}

public boolean isGameOver() {

// Test if there are no rabbits left
if ( (piece_bb[0] | piece_bb[1]) == 0) {
return true;
}

// Test for rabbit goal / all rabbit capture
int gold_goal, silver_goal;

if (use_no_rabbits_is_a_loss) {
gold_goal = ( ( (piece_bb[0] & RANK_8) != 0) || (piece_bb[1] == 0)) ? 1 : 0;
silver_goal = ( ( (piece_bb[1] & RANK_1) != 0) || (piece_bb[0] == 0)) ? 1 :
0;
}
else {
gold_goal = ( (piece_bb[0] & RANK_8) != 0) ? 1 : 0;
silver_goal = ( (piece_bb[1] & RANK_1) != 0) ? 1 : 0;
}
int steps = total_steps & 0x07;
int index = steps + (gold_goal << 4) + (silver_goal << 3);
return table_is_game_over[index];
}

/**
* Returns result of game SCORE_MATE,SCORE_DRAW,-SCORE_MATE
* From perspective of side to move at start of *previous* step
* @return int
*/
public int getGameResult() {
assert (isGameOver() == true);

// Test if there are no rabbits left
// Rare case possible no rabbits could win!
if (!use_no_rabbits_is_a_loss) {
if ( (piece_bb[0] | piece_bb[1]) == 0) {
return SCORE_DRAW;
}
}

// Test for rabbit goal / all rabbit capture
int gold_goal, silver_goal;
if (use_no_rabbits_is_a_loss) {
gold_goal = ( ( (piece_bb[0] & RANK_8) != 0) || (piece_bb[1] == 0)) ? 1 : 0;
silver_goal = ( ( (piece_bb[1] & RANK_1) != 0) || (piece_bb[0] == 0)) ? 1 :
0;
}
else {
gold_goal = ( (piece_bb[0] & RANK_8) != 0) ? 1 : 0;
silver_goal = ( (piece_bb[1] & RANK_1) != 0) ? 1 : 0;
}
int steps = total_steps & 0x07;
int index = steps + (gold_goal << 4) + (silver_goal << 3);

assert (table_get_game_result[index] != NA);
return table_get_game_result[index];

}

Title: Re: Goal line rabbits
Post by tize on Nov 1^st, 2008, 5:39am

If you give the isEndState function information about who to take the next step and if that player already has taken some steps then you can have something like this in the code.

Code:

function isEndState
...
if( goldToMove or noStepsTaken ) checkForGoldGoal

if( silverToMove or noStepsTaken ) checkForSilverGoal
...

The eval function should then give huge bonuses for to a player with rabbits on the goal line to minimize the cost of searching deeper at thoose nodes.

I have to go and fix this in carlos... not that he will be able to beat Bomb after that...

Title: Re: Goal line rabbits
Post by Janzert on Mar 11^th, 2009, 7:45pm

Just as an update since I ran across this thread while browsing for something else. I did fix this in OpFor before the 2009CC.

Janzert