Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> Endgame Corner I
        
(Message started by: jdb on Jan 18^th, 2005, 11:27am)

Title: Endgame Corner I
Post by jdb on Jan 18^th, 2005, 11:27am

There was a question about the ER vs e endgame posted elsewhere on the forum. It looked interesting to me, so I did a little investigating with clueless. Here are a couple of positions to test your skills:

Ef5 Rd1 ec8 Gold to Move
Ef5 Rd3 ec8 Gold to Move
Ef5 Rc4 ec8 Gold to Move
Ef5 Rd3 ec8 Silver To Move
Ef5 Rc4 ec8 Silver to Move

The first four are all wins for gold.
Clueless thinks the last position is a draw. What do you think?

Title: Re: Endgame Corner I
Post by 99of9 on Jan 18^th, 2005, 11:55am

on 01/18/05 at 11:27:08, jdb wrote:

Ef5 Rd1 ec8 Gold to Move

Ef5w Ee5w Rd1n Rd2n ec8e ed8s ed7s Rd3n Rd4w Rc4n ed6n ed7w ec7w Ed5n Ed6n Rc5e Rd5n eb7e Ed7e Rd6n Rd7n

gold wins :-)

I *think* I can see an answer for all the possible silver plays I can think of, but there are too many possibilities to prove.

Title: Re: Endgame Corner I
Post by mouse on Jan 19^th, 2005, 1:15pm

I wonder in how many step Clueless state the wins and the draw?

And do anybody know how to calculate the number of legal moves in the positions posted by jdb it must be a finite number given the repeat rule. The number of legal move will give a indication of the size of a endgame database.

And if anybody knows the math in this then what about the number of move in a position with E+C+R against E+R.

I couldn't get a starting idea.

Title: Re: Endgame Corner I
Post by 99of9 on Jan 19^th, 2005, 2:01pm

on 01/19/05 at 13:15:59, mouse wrote:

And if anybody knows the math in this then what about the number of move in a position with E+C+R against E+R.

Here's a starting idea, a rough estimate. Each piece could occupy roughly 65 positions (64 on the board, and 1 dead). Each rabbit could occupy roughly 57 positions (anything other than the winning row). These figures are a maximum, because in many cases you can't occupy the trap square because it's not supported.

Therefore:
57*56*63*62*61=760 million possible configurations is an upper estimate. Each of these configurations requires a "best move" to generate the entire endgame table. I have not considered repeat rules in this analysis. (the reason the numbers diminish one by one is that you can't occupy a position that another piece is occupying).

760 million would take gnobby about 1000 seconds to explore. So that's definitely doable.

But to be honest I don't think endgame tables would help much in arimaa. As others have said, it's very rare to get down to so few pieces. It would be better to put the effort into getting the bots to play better at the start of the game.

Title: Re: Endgame Corner I
Post by Fritzlein on Jan 19^th, 2005, 7:28pm

on 01/18/05 at 11:27:08, jdb wrote:

Ef5 Rc4 ec8 Silver to Move
Clueless thinks the position is a draw. What do you think?

I tried it on my home version of Bomb, which pessimistically announced a goal against itself in 16 steps. Possibly this false evaluation is entirely a result of the fact that the old Bomb did not consider any moves of less than four steps, although three-step moves can be critical defensively. I'd like to try it as a test position on the new Bomb.

I am leaning towards the conclusion that Clueless is correct and the position is in fact drawn, but only if Silver plays e->d5 initially. If instead e->b5 or e->b6 then R->g4 wins. If e->d6 then E->d5 plus R->c5 appears quite strong to me, winning in fact. For Silver to hang back further allows Gold too many options and always among them some way to win.

The critical line seems to be
1b: e->d5
2w: R->b7
2b: e->b6
3w: E->c5

but then Silver can play 3b: Rb7w eb6n Ra7s eb7w. Silver can push and pull the Gold rabbit between a6 and a4, I don't see a way for Gold to pry it loose without sacrificing it.

My main hesitation in concluding that the game is drawn at that point comes from the repetition rule. After some number of moves, Silver might not be able to make the best defensive move due to repetition. Of course, there are more defensive options than shuffling on the a-file, but with any finite set of positions there will come a point of repetition. The question is whether the repetition rule will first force Silver to stop defending the goal, or first force Gold to stop defending the rabbit.

This is a very tricky question, and I'm not sure how it could be answered, even with endgame tablebases. The fact that repetition is a loss, not a draw, creates a huge complication that chess does not have. Not only must one know the configuration of pieces to evaluate a position, one must also know the entire subset of previous positions. The astronomical number of possibilities means one can't possibly build a database in a straightforward way, although there may be a trick I'm not seeing.

Does Clueless claim the position is a draw because it sees how Silver can force capture of the rabbit? If so, I'd love to see the moves, because it seems farfetched to me. But if (absent the repetition rule) Gold can't force a goal and Silver can't force capture of the rabbit, then it seems the outcome must be classified as "unknown" until the hideously complicated effect of the repetition rule can be determined. If I had to guess, I would say that repetition will work against Silver here, eventually allowing a goal, but how could one tell?

Title: Re: Endgame Corner I
Post by Fritzlein on Jan 19^th, 2005, 8:02pm

on 01/18/05 at 11:55:05, 99of9 wrote:

Ef5w Ee5w Rd1n Rd2n
ec8e ed8s ed7s
Rd3n Rd4w Rc4n
ed6n ed7w ec7w
Ed5n Ed6n Rc5e Rd5n
eb7e
Ed7e Rd6n Rd7n

gold wins :-)

I *think* I can see an answer for all the possible silver plays I can think of, but there are too many possibilities to prove.

I tried this one before reading your answer, and settled on the same first move as you did. I also agree with your length to victory: forced win for gold in four moves. Maybe other moves win too, but yours seems easiest to demonstrate.

For position two I believe that E->d6 wins in four moves.

For position three I believe that E->d6 wins in three moves.

For the fourth position, Silver's most obvious defense e->d5 is beaten by R->g4. Against other defenses R->g4 is often strong, or R->a4 if Silver goes too far west. Surprisingly Silver's trickiest defense seems to be e->e7 at the outset, but I believe this (as all other Silver defenses) allows goal in four moves.

Title: Re: Endgame Corner I
Post by fotland on Jan 19^th, 2005, 11:58pm

Bombs analysis:

Problem 1: goal in 19 steps, 0 seconds, 86K nodes
Rd1n Rd2n Rd3n Rd4e ec8s ec7e ed7e ee7e Ef5w Ee5n Re4n Re5n ef7e eg7s eg5s

Title: Re: Endgame Corner I
Post by fotland on Jan 20^th, 2005, 12:13am

Bomb's anaysis of the last problem:

Gold has goal in 24 steps. 2 seconds, 440K nodes. I don't trust it, since it found the goal during iteration 27, not iteration 21.

ec8s ec7e ed7n ed8s Rc4e Ef5w Ee5w Rd4w ed7w ec7w eb7s eb6n Rc4e Ed5n Rd4n Ed6n eb7s eb6s eb5e ec5s Rd5e Re5n Re6n Re7n

Bomb's analysis is wrong, since it only looks at 3-step moves for the first player. I'll change that and try it again.

Title: Re: Endgame Corner I
Post by fotland on Jan 20^th, 2005, 12:30am

The fixed bomb confirms your analysis of the last problem. Moving e->d5 holds off the goal for a long time. It searched 60 steps in 2 minutes with no goal.

For the first problem, allowing 3 step moves, goal in 28 steps, 1 second, 411K nodes.

Rd1n Rd2n Rd3n Rd4e ec7e ed7e ee7w Ef5w Re4e Rf4n Pass ed7e ee7e ef7e eg7s Ee5n Rf5n Rf6n Pass eg6n Rf7s eg7w Pass Rf6e ...

I think this is still wrong since bomb doesn't allow a piece to make two consecutive steps that have no effect.

Title: Re: Endgame Corner I
Post by 99of9 on Jan 20^th, 2005, 5:31am

on 01/20/05 at 00:30:45, fotland wrote:

The fixed bomb confirms your analysis of the last problem. Moving e->d5 holds off the goal for a long time. It searched 60 steps in 2 minutes with no goal.

I presume it sees no capture either? That is the critical question. Clueless claims it is a draw, which implies that silver can capture the rabbit.

I played around for a while and ended up with the rabbit stuck on a1, but I agree with Fritz that the repetition rule is vital once you get into the corner like this - who knows who wins.

By the way, if repetition rules ever do become important in arimaa, I'd like to see the game interface improved. As far as I can tell, when you try to send a move it warns you that "this is a repeat position - do you really want to play it?", but it doesn't tell you whether this is the 2nd or 3rd repeat, which is quite a critical distinction.

Title: Re: Endgame Corner I
Post by mouse on Jan 20^th, 2005, 8:00am

Since the repetition rule seems vital in a endgame I think the following should be considered.

Should it be possible to lose by repetition if the opponent has got no rabbits left on the table?

Should a player lose by repetition if the player has got no rabbits?

The first seem unreasonable to me, that a player can lose by repetition if the opponent got no other way of wining the game. In that case I think it should be a draw.

If the first is declared a draw I think to preserve symmetry between the players the second case would also have to be a draw.

Title: Re: Endgame Corner I
Post by jdb on Jan 20^th, 2005, 9:17am

For position 5:

Quote:

The critical line seems to be
1b: e->d5
2w: R->b7
2b: e->b6
3w: E->c5

Clueless has this:
D:86 01:54.12 -2670 ec8e ed8s ed7s ed6s Rc4w Rb4n Rb5n Rb6n ed5n ed6n ed7w pass Ef5w Ee5n Ee6w pass ec7n Rb7e Rc7w ec8s Ed6n Ed7n Ed8s Ed7s ec7n Rb7e Rc7w ec8s Ed6n Ed7n Ed8s Ed7s ec7n Rb7e Rc7w ec8s Ed6n Ed7n Ed8s Ed7s ec7n Rb7e Rc7w ec8s Ed6n Ed7n Ed8s Ed7s ec7n Rb7e Rc7w ec8s Ed6n Ed7n

This analysis does not take into account the repetition rule. Clueless only considers illegal repetitions on the first move. After that they are ignored.

There doesn't seem to be a forced capture, so the repetition rule will eventually come into play, and as pointed out by Fritzlein, things become complicated.

I found it very interesting that 3 step moves turned out to be important in both attacking and defending.

Title: Re: Endgame Corner I
Post by Fritzlein on Jan 20^th, 2005, 1:56pm

on 01/20/05 at 00:30:45, fotland wrote:

The fixed bomb [...] the first problem, allowing 3 step moves, goal in 28 steps, 1 second, 411K nodes.

Rd1n Rd2n Rd3n Rd4e ec7e ed7e ee7w Ef5w Re4e Rf4n Pass ed7e ee7e ef7e eg7s Ee5n Rf5n Rf6n Pass eg6n Rf7s eg7w Pass Rf6e ...

I think this is still wrong since bomb doesn't allow a piece to make two consecutive steps that have no effect.

I think the initial move by Bomb wins in four moves, just as does 99of9's suggested initial move. Goal in four moves takes a maximum of 28 steps, but the actual number of steps to goal is less than 28 if you don't count a pass as a step.

Personally, I'm not very interested in the number of steps to a win; it seems there is no reason to economize on steps on offense or maximize the number of steps on defense since the number of moves is fundamental in my mind. Talking in terms of steps is an artifact of the way computers happen to performs their searches, which is itself at least partially an artifact of the way search trees are constructed for other games. To my mind the top node of the search tree should not have as many branches as there are possible steps, it should have as many branches as there are possible moves. The search tree in my mind is extremely wide but not very deep.

Title: Re: Endgame Corner I
Post by mouse on Jan 20^th, 2005, 2:09pm

on 01/19/05 at 14:01:08, 99of9 wrote:

But to be honest I don't think endgame tables would help much in arimaa. As others have said, it's very rare to get down to so few pieces. It would be better to put the effort into getting the bots to play better at the start of the game.

Actually there might be some reasons for endgame tables. For 2 reasons:

As mentioned elsewhere in the forum the players with the highest ratings got to kill more pieces to win. Hence if the level of play improves so might the average number of kills per game and thereby the chance of a endgame.

The other use of a endgame table would be it could increase the knowledge of how the endgames work. As several players already has realised it is a very complicated situation even with only very few pieces on the board.

But for the bot develpment part I do agree.

Title: Re: Endgame Corner I
Post by Fritzlein on Jan 21^st, 2005, 11:28am

This discussion has been interesting in that it isn't clear whether the humans are testing the bots or the bots are testing the humans. I wonder if we can come up with endgame positions that computers will be able to solve but not humans, or that humans can solve but not computers. In chess I believe humans have the upper hand in all cases except some six piece or under database positions. For example KQ vs kbb, which humans not only can't play well, but also didn't even evaluate as winning for white until databases proved it to be so!

Title: Re: Endgame Corner I
Post by omar on Jan 23^rd, 2005, 1:06pm

Interesting discussion.

Here's a tool to help the humans with working out the
endgame problems:

http://arimaa.com/arimaa/games/planGame.cgi

You can use this to setup any position quickly and use
the flash client to play both side with unlimited takebacks;
even after goal is reached.

So to setup the first position presented by jdb, you
would enter:

1w Ef5 Rd1
1b ec8

In the "Game Moves" area and enter 2w for the
"Start Move". Then just click the "View" button.
The flash client should pop up with the given
position and you can play for both sides.

Title: Re: Endgame Corner I
Post by 99of9 on Jan 23^rd, 2005, 2:47pm

Wow thanks Omar, that sounds like an excellent tool. I'd been doing it using a text editor!

Title: Re: Endgame Corner I
Post by omar on Jan 28^th, 2005, 6:55pm

Another feature that I want to add to the flash client is to open up a new browser window with just the move list so it can easily be copied and pasted somewhere else. Too bad flash does not allow copying of the move list directly.

Title: Re: Endgame Corner I
Post by omar on Jan 28^th, 2005, 6:57pm

Oh by the way there is also another tool where you can get the PGN for any game in the database.

http://arimaa.com/arimaa/games/pgn.cgi