Solving 421 game one chip heads-up variant with minmax algorithm using Markov decision process, dynamic programming and symmetry breaking
Let Xra be the discrete random variable of a dice throw given optional : prior combination r and action a.
Every function is computed from the starting player's perspective.
Let eval(r1, r2) return 1 if combination r1 has a better ranking than r2, 0.5 if tie and 0 otherwise.
Let g(r1, r2, t) be the winning odds for a fixed combination r1 against r2 with t rerolls left to use.
Let f(r1, t) be the winning odds with current combination r1 and t rerolls already done.
Let A be the set of all actions one player can take (for each dice wether or not it gets rerolled).
For an overall weighted winrate of 60.0044%
for the starting player.
Table representation of f.
Action column denotes the optimal strategy by showing which dice to keep.
(For the second player, g results are available under results folder with the facing roll as file name)
r \ t | 0 | 1 | 2 | |||
win% | action | win% | action | win% | action | |
421 | 98.61% | 421 | 94.23% | 421 | 88.59% | 421 |
111 | 96.99% | 111 | 87.94% | 111 | 76.63% | 111 |
611 | 96.06% | 611 | 85.80% | 611 | 73.44% | 611 |
666 | 95.14% | 666 | 83.60% | 666 | 70.45% | 666 |
511 | 94.21% | 511 | 82.02% | 511 | 67.98% | 511 |
555 | 93.29% | 555 | 79.42% | 555 | 63.91% | 555 |
411 | 92.36% | 411 | 76.90% | 411 | 60.82% | 411 |
444 | 91.44% | 444 | 73.99% | 444 | 56.60% | 444 |
311 | 90.51% | 311 | 72.30% | 311 | 54.82% | 311 |
333 | 89.58% | 333 | 70.84% | 333 | 53.44% | 333 |
211 | 88.66% | 211 | 69.38% | 211 | 52.03% | 211 |
222 | 87.73% | 222 | 67.98% | 222 | 50.64% | 222 |
654 | 86.11% | 654 | 66.24% | 654 | 49.38% | 654 |
543 | 83.33% | 543 | 62.54% | 543 | 45.10% | 543 |
432 | 80.56% | 432 | 58.29% | 432 | 40.47% | 432 |
321 | 77.78% | 321 | 53.51% | 321 | 35.58% | 321 |
665 | 75.69% | 665 | 49.40% | 665 | 30.90% | 665 |
664 | 74.31% | 664 | 47.22% | 664 | 29.12% | 664 |
663 | 72.92% | 663 | 45.66% | 663 | 27.67% | 663 |
662 | 71.53% | 662 | 44.44% | 662 | 26.43% | 662 |
661 | 70.14% | 661 | 42.88% | 661 | 25.01% | 661 |
655 | 68.75% | 655 | 41.38% | 655 | 23.97% | 655 |
653 | 66.67% | 653 | 38.73% | 653 | 21.10% | 653 |
652 | 63.89% | 652 | 35.03% | 652 | 17.68% | 652 |
651 | 61.11% | 651 | 31.75% | 651 | 15.21% | 651 |
644 | 59.03% | 644 | 29.75% | 644 | 14.00% | 644 |
643 | 56.94% | 643 | 28.01% | 643 | 12.74% | 643 |
642 | 54.17% | 642 | 25.04% | 642 | 10.66% | 642 |
641 | 51.39% | 641 | 29.15% | 1 | 8.79% | 641 |
633 | 49.31% | 633 | 21.77% | 6 | 7.91% | 633 |
632 | 47.22% | 632 | 21.77% | 6 | 7.43% | 632 |
631 | 49.81% | 1 | 29.15% | 1 | 6.48% | 631 |
622 | 42.36% | 622 | 21.77% | 6 | 5.85% | 622 |
621 | 51.35% | 21 | 30.33% | 21 | 5.38% | 621 |
554 | 38.80% | 4 | 19.69% | 4 | 4.97% | 554 |
553 | 38.54% | 19.31% | 4.61% | 553 | ||
552 | 38.54% | 19.31% | 4.09% | 552 | ||
551 | 49.81% | 1 | 29.15% | 1 | 3.56% | 551 |
544 | 38.80% | 4 | 19.69% | 4 | 3.33% | 544 |
542 | 41.50% | 42 | 23.82% | 42 | 2.90% | 542 |
541 | 49.81% | 1 | 29.15% | 1 | 1.80% | 541 |
533 | 38.54% | 19.31% | 1.43% | 533 | ||
532 | 38.54% | 19.31% | 1.11% | 532 | ||
531 | 49.81% | 1 | 29.15% | 1 | 0.69% | 531 |
522 | 38.54% | 19.31% | 0.49% | 522 | ||
521 | 51.35% | 21 | 30.33% | 21 | 0.39% | 521 |
443 | 38.80% | 4 | 19.69% | 4 | 0.32% | 443 |
442 | 41.50% | 42 | 23.82% | 42 | 0.25% | 442 |
441 | 49.81% | 1 | 29.15% | 1 | 0.18% | 441 |
433 | 38.80% | 4 | 19.69% | 4 | 0.12% | 433 |
431 | 49.81% | 1 | 29.15% | 1 | 0.06% | 431 |
422 | 41.50% | 42 | 23.82% | 42 | 0.02% | 422 |
332 | 38.54% | 19.31% | 0.02% | 332 | ||
331 | 49.81% | 1 | 29.15% | 1 | 0.01% | 331 |
322 | 38.54% | 19.31% | 0.00% | 322 | ||
221 | 51.35% | 21 | 30.33% | 21 | 0.00% | 221 |