Author |
Topic: DCR vs dcr (Read 4897 times) |
|
jdb
Forum Guru
Arimaa player #214
Gender: 
Posts: 682
|
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
|
|
 IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
 |
Re: DCR vs dcr
« Reply #1 on: Sep 9th, 2008, 10:25am » |
 Quote  Modify
|
This (slowly) increases the domain where computers can defeat muggles.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: DCR vs dcr
« Reply #2 on: Sep 9th, 2008, 10:32am » |
Quote Modify
|
Amazing that there are single step moves required 22 moves before the end.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: DCR vs dcr
« Reply #3 on: Sep 9th, 2008, 10:41am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mistre
Forum Guru
Gender:
Posts: 553
|
|
Re: DCR vs dcr
« Reply #4 on: Sep 9th, 2008, 10:44am » |
Quote Modify
|
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?
|
| « Last Edit: Sep 9th, 2008, 10:57am by mistre » |
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: DCR vs dcr
« Reply #5 on: Sep 9th, 2008, 10:56am » |
Quote Modify
|
Impressive work, jdb, from a newbie programmer standpoint 
on Sep 9th, 2008, 10:44am, mistre wrote: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.
|
|
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.
|
|
IP Logged |
|
|
|
chessandgo
Forum Guru
Arimaa player #1889
Gender:
Posts: 1244
|
|
Re: DCR vs dcr
« Reply #6 on: Sep 9th, 2008, 11:00am » |
Quote Modify
|
on Sep 9th, 2008, 10:41am, Fritzlein wrote:| 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. |
|
I am stuck for words ...
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: DCR vs dcr
« Reply #7 on: Sep 9th, 2008, 11:02am » |
Quote Modify
|
on Sep 9th, 2008, 10:44am, mistre wrote:| 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. |
|
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:| What do you mean that the longest win is 47 moves? |
|
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:| Excuse my ignorance, but can someone explain the significance of this? |
|
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...
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: DCR vs dcr
« Reply #8 on: Sep 9th, 2008, 11:04am » |
Quote Modify
|
on Sep 9th, 2008, 10:44am, mistre wrote:| I still don't understand what you mean by the longest win is 47 moves though. Were their shorter wins? |
|
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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: DCR vs dcr
« Reply #9 on: Sep 9th, 2008, 12:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: DCR vs dcr
« Reply #10 on: Sep 11th, 2008, 12:15am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
ChrisB
Forum Guru
Arimaa player #2339
Gender:
Posts: 147
|
|
Re: DCR vs dcr
« Reply #11 on: Sep 13th, 2008, 6:46am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Arimabuff
Forum Guru
Arimaa player #2764
Gender:
Posts: 589
|
|
Re: DCR vs dcr
« Reply #12 on: Sep 13th, 2008, 7:56am » |
Quote Modify
|
on Sep 9th, 2008, 10:41am, Fritzlein wrote:| 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. |
|
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.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: DCR vs dcr
« Reply #13 on: Sep 14th, 2008, 10:32pm » |
Quote Modify
|
on Sep 13th, 2008, 7:56am, Arimabuff 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.
|
|
When anything is beyond our comprehension we tend to feel stupid about it.
Quote:
However, that’s no more admirable or related to intellect than to compute PI with several million decimal places.
|
|
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:
Lastly, if I were a religious man I don't think I'd find god in tedious simple tasks repeated several billion times. |
|
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
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: DCR vs dcr
« Reply #14 on: Nov 16th, 2008, 10:33pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print