# Jake Baron, 2/3/13 # Homework 2 # I give permission to post. # New programs: AveLosing(n,k,K), ProbWinStupid(G,i), Sinks(G) # AveLosing(n,k,K) finds out the average number of losing positions in K randomly chosen # games on n verts with outdegree (usually) k (using RandGame(n,k) K times). AveLosing:=proc(n,k,K) local totwin,i,j: totwin:=0: for i from 1 to K do totwin:=totwin+add(j,j in WL(RandGame(n,k))): od: (n*K-totwin)/K: end: # ProbWinStupid(G,i) inputs a game given as a directed graph, and a vertex i between 1 # and nops(G) and computes the probability of winning if both players play completely # randomly, by picking (if possible) uniformly at random one of the available legal moves. ProbWinStupid:=proc(G,i) local j: option remember: if G[i]={} then RETURN(0): else RETURN( ( nops(G[i])-add(ProbWinStupid(G,j),j in G[i]) ) / nops(G[i]) ): fi: end: # Given a game G as a digraph, returns the set of indices of the sinks Sinks:=proc(G) local i,sinks: sinks:={}: for i from 1 to nops(G) do if G[i]={} then sinks:=sinks union {i}: fi: od: sinks: end: # ~~~~~~~~~~~~~~~~~~~~~~~~~ C2.txt from Mon 1/28/13 class ~~~~~~~~~~~~~~~~~~~~~~ #Jan. 28, 2013, general non-partisan games Help:=proc(): print(` fGi(G,i) , AM(G) , IsCyclic(G) `): print(`WL(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: #WL(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 WL:=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: