import java.util.Vector; import java.util.HashMap; import java.math.BigInteger; /** A class which computs the winning-losing positions of Norton's Tribulation game * @author R. J. Mathar * @since 2016-05-05 */ public class A006019 { /** The parity of the position with n beans. Three-valued, * so 1 represents an even of the remoteness, and the next move * is known to lose (assuming optimum strategies of both playes). * 0 represents an odd value of the remoteness, and the next move * is known to win (assuming optimum strategies). -1 is the tristate * where the check on whether this is a win or lose state is not known. */ byte even ; /** P-Positions: previous player wins. * Positions with even-valued remoteness. */ static byte PPOS = 1 ; /** N-Positions: next player wins. * Positions with odd-valued remoteness. */ static byte NPOS = 0; /** U-Positions: unknown whether the number of beans is a * winning or losing case. */ static byte UPOS = -1 ; /** remoteness : number of moves until the game is finished */ int remness ; static HashMap knownRems = new HashMap() ; /** the non-negative index. * Number of chips currently on the heap. */ BigInteger n ; /** The n-th Triangular Number. * @param n The non-negative index. * @return n*(n+1)/2 . */ static BigInteger A000217(BigInteger n) { return n.multiply(n.add(BigInteger.ONE)).shiftRight(1) ; } /** largest triangular number not greater than n * @param n The upper limit on the resulting triangular number. */ static BigInteger A057944(BigInteger n) { /* search all k>=0 and compute k(k+1)/2. As soon as * this value exceeds n, return the triangular number for the * k-value just before */ for(BigInteger k= BigInteger.ONE ; ; k = k.add(BigInteger.ONE) ) { if ( A000217(k).compareTo(n) > 0 ) return A000217( k.subtract(BigInteger.ONE) ) ; } } /* A057944 */ /** Parity of the remoteness of n * @param depth The depth of searching the binary tree of the moves. * The larger this parameter, the more likely one of theleaves * of the search tree will be able to figure out whether the * n is associated with a winning N-state or a losing P-state. * @return The parity if a search down the moves-tree to depth yields a result * Returns UPOS if undecided up to that search depth. */ static byte parity(final BigInteger n, final int depth) { if ( n.compareTo(BigInteger.ZERO) == 0 ) /* even parity */ return PPOS ; else { /* try to look up the result in the history of * older computations to minimize the effort of * the recursive calculations. */ int r = searchStack(n) ; if ( r >= 0 ) { /* if this parity is even, a P-position (losing), * if it is odd, a N-position (winning). */ return ( r %2 == 0 ) ? PPOS : NPOS ; } /* the remoteness if n is a triangular value is +1 */ for(BigInteger k=BigInteger.ZERO ; ; k = k.add(BigInteger.ONE) ) { final BigInteger t = A000217(k) ; if ( t.compareTo(n) == 0) { /* odd parity */ return NPOS ; } else if ( t.compareTo(n) > 0) break ; } /* exhausted the depth-search through the binary * tree of moves: return that the value is unknown */ if ( depth < 1 ) return UPOS ; /* construct the stack sizes for both possible * moves (tak and put) and call recursively for * their associated parities */ BigInteger tak = n.subtract(A057944(n)) ; byte partak = parity(tak,depth-1) ; BigInteger put = n.add(A057944(n)) ; byte parput = parity(put,depth-1) ; if ( parput != UPOS && partak != UPOS ) { /* this case that both choices have a known * parity value... */ if ( parput == partak) /* if both parities after the two moves * are the same, this parity here is * the opposite of each. */ return (parput == NPOS) ? PPOS : NPOS ; else /* the two parities are different and known: * the player has a choice and selects the NPOS * to win. */ return NPOS ; } else if ( parput == PPOS || partak == PPOS) /* One of the parities after the moves * is not known; we have only partial parity information, * but one of is known to put the next player in a P-position. * So from the view of this player this is the winning strategy. * Also not evaluating the unknown parity further is equivalent * to take a winning strategy with a minimum number of moves. */ return NPOS ; else /* this here means either at least one of the moves leads * to an undecided position and the other (if known) leads * to a winning position of the next player. Because the * strategy is to choose the longer game if we are to lose, * we delay the decision (by saying there is none) assuming that * taking the (yet unknown) branch may be a better choice. */ return UPOS ; } } /* parity */ /** Search the history of all the evaluation for a known remoteness. * @param n The number of beans * @return The remoteness (if previously stored into the map) * or -1 if the value of n is (yet) unknown. */ static int searchStack(BigInteger n) { final Integer r = knownRems.get(n) ; if ( r== null) return -1; else return r.intValue() ; } /** Initialize and compute the remoteness of a heap with n beanse. * @param n The number of beans before the next move. */ A006019(final int nbeans) { this(BigInteger.valueOf((long)nbeans)) ; } /** Initialize and compute the remoteness of a heap with n beanse. * @param n The number of beans before the next move. */ A006019(final BigInteger nbeans) { n = nbeans ; /* unknown even-odd value of the remoteness. */ even = UPOS ; /* unknown value of the remoteness. */ remness =-1 ; if ( n.compareTo(BigInteger.ZERO) == 0 ) { /* no beans means the previous player has won. */ even = PPOS; remness =0 ; knownRems.putIfAbsent(n,new Integer(remness) ) ; } else { /* the remness at triangular numbers are +1 */ for(BigInteger k=BigInteger.ZERO ; ; k = k.add(BigInteger.ONE) ) { final BigInteger t = A000217(k) ; if ( t.compareTo(n) == 0) { remness =1 ; knownRems.putIfAbsent(n,new Integer(remness) ) ; even = NPOS ; } else if ( t.compareTo(n) > 0) break ; } /* try to look up the result in the history of earlier computations */ remness = searchStack(n) ; if (remness < 0) { /* construct the number of beans in the two possible next moves */ BigInteger tak = n.subtract(A057944(n)) ; BigInteger put = n.add(A057944(n)) ; /* recursive searc up to some depth (increasing) for a move * that makes n a N-position. */ for(int depth = 1; ; depth++) { /* the two parities of the two possible moves. One or both * may be undecided if the depth is not deep enough. */ byte partak = parity(tak,depth) ; byte parput = parity(put,depth) ; /* we have 9 possible pairs of (partak,parput), one or both * being PPOS, NPOS or UPOS. This scenario is eavaluated with the * strategy to grab a winning move as soon as possible and to delay a * losing move as long as possible. */ if (partak == PPOS ) { final A006019 atak = new A006019(tak) ; if ( parput != PPOS) { /* taking would lead to a P-position of the opponent, putting not or unknown * Game strategy is to take the shortest path towards winning */ remness = 1+atak.remness ; } else { /* taking and putting give both P-position of the opponent. * Strategie is to select fastest game (game with smallest number of moves) */ final A006019 aput = new A006019(put) ; remness = 1+Math.min(aput.remness, atak.remness) ; } } else if (parput == PPOS) { /* putting gives a P-position of the opponent, and * taking gives an N-position or undecided. Stategy is to * leave a P-position to the opponent. */ final A006019 aput = new A006019(put) ; remness = 1+aput.remness ; } else if ( parput ==NPOS) { final A006019 atak = new A006019(tak) ; if ( partak == NPOS) { /* taking or putting both give N-position. * select slowest game, because we're losing. */ final A006019 aput = new A006019(put) ; remness = 1+Math.max(aput.remness, atak.remness) ; } else { /* putting gives N-position and taking is unknown: * select slowest game, which is the unknown branch * because we are increasing the search depth in the outer loop */ remness = 1+atak.remness ; } } /* note there is no else-branch here that deals with the effect * of having two UPOS-values in partak and parput. This is left over * to the next loop with deeper search. */ if (remness >= 0 ) { /* if one of the branches above could decide on the * best next move: put the result into the history to speed * up the further decisions. */ knownRems.putIfAbsent(n,new Integer(remness) ) ; break; } } } } } /* A006019 ctor */ /** Main program. * It is compiled with * javac -cp . A006019.java * and then called with * java -cp . A006019 [nlimit] * where nlimit is an optional upper search limit for the number of beans. * @author R. J. Mathar * @since 2016-05-07 */ public static void main(String [] args) { /* default upper search limit is so large that it * cannot be reached.... */ int nlimit = 1000000 ; if ( args.length > 0 ) /* if there is a command line argument: take it as the limit */ nlimit = (new Integer(args[0])).intValue() ; for(int n=0 ; n < nlimit ; n++) { //System.out.print(n+ " " + A006019.parity(n,16) ) ; A006019 a = new A006019(n) ; System.out.println(n + " " + a.remness) ; } } /* main */ } /* A006019 */