|
||||||
|
Title: DCR vs dcr Post by jdb on Sep 9th, 2008, 6:00am The DCR vs dcr tablebase is finished. It started on June14 and finished on September 03. The longest win is 47 moves. 1w Rc1 Dh1 Cg3 1b dh2 re8 cf8 2w Rc1w Dh1w Dg1w Df1n 2b cf8s re8e cf7w dh2w 3w Rb1w Df2n Df3n 3b ce7w cd7w cc7w cb7s 4w Df4e Cg3e Ch3n Ch4n 4b rf8w re8w cb6s cb5w 5w Ch5w Dg4w Df4w De4n 5b rd8w rc8w ca5s ca4s 6w Cg5w De5w Cf5w Ce5n 6b rb8w ca3s dg2w df2w 7w Ce6w Cd6n Cd7w Dd5s 7b Ra1e ca2s de2w dd2w 8w Cc7w Cb7n Dd4s 8b dc2w db2n db3n db4n 9w ra8s Cb8w Dd3s Dd2w 9b db5w da5n ra7e da6e 10w Ca8e Dc2w Rb1e Rc1e 10b rb7e rc7e rd7e db6n 11w Rd1e Re1e Rf1e Rg1e 11b re7e rf7e db7e dc7e 12w Cb8s Cb7s Cb6s Cb5s 12b ca1e dd7s dd6s dd5s 13w Db2e Dc2e Dd2e De2e 13b cb1e cc1e cd1e dd4e 14w Cb4s Df2e Dg2n Dg3n 14b de4e df4n df5e dg5n 15w Cb3s Cb2e Cc2e Cd2e 15b ce1e cf1e Rh1n cg1e 16w Ce2e Cf2e Rh2n Dg4n 16b rg7e ch1n dg6e dh6s 17w Cg2n Rh3n Cg3s Cg2w 17b dh5n Rh4n dh6w Rh5n 18w Cf2w Ce2n Ce3n Dg5w 18b dg6s dg5e dh5w Rh6s 19w Df5s Df4e Dg4e Rh5n 19b ch2s ch1w cg1w dg5n 20w Ce4n Ce5n Dh4w Dg4n 20b rh7w cf1e rg7e cg1e 21w Dg5w Df5n Df6n Df7e 21b ch1n ch2n ch3n 22w Dg7w Df7s Df6s 22b ch4s ch3s ch2s 23w Ce6s Df5e Ce5n 23b ch1w cg1w cf1w ce1w 24w Dg5w Df5n Df6n Df7e 24b cd1n cd2n cd3n cd4n 25w Dg7w rh7w Df7s rg7w 25b cd5n cd6n cd7e rf7e 26w Df6n 26b rg7e 27w Df7s ce7e cf7n Df6n 27b dg6n Rh6w Rg6s dg7s 28w Ce6s Ce5e Rg5e 28b dg6s dg5n Rh5w 29w Rg5e Rh5n Cf5s 29b dg6s dg5e dh5w Rh6s 30w Cf4n Df7e Dg7s rh7w 30b cf8s rg7e Cf5s dg5w 31w Rh5n Dg6n Dg7s rh7w 31b rg7e cf7s cf6n cf7e 32w cg7n Dg6n Dg7w rh7w 32b rg7e df5e dg5e 33w Cf4e Cg4s Cg3e Ch3n 33b Ch4s dh5s dh4n 34w Ch3n Df7n Df8s cg8w 34b rh7w dh5w dg5n rg7e 35w Ch4s Ch3s Ch2w Cg2n 35b dg6s Rh6w dg5s Rg6s 36w Df7e Dg7w rh7w 36b dg4w Cg3n df4n Cg4w 37w rg7s Df7e rg6w Dg7s 37b cf8e cg8e ch8s ch7s 38w Rg5e Dg6s ch6w Rh5n 38b Rh6s cg6e rf6e 39w Dg5s Cf4w Ce4s Dg4n 39b ch6n ch7w rg6e cg7s 40w Ce3s Ce2s cg6n Dg5n 40b df5s df4e dg4n 41w Ce1w Cd1n Cd2e 41b dg5s Rh5w dg4w df4n 42w Rg5e Dg6s rh6w Rh5n 42b cg7e Rh6s ch7s 43w Ce2n rg6w Dg5n 43b rf6w re6s df5e 44w Ce3n re5n Ce4n 44b dg5w Ce5s df5w 45w Dg6s ch6w Rh5n 45b re6e de5e Rh6s cg6e 46w Ce4w Cd4n Cd5n Dg5n 46b rf6w df5w de5w 47w Dg6s ch6w Rh5n 47b dd5s 48w Cd6s Dg5e Rh6n Rh7n |
||||||
|
Title: Re: DCR vs dcr Post by RonWeasley on Sep 9th, 2008, 10:25am This (slowly) increases the domain where computers can defeat muggles. |
||||||
|
Title: Re: DCR vs dcr Post by Janzert on Sep 9th, 2008, 10:32am Amazing that there are single step moves required 22 moves before the end. Janzert |
||||||
|
Title: Re: DCR vs dcr Post by Fritzlein on Sep 9th, 2008, 10:41am Playing this out in the plan window is absolutely mind-blowing. I have to keep reminding myself that all of these moves are optimal, even though sometimes I can't even see the general point of what they are supposed to accomplish. I have felt stupid about Arimaa before, but this raises the feeling to a new level. |
||||||
|
Title: Re: DCR vs dcr Post by mistre on Sep 9th, 2008, 10:44am Excuse my ignorance, but can someone explain the significance of this? What do you mean that the longest win is 47 moves? How often is a game played when both E's are off the board? Which is why I am puzzled with the relevance of DCR vs DCR. Edit: Nevermind. DCR = ECR. There is no difference in this instance. I watched it in the plan menu and it was fascinating but also perplexing. I still don't understand what you mean by the longest win is 47 moves though. Were their shorter wins? |
||||||
|
Title: Re: DCR vs dcr Post by chessandgo on Sep 9th, 2008, 10:56am Impressive work, jdb, from a newbie programmer standpoint :) on 09/09/08 at 10:44:08, mistre wrote:
I am very ignorant to these things as well ; what I understand is that there is a position where the quickest way to win for the winning side against the best defense by the losing sides takes these 47 moves. DCR vs dcr is equivalent to ECR vs ecr ; jdb is just collapsing empty classes. As for the relevance, I can't tell. |
||||||
|
Title: Re: DCR vs dcr Post by chessandgo on Sep 9th, 2008, 11:00am on 09/09/08 at 10:41:22, Fritzlein wrote:
I am stuck for words ... |
||||||
|
Title: Re: DCR vs dcr Post by Fritzlein on Sep 9th, 2008, 11:02am on 09/09/08 at 10:44:08, mistre wrote:
It is functionally equivalent to EXR vs EXR, where X can be M, H, D, or C. I don't think there has been a ECR vs. ECR endgame in the history of Arimaa, certainly not since the rabbit-elimination rule changed, but we have come close a couple of times. Quote:
If you put these six pieces at random on the board, one side or the other has a forced win, as a logical consequence of the rules. Often we can't tell who has the forced win, or what move wins most quickly. However, if jdb has correctly constructed his database, then he does know who wins nearly every such position, and does know the winning move. JDB's database is a great source of "Goal in 3" or "Goal in N" puzzles. So far, the most impressive-sounding puzzle he can give you is "Goal in 47". Quote:
Hmmm... We'll, it is interesting. It might not have any significance in terms of winning the Arimaa World Championship. On the other hand, the Arimaa World Championship itself might not have any significance, when you take a broad view of things... |
||||||
|
Title: Re: DCR vs dcr Post by Fritzlein on Sep 9th, 2008, 11:04am on 09/09/08 at 10:44:08, mistre wrote:
Gold can't force a win in fewer than 47 moves if Silver defends properly. There is no position in JDB's database where he can demonstrate a win that is forced, but takes longer than 47 moves. |
||||||
|
Title: Re: DCR vs dcr Post by jdb on Sep 9th, 2008, 12:33pm Just to clarify, the one step moves in the middle of the solution are not necessarily unique. It is possible that a move taking a different number of steps will also lead to a win in the same number of moves. |
||||||
|
Title: Re: DCR vs dcr Post by omar on Sep 11th, 2008, 12:15am Nice work Jeff. You're becoming the Ken Thompson of Arimaa :-) Even in chess the end games look quite bizarre and the moves are totally unexplainable. Way beyond human comprehension. As Paul Erdos would say: these games are from The Book :-) http://research.swtch.com/2008/01/play-chess-with-god.html |
||||||
|
Title: Re: DCR vs dcr Post by ChrisB on Sep 13th, 2008, 6:46am Good work, jdb. I'm impressed you were able to complete the tablebase as quickly as you did. It must have involved a lot of creative programming. I was wondering what the total number of positions for those six pieces in an unfinsihed game would be and came up with a lower bound of 30*59*58*57*48*47 = 13.20 billion and an upper bound of 32*63*62*61*52*52 = 20.62 billion. Thus, over the 11 to 12 weeks, one way or another, you were able to solve on average around 2,000 positions per second. One interesting question could be answered by working on only a small subset of the total number of positions: Which color can force a win if arimaa is limited to only these six pieces? If each player is still allowed to set up in their first two rows, gold has 8*15*14 = 1680 possible setups; and for each of these setups, silver has 16*15*14 = 3360 possible responses. So, if at least one of those gold setups wins against all of silver's 3360 responses, gold can force a win. Otherwise, silver can force a win. |
||||||
|
Title: Re: DCR vs dcr Post by Arimabuff on Sep 13th, 2008, 7:56am on 09/09/08 at 10:41:22, Fritzlein wrote:
What's there to feel stupid about? At its beginning it is a solution to a goal in 47-move problem, we can't even imagine one to a goal in five move’s without computer help, that's way beyond human comprehension. However, that’s no more admirable or related to intellect than to compute PI with several million decimal places. Lastly, if I were a religious man I don't think I'd find god in tedious simple tasks repeated several billion times. |
||||||
|
Title: Re: DCR vs dcr Post by omar on Sep 14th, 2008, 10:32pm on 09/13/08 at 07:56:58, Arimabuff wrote:
When anything is beyond our comprehension we tend to feel stupid about it. Quote:
Computers make it easy for us to do this, but if you didn't have a computer to help you it would be considered an intellectual achievement and you would definitely feel very proud of each digit of PI you discovered. "The first major European contribution since Archimedes was made by the German mathematician Ludolph van Ceulen (1540–1610), who used a geometrical method to compute 35 decimals of PI. He was so proud of the calculation, which required the greater part of his life, that he had the digits engraved into his tombstone." http://en.wikipedia.org/wiki/Pi Quote:
It's quite deceiving, but in fact simple tasks repeated iteratively can give rise to incredibly complex phenomenon. There are some who believe the universe itself could arise from the iterative repetition of some very simple rules. http://blog.wolfram.com/index.php?year=2007&monthnum=09&name=my-hobby-hunting-for-our-universe |
||||||
|
Title: Re: DCR vs dcr Post by 99of9 on Nov 16th, 2008, 10:33pm I only just looked through this! What fantastic work. I kept trying to find holes in this game, but most of my preferred moves resulted in a near-immediate loss when I played with them in the plan window. |
||||||
|
Title: Re: DCR vs dcr Post by chessandgo on Feb 25th, 2010, 3:38am Digging up this old (awesome) thread. I'm considering giving an example of EMR vs edcrr in my book to illustrate the importance of the number of pieces over their strength in an endgame, perhaps something like: 1w Ed4 Rd1 Mf2 1b ed5 ra8 rh8 cf7 dc7 I wonder whether a bot or some kind of exhaustive search can prove that silver is winning even with gold to play in a position like the above. What do you programming wizards think? |
||||||
|
Title: Re: DCR vs dcr Post by jdb on Feb 25th, 2010, 6:54am The current bots are not able to solve a position with 8 pieces still on the board. However, with rabbits new GUI it would be easy enough to play against a bot offline, starting from any position. This would let you play out some lines to demonstrate the proper technique in your book. |
||||||
|
Title: Re: DCR vs dcr Post by chessandgo on Feb 25th, 2010, 7:24am Ok. I was just checking, I'm not going to go into any line in the book, I merely wondered whether someone would come up after the book is released and say: well, the position you assess as won for silver is actually a goal in 15 for gold :) |
||||||
|
Title: Re: DCR vs dcr Post by Hippo on Feb 25th, 2010, 8:40am What about other databases with 6 pieces? The most important are with both having the same strongest piece (HCR/hdr). There were 2 symmetries in DCR/dcr (East-West, North-South) which can be used so ~ 65*64*63*62*60*59*2/4>234 ... roughly 4GB of resulting space with 1 bit per position. But you need a bit indicating not known result yet ... so around additional 4GB of space during computation required. I suppose most of positions lead to "immediate" end so the "unknown result yet" shrinks fast. ... The computational time is not so surprising :). In HCR/hdr the North-South symmetry vanishes. I am happy that Arimaa game ends mostly with 10 or more pieces on the board. |
||||||
|
Title: Re: DCR vs dcr Post by RonWeasley on Feb 25th, 2010, 8:54am I really like these kind of results. While some folks have expressed disinterest, I think there are those of us who would like to see more. jdb is my hero. |
||||||
|
Title: Re: DCR vs dcr Post by jdb on Feb 25th, 2010, 1:22pm on 02/25/10 at 08:40:31, Hippo wrote:
Only 1 bit per position is required for computation. I don't remember off the top of my head how it worked. I'd have to look it up. 4Gb is enough memory to do the 6 piece tablebases (barely). The initial gold rabbit can only go on 28 squares. The board has left/right symmetry. The gold rabbit can't be on the 8th rank, since the game would be over. It also can't be off the board, since the game would also be over. The initial silver rabbit can only go on 48 squares. It can't be on the first rank, since the game would be over. The other pieces can be on 65 squares. Anywhere on the board, plus off the board. Tighter indexing is possible. This method allows the 6 piece tables to be done using 4Gb. Even with better indexing 7 pieces takes alot of memory. |
||||||
|
Title: Re: DCR vs dcr Post by jdb on Feb 25th, 2010, 1:24pm on 02/25/10 at 08:54:57, RonWeasley wrote:
It should be possible to do something with rabbits GUI to allow people to play around with the endgame puzzles. |
||||||
|
Title: Re: DCR vs dcr Post by Hirocon on Feb 25th, 2010, 2:55pm Do these results take into consideration the 3-repeat rule? I remember seeing a ER v. r position where silver to move has a forced win, but only because of the 3-repeat rule (without the rule the position would be a draw). Do situations like that ever arise on any DCR v. dcr positions? |
||||||
|
Title: Re: DCR vs dcr Post by jdb on Feb 25th, 2010, 3:31pm on 02/25/10 at 14:55:32, Hirocon wrote:
The tablebase ends up recording 3-repeat positions as "unknown". When the engine probes the tablebase it has to figure out itself which side wins using repetition. In practice these types of positions are easy to figure out. The 3-repeat type positions occur in all the tablebases I have made so far. |
||||||
|
Title: Re: DCR vs dcr Post by Fritzlein on Feb 25th, 2010, 4:27pm on 02/25/10 at 03:38:30, chessandgo wrote:
I'm not a programming wizard, but this looks like a goal in at least six for Silver with Gold to move. That's a 48-step search. Even with reduced branching factor deepening the possible search, and even with static goal evaluation knocking (say) 8 steps off the end of the search, I'm guess the 40-step exhaustive search proof you are looking for is not forthcoming. |
||||||
|
Title: Re: DCR vs dcr Post by rabbits on Feb 26th, 2010, 8:33am on 02/25/10 at 13:24:36, jdb wrote:
This would be cool! If you want any particular feature added, let me know. |
||||||
|
Title: Re: DCR vs dcr Post by Hippo on Apr 5th, 2010, 6:25am http://arimaa.com/arimaa/gameroom/comments.cgi?gid=140298 is a game where this analysis could be helpful. BTW: 20b rh7w cf1e rg7e cg1e = 20b cf1e cg1e 23w Ce6s Df5e Ce5n = 23w Df5e We get the same position after 23w as after 20b so that must be one sided zugzwang! 31b rg7e cf7s cf6n cf7e = 31b rg7e cf7e 33w Cf4e Cg4s Cg3e Ch3n = 33w Cf4e Cg4e 34b rh7w dh5w dg5n rg7e = 34b dh5w dg5n 35w Ch4s Ch3s Ch2w Cg2n = 35w Ch4s Ch3w 40b df5s df4e dg4n = 40b df5e 41w Ce1w Cd1n Cd2e = 41w Ce1n 41b dg5s Rh5w dg4w df4n = 41b dg5w Rh5w 48w Cd6s Dg5e Rh6n Rh7n is illegal, should be 48w cg6w Dg5n Rh6n Rh7n or 48w Cd6n re6w rd6w rc6x Cd7s Wow 44w capturing the silver cat would lead to gold elimination. A lot of one sided zugzwangs. I suppose most of the positions remain in state "unknown". |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |