#OKEY.txt: A Maple package for simulating and analyzing the game OKEY #written ny Nuray Kutlu with advice from Doron Zeilberger Help:=proc(): print(`OKEY.txt: a Maple package for simulating and studying and experimenting with generalized Okey`): print(``): if nargs=0 then print(`The main procedures are: `): print(` Deal, Tile, MiddleDeck, FindRuns, FindSets, FindRunsWJ, FindSetsWJ, GenerateRandomGrouping, StartGame, RemoveRandomTile, SimulateGame, SimulateGameT`): print(`GenerateDetGrouping, GenerateStates, WinningStates, ChildrenStates, TransitionMatrix, StateProbabilities, TransitionMul`): #print(`Tools for experimenting: RandomGamesP, RandomGamesN, RandomGamesL, RandomGamesC, SimulateGameT`): (* elif nargs = 1 and args[1]=RandomGamesP then print(`RandomGamesP(L,R,K) that inputs integers L, R, K.`): print(`Keeps r, k , s, l controlled and tests p from L to R, the number of players in a game K times.`): print(`Returns a list of how many games resuluted in a winner for each p.`): elif nargs = 1 and args[1]=RandomGamesC then print(`RandomGamesC(L,R,K) that inputs integers L, R, K.`): print(`Keeps k , p, s, l controlled and tests r from L to R, the number of colors for tiles K times.`): print(`Returns a list of how many games resuluted in a winner for each r.`): elif nargs = 1 and args[1]=RandomGamesN then print(`RandomGamesN(L,R,K) that inputs integers L, R, K.`): print(`Keeps r, p , s, l controlled and tests p from L to R, the number of numbers for tiles K times.`): print(`Returns a list of how many games resuluted in a winner for each k.`): elif nargs = 1 and args[1]=RandomGamesL then print(`RandomGamesL(L,R,K) that inputs integers L, R, K.`): print(`Keeps r, k , p, s controlled and tests l from L to R, the minimum grouping value in a game K times.`): print(`Returns a list of how many games resuluted in a winner for each l.`): *) elif nargs=1 and args[1]=Deal then print(`Deal(r,k,p,s) that inputs integers r,k,p,s and outputs a pair [L,T] where L is a list of lists of length`): print(`p such that L[i] is the "hand" of player i, where L[i] is a random list of length s, and T is the leftover tiles that have not been dealt`): print(`For example for the usual game, try: Deal(4,13,4,14);`): elif nargs=1 and args[1]=Tile then print(`Tile(r,k) that inputs r and k and outputs the initial deck LIST of`): print(`[i,j], 1<=i<=k, 1<=j<=r`): print(`For example try`): print(` Tile(4.13);`): elif nargs=1 and args[1]=MiddleDeck then print(`MiddleDeck(Hands,r,k) that inputs list of lists Hands, and integers r,k and outputs a list`): print(`of tiles un-used in Hands, which consists of the tiles dispersed between the players.`): print(`For example `): print(`H:=Deal(4,13,4,14); MiddleDeck(H,4,13);`): elif nargs=1 and args[1]=FindRuns then print(`FindRuns(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`): print(`the runs of size at least s without jokers found in Hand.`): print(`For example, try:`): print(`H:=Deal(4,13,4,14)[1]; `): print(`FindRuns(H,4,13,3);`): elif nargs=1 and args[1]=FindSets then print(`FindSets(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`): print(`the sets of size at least s without jokers found in Hand.`): print(`H:=Deal(4,13,4,14)[1]; `): print(`FindSets(H,4,13,3);`): elif nargs=1 and args[1]=FindRunsWJ then print(`FindRunsWJ(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`): print(`the sets of size at least s with jokers found in Hand.`): print(`H:=Deal(4,13,4,14)[1]; `): print(`FindRunsWJ(H,4,13,3);`): elif nargs=1 and args[1]=FindSetsWJ then print(`FindSetsWJ(Hand,r,k,s) that inputs a list, Hand, and integers r, k, and s and outputs all`): print(`the sets of size at least s with jokers found in Hand.`): print(`H:=Deal(4,13,4,14)[1]; `): print(`FindSetsWJ(H,4,13,3);`): elif nargs=1 and args[1] = GenerateRandomGrouping then print(`GenerateRandomGrouping(Hand,r,k,s) that inputs a list, Hand, and integers r (number of tile colors), `): print(`k (number of tile colors), and s (minimum length of groupings) and outputs a random grouping and "extra tile" pair`): print(`which are tiles leftover in your hand that are not yet grouped. Returns [Groups, NewHand]`): print(`H:=Deal(4,13,4,14)[1]; `): print(`GenerateRandomGrouping(H,4,13,3);`): elif nargs=1 and args[1] = StartGame then print(`StartGame(r,k,p,s, l) that inputs integers r, k, p, s, l and prints out the`): print(`initial state of a game of Okey with p players each dealt a hand of length s with tiles`): print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`): print(`Try StartGame(4,13,4,14, 3)`): elif nargs=1 and args[1] = SimulateGame then print(`SimulateGame(r,k,p,s, l) that inputs integers r, k, p, s, l and simulated`): print(`a game of Okey with p players each dealt a hand of length s with tiles`): print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`): print(`Try SimulateGame(4,13,4,14, 3)`): elif nargs=1 and args[1] = SimulateGameT then print(`SimulateGameT(r,k,p,s, l) that inputs integers r, k, p, s, l and simulated`): print(`a game of Okey with p players each dealt a hand of length s with tiles`): print(`numbered 1-k numbers and colored 1-r colors, and initial groupings of min length l`): print(`Returns a pair of the number of moves played and the winning player (returns 0 if there is none).`): print(`Try SimulateGameT(4,13,4,14, 3)`): elif nargs=1 and args[1] = RemoveRandomTile then print(`RemoveRandomTile(Tiles) picks a random tile from a list of tiles "Tiles", and returns a pair [tile to remove, list of rest of tiles]`): print(`Try the following: `): print(`H:=Deal(4,13,4,14)[1];`): print(`LeftoverTiles:=GenerateRandomGrouping(H,4,13,3)[2];`): print(`RemoveRandomTile(LeftoverTiles);`): elif nargs=1 and args[1] = ParamModes then print(`ParamModes(lr, rr, lk,rk, lp,rp, ls, rs, ll, rl, k) takes in ranges for`): print(`All 5 parameters in SimulateGameT, runs SimulateGameT K times for each parameter, `): print(`and returns the Mode of the parameters for which a game results in a winning player.`): print(`Try ParamModes(5, 7, 4, 7, 3, 4, 5, 9, 2, 3, 10)`): elif nargs=1 and args[1] = GenerateDetGrouping then print(`GenerateDetGrouping(Hand, r, k, s)`): print(`Deterministic Generate Grouping, input your Hand, and r (colors), k (numbers), s (grouping sizes) values and get [Groupings, Leftover Tiles]`): print(`For example, try GenerateDetGrouping(Deal(2,2,1,4)[1][1], 2, 2, 2)`): elif nargs =1 and args[1] = GenerateStates then print(`GenerateStates(r, k, s)`): print(`Generates states ( every possible hand) for a game with tiles generated with r colors, k numbers, and hand sizes of s, along with a vector of their probabilities.`): print(`For example try GenerateStates(2, 2, 4)`): elif nargs =1 and args[1] = StateProbabilities then print(`StateProbabilities(r, k, s)`): print(`Generates state probabilities (for every possible hand) for a game with tiles generated with r colors, k numbers, and hand sizes of s, along with a vector of their probabilities.`): print(`This can be used as an initial vector V0 in a markov chain.`): print(`For example try StateProbabilities(2, 2, 4)`): elif nargs =1 and args[1] = WinningStates then print(`WinningStates(States, r, k, gs)`): print(`Finds all the states that result in a winning state given a list of states for tiles generated with r colors, k numbers, and gs grouping sizes. `): print(`For example, try WinningStates(GenerateStates(2,2,4), 2, 2, 2)`) elif nargs = 1 and args[1] = ChildrenStates then print(`Takes in a state for a game with r color and k number tiles, along with grouping sizes and generates all probabilities for Children States.`): print(`For example, ChildrenStates(GenerateStates(2, 2, 4)[1], GenerateStates(2, 2, 4), 2, 2, 2)`): elif nargs = 1 and args[1] = TransitionMatrix then print(`|S|x|S| matrix where S is the set of all possible states, such that the S_a_b'th entry is the probability that if the current state is S_a, the player will move to state S_b.`): print(`Gives the probabilty for states with tiles generated by r colors and k numbers, grouping sizes of gs, and hand sizes of s.`): print(`For example, try TransitionMatrix(2, 2, 2, 4) for the small case.`): elif nargs = 1 and args[1] = TransitionMul then print(`TransitionMul(V,M) multiplies a 1 x n vector V with an n x n Matrix M.`): print(`For example, try TransitionMul(StateProbabilities(2,2,4), TransitionMatrix(2,2,2,4))`): #elif nargs = 1 and args[1] = WinningProbability then else print(`There is no Help for`, args[1]): fi: end: # Generalized OKEY r=4 k=13 p players (p>=1) and every player gets s random tiles # 2*r sets of tiles labeled 1,...,k with colors from 1, ..., r, plus 2 jokers #2*r*k+2 tiles #2*4*13+2 = 106 #Tile(r,k) inputs r and k and outputs the LIST of #[i,j], 1<=i<=k, 1<=j<=r and the two jokers (0,0) Tile:=proc(r,k) local i,j,L: L:=[seq(seq([i,j],j=1..r),i=1..k)]: [op(L),op(L),0,0]: end: # Deal(r,k,p,s) inputs integers r,k,p,s (# of colors in tiles, # of numbers in tiles, # of players, # of tiles each player gets) # and outputs a list of lists of length p, L, such that L[i] is the "hand" of player i, where L[i] is a random list of length s # Also outputs the tiles that are not dealt to players. # taken from the set of tiles Deal2:=proc(r,k,p,s) local T, L, i, PD, tile, j: T:= Tile(r,k): if (p*s > nops(T)) then print (`Not enough tiles for all players!`): RETURN(FAIL): fi: L:= []: for i from 1 to p do: PD:=[]: for j from 1 to s do: tile:= rand(1..nops(T))(): PD:= [op(PD), T[tile]]: T:=subsop(tile=NULL, T): od: L:= [op(L), PD]: od: [L,T]: end: #FindRuns(Hand,r,k,s) #with exactly s members #Ignores jokers FindRuns:=proc(Hand, r, k, s) local i, j, left, right, Runs, Run, RunI: if (k < s) then print(`Bad Input! Can't make runs of requested size.`): `quit`(0): fi: Runs:= []: for i from 1 to nops(Hand) do: if(evalb(Hand[i] <> 0) ) then RunI:= [i]: Run:= [Hand[i]]: left:= Hand[i]: right:= Hand[i]: for j from 1 to nops(Hand) do: if(evalb(Hand[j] <> 0)) then if ((Hand[j][1] = (left[1] - 1)) and (Hand[j][2] = left[2])) then RunI:= [op(RunI), j]: Run:= [Hand[j], op(Run)]: left:= Hand[j]: elif ((Hand[j][1] = (right[1] + 1)) and (Hand[j][2] = right[2])) then RunI:= [op(RunI), j]: Run:= [op(Run), Hand[j]]: right:= Hand[j]: fi: fi: od: if (nops(Run) >= s) then if (not member(Run,Runs)) then Runs := [op(Runs), Run]: fi: fi: fi: od: Runs: end: #FindSets(Hand,r,k,s) FindSets:=proc(Hand,r,k,s) local Sets, SetI, i, j, Set, colors, number: if (r < s) then print(`Bad Input! Can't make sets of requested size.`): `quit`(0): fi: Sets:=[]: for i from 1 to nops(Hand) do: if(evalb(Hand[i] <> 0)) then SetI:=[i]: Set:= [Hand[i]]: colors:= [Hand[i][2]]: number:= Hand[i][1]: for j from 1 to nops(Hand) do: if(evalb(Hand[j] <> 0)) then if ((Hand[j][1] = number) and (not (evalb( Hand[j][2] in colors)))) then SetI:= [op(SetI), j]: Set:= [Hand[j], op(Set)]: colors:= [op(colors), Hand[j][2]]: fi: fi: od: if (nops(Set) >= s) then Set := sort(Set): if (not member(Set,Sets)) then Sets:= [op(Sets), Set]: fi: for j from 1 to nops(SetI) do: subsop(SetI[j] = 1, Hand): od: fi: fi: od: Sets: end: # Write FindRunsWJ and FindSetsWJ that finds runs and sets with jokers #FindRunsWJ(Hand,r,k,s) #with exactly s members FindRunsWJ:=proc(Hand, r, k, s) local i, Runs, jokercount: if (k < s) then print(`Bad Input! Can't make runs of requested size!`): `quit`(0): fi: Runs:= []: jokercount:= 0: for i from 1 to nops(Hand) do: if (Hand[i] = 0) then jokercount++: fi: od: if (jokercount = 0) then Runs:= FindRuns(Hand, r, k, s): elif (jokercount = 1) then Runs:= FindRuns(Hand, r, k, s-1): for i from 1 to nops(Runs) do if (nops(Runs[i]) = (s - 1)) then Runs[i] := [op(Runs[i]), 0]: fi: od: else Runs:= FindRuns(Hand, r, k, s-2): for i from 1 to nops(Runs) do if (nops(Runs[i]) = (s - 1)) then Runs[i] := [op(Runs[i]), 0]: elif (nops(Runs[i]) = (s - 2)) then Runs[i] := [op(Runs[i]), 0]: fi: od: fi: Runs: end: FindSetsWJ:=proc(Hand, r, k, s) local i, Sets, jokercount: if (k < s) then print(`Bad Input! Can't make sets of requested size!`): `quit`(0): fi: Sets:= []: jokercount:= 0: for i from 1 to nops(Hand) do: if (Hand[i] = 0) then jokercount++: fi: od: if (jokercount = 0) then Sets:= FindSets(Hand, r, k, s): elif (jokercount = 1) then Sets:= FindSets(Hand, r, k, s-1): for i from 1 to nops(Sets) do if (nops(Sets[i]) = (s - 1)) then Sets[i] := [op(Sets[i]), 0]: fi: od: else Sets:= FindSets(Hand, r, k, s-2): for i from 1 to nops(Sets) do if (nops(Sets[i]) = (s - 1)) then Sets[i] := [op(Sets[i]), 0]: elif (nops(Sets[i]) = (s - 2)) then Sets[i] := [op(Sets[i]), 0]: fi: od: fi: Sets: end: GenerateRandomGrouping:= proc(Hand, r, k, s) local i, flagRS, Groups, Runs, Sets, flagsRS, Set, Run, NewHand: #flagRS will first check if there is more in findrunsWJ or findsetsWJ and prioritize #starting with runs or sets based on that, but if they're equal then it prioritizes randomly Groups:= []: Runs:= FindRunsWJ(Hand, r, k , s): Sets:= FindSetsWJ(Hand, r, k, s): NewHand:= Hand: flagRS := 0: if(nops(Runs) > nops(Sets)) then flagRS := 1: elif(nops(Sets) = nops(Runs)) then flagRS := rand(0..1)(): fi: if(flagRS = 0) then while nops(Sets) <> 0 do: Set:= Sets[1]: Groups:= [op(Groups), Set]: NewHand := UpdateHands(NewHand, Set): Sets := FindSetsWJ(NewHand, r, k, s): od: Runs:= FindRunsWJ(NewHand, r, k, s): while nops(Runs) <> 0 do: Run:= Runs[1]: Groups:= [op(Groups), Run]: NewHand:= UpdateHands(NewHand, Run): Runs:= FindRunsWJ(NewHand, r, k, s): od: else while nops(Runs) <> 0 do: Run:= Runs[1]: Groups:= [op(Groups), Run]: NewHand:= UpdateHands(NewHand, Run): Runs:= FindRunsWJ(NewHand, r, k, s): od: Sets := FindSetsWJ(NewHand, r, k, s): while nops(Sets) <> 0 do: Set:= Sets[1]: Groups:= [op(Groups), Set]: NewHand := UpdateHands(NewHand, Set): Sets := FindSetsWJ(NewHand, r, k, s): od: fi: [Groups, NewHand]: end: #Deterministic Generate Grouping, used in Groupings for markov chain stuff GenerateDetGrouping:= proc(Hand, r, k, s) local i, flagRS, Groups, Runs, Sets, flagsRS, Set, Run, NewHand: #flagRS will first check if there is more in findrunsWJ or findsetsWJ and prioritize #starting with runs or sets based on that, but if they're equal then it prioritizes randomly Groups:= []: Runs:= FindRunsWJ(Hand, r, k , s): Sets:= FindSetsWJ(Hand, r, k, s): NewHand:= Hand: flagRS := 0: while nops(Sets) <> 0 do: Set:= Sets[1]: Groups:= [op(Groups), Set]: NewHand := UpdateHands(NewHand, Set): Sets := FindSetsWJ(NewHand, r, k, s): od: Runs:= FindRunsWJ(NewHand, r, k, s): while nops(Runs) <> 0 do: Run:= Runs[1]: Groups:= [op(Groups), Run]: NewHand:= UpdateHands(NewHand, Run): Runs:= FindRunsWJ(NewHand, r, k, s): od: [Groups, NewHand]: end: # The issue is that for some reason, findSets and findRuns With Joker are finding sets and runs with #Two jokers even if the user only has one UpdateHands:=proc(Hand,Group) local i, j, k1, B, NewHand: NewHand:= Hand: for i from 1 to nops(Group) do: j := 1: B:= 0: if(evalb(Group[i] <> NewHand[j])) then B:=1: fi: while B = 1 do: j++: if(nops(NewHand) >= j) then if(evalb(Group[i] = NewHand[j])) then B:=0: fi: else print(`Something went wrong!`): `quit`(0): fi: od: NewHand:=subsop(j=NULL, NewHand): od: NewHand: end: #StartGame() starts a game of Okey with p players, s tiles per player, # k numbers in the tiles, kr colors in the tiles, and sets of length l. #It prints the starting state of the game. StartGame:=proc(r,k,p,s, l) local PlayerGroups, i,j, Group, GHPair, PlayerTiles, Tiles, statement, RandomDealing, Hands, ExtraTiles: # Deal returns a pair, the list of lists L, which represents the hands of players and the extra tiles left over in the middle. RandomDealing := Deal2(r,k,p,s): Hands := RandomDealing[1]: ExtraTiles := RandomDealing[2]: PlayerGroups := []: PlayerTiles:= []: for i from 1 to nops(Hands) do: GHPair:= GenerateRandomGrouping(Hands[i],r,k,l): Group:= GHPair[1]: Tiles:= GHPair[2]: PlayerGroups:= [op(PlayerGroups), Group]: PlayerTiles:= [op(PlayerTiles), Tiles]: od: statement:= "": for i from 1 to nops(ExtraTiles) do: statement:= cat(op(statement), " ", ExtraTiles[i]): od: for i from 1 to nops(Hands) do: if(nops(PlayerGroups[i]) = 0) then statement:= cat("Player ", i, " has no groupings and the leftover tiles ", op(PlayerTiles[i]), "."): else statement:= cat("Player ", i, " has the groupings ", seq(cat(PlayerGroups[i][j], ", "), j = 1..nops(PlayerGroups[i])), " and the leftover tiles ", op(PlayerTiles[i]), "."): fi: od: [Hands, PlayerGroups, PlayerTiles, ExtraTiles]: end: #RemoveRandomTile(Tiles) picks a random tile from a list of tiles, and returns a pair #[tile to remove, list of rest of tiles] RemoveRandomTile:=proc(Tiles) local i, TilesUpd: if(nops(Tiles) = 0) then print(`Something went wrong, out of tiles!`): `quit`(0): fi: i:= rand(1..nops(Tiles))(): TilesUpd:= UpdateHands(Tiles, [Tiles[i]]): [Tiles[i], TilesUpd]: end: SimulateGame:=proc(r,k,p,s, l) local GameStatus, Hands, PlayerGroups, PlayerTiles, ExtraTiles, TrashTiles, HandPart, prevTile, RandomGrouping, i, PotentialHand, statement: GameStatus:= StartGame(r,k,p,s, l): Hands:= GameStatus[1]: PlayerGroups:= GameStatus[2]: PlayerTiles:= GameStatus[3]: ExtraTiles:= GameStatus[4]: TrashTiles := []: #The first player gets handled seperately, as it only has one choice of tile. HandPart := RemoveRandomTile(ExtraTiles): prevTile := HandPart[1]: ExtraTiles := HandPart[2]: Hands[1] := [op(Hands[1]), prevTile]: RandomGrouping := GenerateRandomGrouping(Hands[1], r, k, l): PlayerGroups[1] := RandomGrouping[1]: PlayerTiles[1] := RandomGrouping[2]: HandPart := RemoveRandomTile(PlayerTiles[1]): prevTile:= HandPart[1]: PlayerTiles[1] := HandPart[2]: i := 2: while (nops(ExtraTiles) <> 0) do: # First try regrouping and checking extra tile count. # if it's not the same or less extra tiles, then pick something at random PotentialHand := [op(Hands[i]), prevTile]: RandomGrouping := GenerateRandomGrouping(PotentialHand, r, k, l): if (nops(PlayerTiles[i]) >= nops(RandomGrouping[2])) then Hands[i] := PotentialHand: PlayerGroups[i] := RandomGrouping[1]: PlayerTiles[i] := RandomGrouping[2]: else TrashTiles:= [op[TrashTiles], prevTile]: HandPart:= RemoveRandomTile(ExtraTiles): prevTile:= HandPart[1]: ExtraTiles := HandPart[2]: Hands[i] := [op(Hands[i]), prevTile]: RandomGrouping := GenerateRandomGrouping(Hands[i], r, k, l): PlayerGroups[i] := RandomGrouping[1]: PlayerTiles[i] := RandomGrouping[2]: fi: print(`i am player`): print(i): print(`my groupings are:`): print(PlayerGroups[i]): if(nops(PlayerTiles[i]) = 1) then statement := cat("Player ", i, " wins! Here are their groups: ", PlayerGroups[i]): print(statement): return: fi: HandPart := RemoveRandomTile(PlayerTiles[i]): prevTile := HandPart[1]: print (` I removed `): print(prevTile): PlayerTiles[i] := HandPart[2]: print(`my leftover tiles are:`): print(PlayerTiles[i]): i := i+ 1: if (i = p+1) then i := 1: fi: od: print(`This game terminated since there are no middle tiles left.`) end: SimulateGameT := proc(r,k,p,s, l) local GameStatus, moves, Hands, PlayerGroups, PlayerTiles, ExtraTiles, TrashTiles, HandPart, prevTile, RandomGrouping, i, PotentialHand, statement: GameStatus:= StartGame(r,k,p,s, l): #[Hands, PlayerGroups, PlayerTiles, ExtraTiles] returns from start game Hands:= GameStatus[1]: PlayerGroups:= GameStatus[2]: PlayerTiles:= GameStatus[3]: ExtraTiles:= GameStatus[4]: TrashTiles := []: if(nops(ExtraTiles) = 0) then print(`No middle tiles available to play the game! Please increase your r, k parameters!`): return [0,0]: fi: i := 1: moves := 1: #The first player gets handled seperately, as it only has one choice of tile. HandPart := RemoveRandomTile(ExtraTiles): # Returns [Tile to remove, the rest of the tiles] prevTile := HandPart[1]: ExtraTiles := HandPart[2]: Hands[1] := [op(Hands[1]), prevTile]: # Hand of player 1 RandomGrouping := GenerateRandomGrouping(Hands[1], r, k, l): PlayerGroups[1] := RandomGrouping[1]: PlayerTiles[1] := RandomGrouping[2]: if(nops(PlayerTiles[i]) <= 1) then return [1,1]: fi: HandPart := RemoveRandomTile(PlayerTiles[1]): prevTile:= HandPart[1]: PlayerTiles[1] := HandPart[2]: i := i + 1: # The first players turn is now over, it's player 2's turn. 1 move has been made. while (nops(ExtraTiles) <> 0) do: moves := moves +1: # First try regrouping and checking extra tile count. # if picking the given tile results in <= extra tiles (ungrouped), then pick something at random from the middle. PotentialHand := [op(Hands[i]), prevTile]: RandomGrouping := GenerateRandomGrouping(PotentialHand, r, k, l): if (nops(PlayerTiles[i]) >= nops(RandomGrouping[2])) then Hands[i] := PotentialHand: PlayerGroups[i] := RandomGrouping[1]: PlayerTiles[i] := RandomGrouping[2]: else TrashTiles:= [op[TrashTiles], prevTile]: HandPart:= RemoveRandomTile(ExtraTiles): prevTile:= HandPart[1]: ExtraTiles := HandPart[2]: Hands[i] := [op(Hands[i]), prevTile]: RandomGrouping := GenerateRandomGrouping(Hands[i], r, k, l): PlayerGroups[i] := RandomGrouping[1]: PlayerTiles[i] := RandomGrouping[2]: fi: if(nops(PlayerTiles[i]) <= 1) then return [moves,i]: fi: HandPart := RemoveRandomTile(PlayerTiles[i]): prevTile := HandPart[1]: PlayerTiles[i] := HandPart[2]: i := i+ 1: if (i = p+1) then i := 1: fi: od: return [moves, 0]: end: with(Statistics): #ParamModes takes in ranges of parameters to try for each call to SimulateGameT #Returns a list of the modes for each range, out of all numbers that work. ParamModes := proc(lr, rr, lk,rk, lp,rp, ls, rs, ll, rl, k) local RList, LList, KList, PList, SList, ri,ki,pi,li,si,i,output: RList:= []: KList:= []: PList:= []: SList:= []: LList:= []: for ri from lr to rr do: for ki from lk to rk do: for pi from lp to rp do: for si from ls to rs do: for li from ll to rl do: for i from 1 to k do: output:= SimulateGameT(ri,ki,pi,si,li): if(output <> 0) then if(output[2] <> 0) then RList := [op(RList), ri]: KList := [op(KList), ki]: PList := [op(PList), pi]: SList := [op(SList), si]: LList := [op(LList), li]: fi: fi: od: od: od: od: od: od: [Mode(RList), Mode(KList),Mode(PList),Mode(SList),Mode(LList)]: end: #Deterministic Generate Grouping, used in Groupings for markov chain stuff GenerateDetGrouping:= proc(Hand, r, k, s) local i, flagRS, Groups, Runs, Sets, flagsRS, Set, Run, NewHand: Groups:= []: Runs:= FindRunsWJ(Hand, r, k , s): Sets:= FindSetsWJ(Hand, r, k, s): NewHand:= Hand: flagRS := 0: while nops(Sets) <> 0 do: Set:= Sets[1]: Groups:= [op(Groups), Set]: NewHand := UpdateHands(NewHand, Set): Sets := FindSetsWJ(NewHand, r, k, s): od: Runs:= FindRunsWJ(NewHand, r, k, s): while nops(Runs) <> 0 do: Run:= Runs[1]: Groups:= [op(Groups), Run]: NewHand:= UpdateHands(NewHand, Run): Runs:= FindRunsWJ(NewHand, r, k, s): od: [Groups, NewHand]: end: GenerateStates := proc(r, k, s) local S, Tiles, St, i , j, C: with(combinat): # r colors k numbers s tiles per player # tiles are in k, r format (i should change the order ooops) S:= {}: Tiles := Tile(r,k): C := choose({seq(i,i=1..nops(Tiles))},s): for i in C do St:= []: for j in i do St:= [op(St), Tiles[j]]: od: St:= sort(St): S:= S union {St}: od: S: end: #Initial vector StateProbabilities := proc(r, k, s) local S, Tiles, St, i , j, C, ProbT, tot, sz: with(combinat): # r colors k numbers s tiles per player S:= {}: Tiles := Tile(r,k): tot := numbcomb({seq(i,i=1..nops(Tiles))},s): C := choose({seq(i,i=1..nops(Tiles))},s): for i in C do St:= []: for j in i do St:= [op(St), Tiles[j]]: od: St:= sort(St): sz := nops(S): S:= S union {St}: if sz <> nops(S) then ProbT[St] := 0: fi: ProbT[St] := evalf(ProbT[St] + evalf(1/tot)): od: [seq(ProbT[i], i in S)]: end: #Finds all the states that result in a winning state given a list of states. #r, k are colors, numbers and gs is group sizes WinningStates := proc(S, r, k, gs) local W, i: W:=[]: for i from 1 to nops(S) do if(nops(GenerateDetGrouping(S[i],r,k,gs)[2]) = 0) then W:= [op(W), 1]: else W:= [op(W), 0]: fi: od: W: end: # Takes in a state for a 10 Tile game and generates all possible children states with their probabilities. #Current State, All States, #colors, #numbers, group sizes ChildrenStates := proc(S, States, r, k, gs) local W, Tiles, i, j, CS, C_i, TS, SG, TC, C_r, Prob_r, t,l, Prob_i: #initially set every probability to zero for i from 1 to nops(States) do CS[States[i]] := 0: od: #you only pick from UNGROUPED tiles to give away tiles. If there are none then that state is already a game over state. Tiles := Tile(r,k): TS:= S: SG:= GenerateDetGrouping(S,r,k,gs): #This happens when there are no ungrouped tiles left to give away, this state is a game over state with no children if(nops(SG[2]) = 0) then return [seq(CS[i], i in States)]: else #probability that you give a tile away * probability that you pick a tile # First remove the tiles in your state from the extra tiles: while nops(TS)>0 do: j:= 1: while Tiles[j] <> TS[1] do j:= j+1: od: TS:=subsop(1=NULL, TS): Tiles := subsop(j = NULL, Tiles): od: # For every tile you can remove, calculate how many of that tile there is. that's the probaability of removing that tile # For every tile you want to add, calculate how many of that tile there is in the possible tiles you can pull. that's the probability of pulling that tile. # Add that [child state, probability] to CS. for i from 1 to nops(SG[2]) do #count how many of that tile is in the tiles you are willing to give away TC:= 0: for j from 1 to nops(SG[2]) do if(SG[2][j] = SG[2][i]) then TC:=TC+1: fi: od: #Build the transition state so you can set its probability later C_r:= S: C_r := subsop(i= NULL, S): Prob_r := (TC/nops(SG[2])): #now multiply with the probability that you pick the next tile for t from 1 to nops(Tiles) do C_i := C_r: TC:= 0: for l from 1 to nops(Tiles) do if(Tiles[t] = Tiles[l]) then TC:= TC+1: fi: od: #sort them so that multiple states that are the same dont get counted too many times C_i := sort([op(C_r), Tiles[t]]): Prob_i := evalf(Prob_r * (TC/nops(Tiles))): CS[C_i] := Prob_i: od: od: fi: #make the table into a list of lists [seq(CS[i], i in States)]: end: # # colors, # numbers, group sizes, size of hand TransitionMatrix := proc(r, k , gs, s) local A, States, i, Children, TS, j: A:= []: States:= GenerateStates(r, k, s): for i from 1 to nops(States) do Children := ChildrenStates(States[i], States, r, k, gs): A:= [op(A), Children]: od: A: end: # Computes the probability of ending up with each state as the board you receive when the game starts (Returns initial vector V0) # # colors, # numbers, size of hand TransitionMul:= proc(V, M) local i,j: #[1,1,1,1,1] [[1,1,1,1,1],[1,1,1,1,1]] [seq(add(V[j] * M[i][j], j = 1..nops(V)), i = 1..nops(M))]: end: