| |
BGonline.org Forums
Most legal plays
Posted By: Ray Kershaw
Date: Thursday, 13 January 2011, at 11:50 p.m.
Bob Koca (Jan 05) asked what position has the greatest number of legal plays. Tom Keith (Jan 06) drew attention to an old answer by Douglas Zare:
"It's not too hard to show that the positions with the most number of moves possible will involve 1-1: Any move you can make with 2-2 can be made with 1-1 if you order the points 24-22-20-...-2-23-21-19-...1. There are too few moves possible with nondoubles or checkers on the bar or the bearoff.
The most I have found is 2226, with checkers on the 24, 23, 21, 20,...6,5, and 3. There are a few variations possible in this ordering, e.g., pushing the checker on the 5 to the 4. An easy upper bound on the number of moves possible is 18 choose 4=3060, which would be the number of ways to distribute 4 moves to 15 distinct objects, but I think that the 2226 is optimal."
I interpret Zare has having 15 checkers on the 24, 23, 21, 20, 18, 17, 15, 14, 12, 11, 9, 8, 6, 5 and 3 points. Can you explain how he counts to 2,226 ?
I can see that there are 3,060 physically possible plays of a double ace with 15 checkers on different points between the 24pt and the 5pt:
4 checkers each move one pip = 15C4 = 1,365
1 checker moves two pips and 2 checkers each move one pip = 15C1 x 14C2 = 15C2 x 13C1 = 1,365
1 checker moves three pips and 1 checker moves one pip = 15C1 x 14C1 = 210
2 checkers each move two pips = 15C2 = 105
1 checker moves four pips = 15C1 = 15
I also see that Zare’s answer of 2,226 excludes duplication of plays which result in the same position. For example, starting with a checker on the 24pt and another on the 23pt, playing 24/20 with the first checker ends up the same as playing 24/23 with the first checker and 23/20 with the second checker.
Is there some neat trick to exclude duplications or is it a programing challenge ?
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.