#C26.txt: Generalizing the centepede game to general directed graphs
#April 29, 2013
Help:=proc(): print(`ElsterG() `):
print(`P1(G,i), P2(G,i), RandGame(n,k) , RGG(n,k,Si,L) `):
end:
#ElsterG():
ElsterG:=proc()
[{2,6},{3,7},{4,8},{5,9},[3,4],[2,-1],[1,2],[4,1],
[6,3]]:
end:
#P1(G,i): The best move, followed by the pair
#[payOff of I, payoff of II] in a game given
#by the generalized directed graph G where
#the sinks are labeled by payoofs
#If player I is moving
P1:=proc(G,i) local champ, rec, GoHome,S,s, ross,DrZ:
option remember:
if type(G[i],list) then
RETURN(GoHome,G[i]):
fi:
S:=G[i]:
champ:=DrZ:
rec:=[-infinity, -infinity]:
#infinity is OK here, it is a symbol!
#(the "real" infinity is nonsense)
for s in S do
ross:=P2(G,s)[2]:
if ross[1]>rec[1] then
champ:=s:
rec:=ross:
fi:
od:
champ, rec:
end:
#P2(G,i): The best move, followed by the pair
#[payOff of I, payoff of II] in a game given
#by the generalized directed graph G where
#the sinks are labeled by payoofs
#If player II is moving
P2:=proc(G,i) local champ, rec, GoHome,S,s, ross,DrZ:
option remember:
if type(G[i],list) then
RETURN(GoHome,G[i]):
fi:
S:=G[i]:
champ:=DrZ:
rec:=[-infinity, -infinity]:
#infinity is OK here, it is a symbol!
#(the "real" infinity is nonsense)
for s in S do
ross:=P1(G,s)[2]:
if ross[2]>rec[2] then
champ:=s:
rec:=ross:
fi:
od:
champ, rec:
end:
#RandDi(n,k): a random directed graph with n
#vertices and (usually) outdegree k
RandDi:=proc(n,k) local ra,i,j:
ra:=rand(1..n):
[seq({seq(ra(),i=1..k)} minus {j} ,j=1..n)]:
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:
#RGG(n,k,Si,L): a random centepede-style
#game with n vertices, roughly outdegree k
#for non-sinks, and roughly Si sinks
RGG:=proc(n,k,Si,L) local G, ra,i, t,a, b:
ra:=rand(0..L):
G:=RandGame(n,k):
for i from 2 to Si do
t:=rand(2..n)():
a:=ra(): b:=ra():
G:=[op(1..t-1,G) , [a,b], op(t+1..n,G)]:
od:
a:=ra(): b:=ra():
G:=[[a,b],op(2..nops(G),G)]:
end: