Comparison of strategies for playing the Taxman game

This table compares scores for five strategies for playing the Taxman game, for game sizes N=1 to 128. One is the optimal strategy, and the others are heuristics that are observed to perform well. The upper bound given by the maximum-weight matching on the Taxman graph is also included for comparison. See the “Taxman Conquered” page for descriptions of these strategies.

N Upper
Bound		 Optimal Cycle
Break		 One
Tax		 Max
Turn+		 Max
Turn
1 0 0 0 0 0 0
2 2 2 2 2 2 2
3 3 3 3 3 3 3
4 7 7 7 7 7 7
5 9 9 9 9 9 9
6 15 15 15 15 15 15
7 17 17 17 17 17 17
8 21 21 21 21 21 21
9 30 30 30 30 30 30
10 40 40 40 40 40 40
11 44 44 44 44 44 44
12 50 50 50 48 48 48
13 52 52 52 50 50 50
14 66 66 66 64 66 66
15 81 81 81 81 81 72
16 89 89 89 89 89 80
17 93 93 93 93 93 84
18 111 111 111 111 102 102
19 113 113 113 113 104 104
20 124 124 124 121 124 124
21 145 144 135 144 135 135
22 167 166 157 166 157 157
23 171 170 161 170 161 161
24 183 182 173 178 173 173
25 198 198 198 190 198 198
26 224 224 224 216 224 224
27 251 251 251 247 247 232
28 279 279 279 279 279 264
29 285 285 285 285 285 270
30 301 301 301 297 300 300
31 303 303 303 299 302 302
32 319 319 319 315 318 318
33 352 352 352 352 337 337
34 386 386 386 386 371 371
35 418 418 418 418 406 360
36 442 442 442 418 442 396
37 448 448 448 424 448 402
38 486 486 486 462 486 440
39 504 503 482 479 482 457
40 526 525 504 499 502 477
41 530 529 508 503 506 481
42 572 571 550 569 548 523
43 574 573 552 571 550 525
44 618 617 596 615 596 571
45 663 660 641 660 621 569
46 709 706 687 706 667 615
47 713 710 691 710 671 619
48 737 734 715 726 695 643
49 761 758 739 750 719 692
50 811 808 789 800 769 742
51 858 833 832 825 794 767
52 892 885 866 877 846 819
53 898 891 872 883 852 825
54 952 940 926 883 879 879
55 981 981 981 945 934 866
56 1017 1017 1017 973 990 922
57 1041 1040 1007 996 1013 945
58 1099 1098 1065 1054 1071 1003
59 1105 1104 1071 1060 1077 1009
60 1138 1137 1104 1084 1109 1041
61 1140 1139 1106 1086 1111 1043
62 1202 1201 1168 1148 1173 1105
63 1265 1264 1231 1219 1236 1128
64 1297 1296 1263 1251 1268 1160
65 1328 1328 1328 1283 1265 1225
66 1394 1394 1366 1349 1331 1291
67 1400 1400 1370 1355 1337 1297
68 1468 1468 1468 1423 1405 1365
69 1502 1499 1464 1454 1436 1357
70 1572 1566 1534 1530 1476 1437
71 1576 1570 1538 1534 1480 1441
72 1648 1642 1610 1606 1552 1513
73 1650 1644 1612 1608 1554 1515
74 1724 1718 1686 1682 1628 1589
75 1799 1793 1761 1793 1733 1694
76 1875 1869 1807 1869 1809 1770
77 1914 1914 1884 1905 1886 1798
78 1992 1991 1934 1991 1895 1846
79 1998 1997 1940 1997 1901 1852
80 2042 2041 2012 2029 1945 1896
81 2123 2105 2065 2029 2022 1928
82 2205 2187 2133 2111 2104 2010
83 2209 2191 2137 2115 2108 2014
84 2265 2263 2195 2207 2196 2102
85 2311 2309 2241 2245 2232 2132
86 2397 2395 2357 2331 2318 2218
87 2438 2436 2398 2372 2359 2208
88 2496 2496 2496 2372 2403 2252
89 2502 2502 2502 2378 2409 2258
90 2552 2552 2552 2414 2454 2348
91 2594 2588 2539 2450 2539 2374
92 2686 2680 2631 2542 2631 2466
93 2728 2715 2615 2577 2666 2501
94 2822 2809 2709 2671 2760 2595
95 2862 2853 2804 2715 2755 2633
96 2910 2901 2852 2731 2803 2681
97 2918 2909 2860 2739 2811 2689
98 3016 3007 2958 2861 2909 2787
99 3115 3106 3057 2878 2966 2844
100 3173 3164 3115 3018 3026 2904
101 3177 3168 3119 3022 3030 2908
102 3279 3270 3221 3124 3132 3010
103 3281 3272 3179 3126 3134 3012
104 3341 3332 3283 3126 3186 3064
105 3446 3434 3388 3141 3241 3119
106 3552 3540 3449 3247 3347 3225
107 3556 3544 3453 3251 3351 3229
108 3664 3652 3606 3359 3443 3321
109 3666 3654 3608 3361 3445 3323
110 3776 3764 3718 3471 3555 3433
111 3829 3813 3717 3520 3604 3482
112 3941 3925 3829 3664 3660 3538
113 3945 3929 3833 3668 3664 3542
114 4059 4043 3895 3836 3721 3656
115 4117 4101 4005 3840 3836 3702
116 4233 4217 4121 3956 3952 3818
117 4350 4334 4243 4007 4069 3935
118 4468 4452 4406 4125 4187 4053
119 4525 4506 4460 4179 4241 4087
120 4633 4593 4568 4227 4301 4147
121 4689 4689 4595 4633 4422 4191
122 4811 4811 4769 4755 4544 4313
123 4865 4860 4697 4804 4593 4362
124 4989 4984 4873 4928 4717 4486
125 5114 5109 5040 5107 4765 4548
126 5198 5191 5064 5147 4828 4674
127 5212 5205 5078 5161 4842 4688
128 5310 5301 5188 5289 4970 4816