#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: