Comparison of strategies for playing the Taxman game

This page compares the results obtained using various strategies for playing Taxman. Included here are:

Upper Bound

The upper bound on the score given by the weight of the maximum-weight matching (independent edge set), as described in Franklín, A. F. and Moniot R. K., The difficulty of beating the Taxman. Discrete Applied Mathematics, 339, 166-171 (2023). This score is not achievable by playing, except for those few cases in which the Taxman graph has no flat alternating cycles.

Optimal

The maximum achievable score, found by Brian Chess and posted on GitHub.

Cycle Breaking

Score achieved by removing edges from the maximum matching to eliminate flat alternating cycles, resulting in a playable set, as described in Franklín and Moniot, op. cit..

MaxTurn

A greedy strategy first published by Carmony and Holliday, “An Example from Artificial Intelligence for CS1,” SIGCSE Bulletin vol. 25 iss. 1 (1993). On each turn, it picks the number that maximizes the difference between the player's take and the Taxman's take.

MaxTurn+

An improvement on MaxTurn published by Moniot, “The Taxman Game,” Math Horizons 14, Feb. (2007). It looks for “freebies,” which are numbers that can be inserted into the move sequence without preventing future picks chosen by MaxTurn.

OneTax

Strategy #3 in Trono, “Taxman Revisited,” SIGSCE Bulletin, vol. 26, no. 4 (Dec. 1994), with one key modification. I call it OneTax since the basic strategy is to pick the largest number that has only one divisor remaining in play, so the Taxman gets only one number as tax on each turn. Trono noted that sometimes near the end of the game, there would be three remaining integers forming a series of successive multiples of the first. For instance, for N=64, the numbers 16, 32, and 64 are left. The one-divisor rule would say to take 32, but clearly 64 is the better pick. Trono's suggestion was that if 5 or fewer numbers remain available to play, use MaxTurn instead. A better solution is to keep checking for situations where picking a number would render a multiple of it unpickable by taking its last divisors, while that multiple itself is not a divisor of any remaining number. Taking that multiple instead gives a better score and does not invalidate any future picks in the sequence.

The chart below shows the fraction of the pot won by the player for each of the various strategies, for N=1 to 1000. They are identified by the following abbreviations: UB = upper bound; Opt = optimal; 1T = OneTax; CB = cycle breaking; MT+ = MaxTurn+; MT = MaxTurn.

For a very simple heuristic, OneTax does very well, besting our cycle-breaking method for large N. The chart also shows that the optimal score is quite close to the upper bound.

Here is a closer look at the performance of the strategies for N=1 to 128.

Here is a table comparing the scores for the five strategies for playing the Taxman game, for game sizes N=1 to 128. Both cycle-breaking and OneTax achieve the optimal score for numerous values of N up to 90 and 79 respectively.