#Feb. 4, 2013, C4.txt Sprague-Grundy function of non-partizan games Help4:=proc(): print(` mex(s), SG(G,i) , SG2N(i,j) , SG1(i,j)`): print(`NimSum(L) `): end: #mex(S): inputs a set of non-neg. integers and outputs #the minimum of the set {0,1,2,3,...}\S mex:=proc(S) local i: for i from 0 to nops(S) while i in S do od: i: end: #SG(G,i): inputs a digraph (representing a cycle-less #combinatorial game with positions 1, 2, ..., nops(G) #and G[i] is the subset of {1, ..., nops(G)} rechable #in one legal move #outputs the value of the Sprague-Grundy function #at vertex i SG:=proc(G,i) local m: option remember: mex({seq(SG(G,m), m in G[i])}): end: #SG2N(i,j): The S-G function of positon [i,j] in 2-pile Nim SG2N:=proc(i,j) local k: option remember: mex({ seq(SG2N(i-k,j),k=1..i), seq(SG2N(i,j-k),k=1..j)}): end: with(Bits): #NimSum(L): the Nim sum of the list of non-neg. integers #in L NimSum:=proc(L) if L=[] then RETURN(0): elif nops(L)=1 then RETURN(L[1]): else NimSum( [Xor(L[1],L[2]), op(3..nops(L),L)]): fi: end: #NimSumPat(L): the Nim sum of the list of non-neg. integers #in L NimSumPat:=proc(L) if L=[] then RETURN(0): else RETURN(Xor(L[1],NimSumPat([op(2..nops(L),L)]))): fi: end: #SG(2*m,2*n)=2*SG(m,n) #SG(2*m,2*n+1)=2*SG(m,n)+1 #SG(2*m+1,2*n)=2*SG(m,n)+1 #SG(2*m+1,2*n+1)=2*SG(m,n): #a^(2*n)= (a^n)^2 , a^(2*n+1)=(a^n)^2*a #a^i=a^(i-1)*a #SG1(m,n): Like SG2N(m,n), but done using the fast recurrene SG1:=proc(m,n) option remember: if m=0 and n=0 then RETURN(0): elif m mod 2=0 and n mod 2 =0 then RETURN(2*SG1(m/2,n/2)): elif m mod 2=1 and n mod 2 =0 then RETURN(2*SG1((m-1)/2,n/2)+1 ): elif m mod 2=0 and n mod 2 =1 then RETURN(2*SG1(m/2,(n-1)/2)+1 ): else RETURN(2*SG1((m-1)/2,(n-1)/2) ): fi: end: ####Old stuff #C3.txt: Jan. 31, 2013 class continuing no-partizan combinatorial games #and starting partizan games Help3:=proc(): print(` W(G,i), WL(L,R,i), WR(L,R,i) `): print(`Nim1(a), Nim2(Li),Nim3(Li), Nim(Li) `): end: #W(G,i): same as fGi(G,i) from C2.txt #inputs a directed graph representing #a game and a pos. integer i between 1 #and nops(G) (representing a position) #and outputs 0(1) according to whether it #is a losing [P position] (winning [N]) position #due to Matthew Russell (inspired by Pat Devlin #and Tim Naumovitz) W:=proc(G,i) local m: option remember: 1-mul(W(G,m),m in G[i]): end: #WL(L,R,i): inputs Two digraphs L and R #(with nops(L)=nops(R), of course, representing #the positions) representing the legal moves #for player Left and player Right resp. #and a position i #Ourputs 0(1) if Left must lose or may win (with perfect players) WL:=proc(L,R,i) local m: option remember: 1-mul(WR(L,R,m),m in L[i]): end: #WR(L,R,i): inputs Two digraphs L and R #(with nops(L)=nops(R), of course, representing #the positions) representing the legal moves #for player Left and player Right resp. #and a position i #Ourputs 0(1) if Right must lose or may win (with perfect players) WR:=proc(L,R,i) local m: option remember: 1-mul(WL(L,R,m),m in R[i]): end: #Nim1(a): inputs a non-neg. #integers, representing a Nim-1 position with #a counters, outputs whether it #is losing (0) or winning (1) #A legal move consist of #removing any number of pennies (up to the total) #from that pile Nim1:=proc(a) local i: option remember: 1-mul(Nim1(a-i),i=1..a): end: #Nim2(Li): inputs a list of length 2 of non-neg. #integers, representing a Nim-3 position with #Li[1],Li[2] counters, outputs whether it #is losing (0) or winning (1) #A legal move consist of picking ONE of the piles #and removing any number of pennies (up to the total) #from that pile Nim2:=proc(Li) local i: option remember: 1-mul(Nim2([Li[1]-i,Li[2]]),i=1..Li[1])* mul(Nim2([Li[1],Li[2]-i]),i=1..Li[2]): end: #Nim3(Li): inputs a list of length 3 of non-neg. #integers, representing a Nim-3 position with #Li[1],Li[2],Li[3] counters, outputs whether it #is losing (0) or winning (1) #A legal move consist of picking ONE of the piles #and removing any number of pennies (up to the total) #from that pile Nim3:=proc(Li) option remember: 1-mul(Nim3([Li[1]-i,Li[2],Li[3]]),i=1..Li[1])* mul(Nim3([Li[1],Li[2]-i,Li[3]]),i=1..Li[2])* mul(Nim3([Li[1],Li[2],Li[3]-i]),i=1..Li[3]): end: #Nim(Li): L of any length Nim:=proc(Li) local i,j: option remember: 1-mul( mul( Nim([ op(1..j-1, Li), Li[j]-i, op(j+1..nops(Li),Li) ]), i=1..Li[j]), j=1..nops(Li)): end: #####old stuff #Jan. 28, 2013, general non-partisan games Help2:=proc(): print(` fGi(G,i) , AM(G) , IsCyclic(G) `): print(`WList(G), RandGame(n,k) `): end: #Every non-partisan combinatorial game can be described #abstractly as a directed graph. The positions are #the vertices, and there is a DIRECTED edge between #vertex v1 to v2, if it is a legal move #We represent a digraph as a list L #The vertices are called 1,2,.., n:=nops(L) #and for i=1,2, ..., n, L[i] is the set of #vertices for which there is a directed edge from i to #For example G=[{},{1},{1,2}], the edges are #{[2,1],[3,1],[3,2]} #IsCyclic(G): inputs a directed graph (described as #a list of sets, andoutputs true (false) if it has #a cycle IsCyclic:=proc(G) local i,M1,M: option remember: M:=AM(G): M1:=M: #Soon-to-be PhD candidate #Jacob Baron thinks that it safer to do nops(G)+1 for i from 1 to nops(G)+1 do if trace(M1)>0 then RETURN(true): fi: M1:=evalm(M1*M): od: false: end: #fGi(G,i), inputs a directed graph G and #an integer i between 1 and nops(G) and outputs #0(resp. 1) if vertex i is a Losing (Winning) position fGi:=proc(G,i) local M,m: option remember: if not (type(i,integer) and type(G,list) and i>=1 and i<=nops(G)) then print(`bad input`): RETURN(FAIL): fi: #if IsCyclic(G) then #print(`graph has cycles`): # RETURN(FAIL): #fi: if G[i]={} then RETURN(0): fi: M:=G[i]: if {seq(fGi(G,m), m in M)}={1} then RETURN(0): else RETURN(1): fi: end: with(linalg): #AM(G): adjacency matrix of G (written a matrix M) #M[i,j]=1 (0) of j belongs (does not belong) #to G[i] AM:=proc(G) local n,i,j,M: n:=nops(G): M:=matrix(n,n): for i from 1 to n do for j from 1 to n do if j in G[i] then M[i,j]:=1: else M[i,j]:=0: fi: od: od: op(M): end: #WList(G): Winning list #Inputs a directed G (representing a game) #and outputs a list of length nops(G) such that #L[i]=0 or 1 according to whether position (vertex) i #is a losing or winning position WList:=proc(G) local i: [seq(fGi(G,i),i=1..nops(G))]: end: #RandGame(n,k): inputs pos. integers n and k #and outputs a random digraph that has the #property that out of vertex i all the labels #are less i, and there are (usually) k outgoing #edges RandGame:=proc(n,k) local L,i,tomas,j: L:=[{}]: for i from 2 to n do tomas:={seq(rand(1..i-1)(),j=1..k)}: L:=[op(L), tomas]: od: L: end: #end old stuff