#C3.txt: Jan. 31, 2013 class continuing no-partizan combinatorial games
#and starting partizan games
Help:=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