#Nathan Fox
#Homework 2
#I give permission for this work to be posted online

#Read C2.txt for necessary procedures
read(`C2.txt`):

#Help procedure
Help:=proc() : print(` AveLosing(n,k,K) , ProbWinStupid(G,i) `): end:

#Finds out the average number of losing positions in
#K randomly chosen games of size n with (approximately)
#k possible moves per position.
AveLosing:=proc(n,k,K)
local i,total:

total:=0:

for i from 1 to K do:
    total:=total + n - convert(WL(RandGame(n, k)), `+`):
od:

convert(total / K, float):
end:

##If K is big, and you run it many times,
##do you get similar answers?
##Can you guess what the answer should be?
#The answers are very similar.  It seems that
#AveLosing(n,1,K) is close to n/2.  Predicting it seems
#more difficult for k>2

#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
#legal available move.
ProbWinStupid:=proc(G,i)
local j:
option remember:

if G[i]={} then
    0:
else
    convert(1/nops(G[i]), float) *
        convert([seq(1 - ProbWinStupid(G,j), j in G[i])], `+`):
fi:

end: