Program StandardMoves; {This program builds state vectors to evaluate a game of moves from all possible initial states. We assume a termination rule where there can be at most maxmoves moves. Two successive passes end a game. We assume that all payoffs are nonnegative. Switches to compute maxima are generous: Row looks first to maximize his own payoff; but in case of ties in his own payoff, he looks to maximize Column's payoff. We do not build a tree explicitly, but use instead the recursive formulas. The game is standard in that one can NOT "move" to the same position as well as "pass" from that position. Information is also presented so as to identify the correct move to make from each position. Only two players are allowed.} USES Fonts, Windows, Menus, SegLoad, OSUtils, QuickDraw, TextEdit, Dialogs; const maxrownumber = 10; {maximum number of rows} maxcolumnnumber = 10; {maximum number of columns} maxiterations = 25; {maximum number possible for number of moves in the game} type { range = 0..vertexnumber; vertexlist = record row: 0..maxrownumber; col: 0..maxcolumnnumber; nexttoplay: 1..2; end;} states = record row: 0..maxrownumber; col: 0..maxcolumnnumber; end; var outfile: text; {the output file} outcometype: array[0..maxiterations,0..maxrownumber,0..maxcolumnnumber,1..2] of states; {outcometype[n,i,j,player] tells the game theoretic outcome if we play a game with at most n moves to play, starting at the entry row i and column j, with player to play initially and required to do so.} game: array[0..maxiterations,0..maxrownumber,0..maxcolumnnumber,1..2] of states; {game[n,i,j,player] tells the game theoretic outcome if we play a game with at most n moves to play, starting at the entry row i and column j, with player to play initially and able to either pass or move initially. We assume that the previous player did not pass, so a pass would not end the game.} movereq: array[0..maxiterations,0..maxrownumber,0..maxcolumnnumber,1..2] of states; {movereq[n,i,j,player] tells the optimal move if we play a game with at most n moves to play, starting at the entry row i and column j, with player to play initially and required to move initially.} movepass: array[0..maxiterations,0..maxrownumber,0..maxcolumnnumber,1..2] of states; { movepass[n,i,j,player] tells the optimal move if we play a game with at most n moves to play, starting at the entry row i and column j, with player to play initially and able to either pass or move initially. If move = 0,0 then the player should pass; otherwise it tells the row and column to which the player should move. This assumes that the previous player did not pass, so passing does not end the game.} moveprevpass: array[0..maxiterations,0..maxrownumber,0..maxcolumnnumber,1..2] of states; { moveprevpass[n,i,j,player] tells the optimal move if we play a game with at most n moves to play, starting at the entry row i and column j, with player to play initially and able to either pass or move initially. If move = 0,0 then the player should pass; otherwise it tells the row and column to which the player should move. This assumes that the previous player did pass, so passing will end the game.} rowpayoff: array[0..maxrownumber,0..maxcolumnnumber] of integer; {payoff to row} colpayoff: array[0..maxrownumber, 0..maxcolumnnumber] of integer; {payoff to column} numberrows: integer; {actual number of rows in payoff matrix} numbercolumns: integer; {actual number of columns in payoff matrix} numberits: integer; {the number of iterations to be done} tied: boolean; {tell whether the maximum is a tie} betterstate: states; betterindex: integer; i,j,k,l, player, n: integer; xx: char; label 10, 20, 30; function otherplayer(player:integer): integer; begin if player = 1 then otherplayer := 2 else otherplayer := 1; end; {otherplayer} procedure maximizerow(x,y:states); {this procedure places the maximum from Row's point of view of the two states x and y into the register betterstate. It also sets betterindex = 1 if x is better and 2 if y is better. It sets tied = true if there is a tie in terms of payoff to Row. It is generous, in that if row is indifferent between two states, it selects the state whose payoff is better for column.} begin if rowpayoff[x.row,x.col] > rowpayoff[y.row,y.col] then begin betterstate.row := x.row; betterstate.col := x.col; betterindex := 1; tied := false; end {if} else if rowpayoff[x.row,x.col] = rowpayoff[y.row,y.col] then begin tied := true; if colpayoff[x.row,x.col] > colpayoff[y.row,y.col] then begin betterstate.row := x.row; betterstate.col := x.col; betterindex := 1; end else begin betterstate.row := y.row; betterstate.col := y.col; betterindex := 2; end; end else begin betterstate.row := y.row; betterstate.col := y.col; betterindex := 2; tied := false; end; {writeln('Compare ', rowpayoff[x.row,x.col]:2, ', ', colpayoff[x.row, x.col]:2, ' with ', rowpayoff[y.row, y.col]:2, ',', colpayoff[y.row,y.col]:2); writeln('by Row to give ', rowpayoff[betterstate.row,betterstate.col]:2, ',', colpayoff[betterstate.row,betterstate.col]:2);} end; {maximizerow} procedure maximizecol(x,y:states); {this procedure places the maximum from Column's point of view of the two states x and y into the register betterstate. It also sets betterindex = 1 if x is better and 2 if y is better. It also sets tied = true if there is a tie from Column's point of view. It is generous, in that if Column is indifferent between two states, it selects the state whose payoff is better for Row.} begin if colpayoff[x.row,x.col] > colpayoff[y.row,y.col] then begin betterstate.row := x.row; betterstate.col := x.col; betterindex := 1; tied := false; end {if} else if colpayoff[x.row,x.col] = colpayoff[y.row,y.col] then begin tied := true; if rowpayoff[x.row,x.col] > rowpayoff[y.row,y.col] then begin betterstate.row := x.row; betterstate.col := x.col; betterindex := 1; end else begin betterstate.row := y.row; betterstate.col := y.col; betterindex := 2; end; end else begin betterstate.row := y.row; betterstate.col := y.col; betterindex := 2; tied := false; end; {writeln('Compare ', rowpayoff[x.row,x.col]:2, ', ', colpayoff[x.row, x.col]:2, ' with ', rowpayoff[y.row, y.col]:2, ',', colpayoff[y.row,y.col]:2); writeln('by Column to give ', rowpayoff[betterstate.row,betterstate.col]:2, ',', colpayoff[betterstate.row,betterstate.col]:2);} end; {maximizecol} procedure update(n:integer); {This procedure performs the update of the outcometypes to level n, assuming it is known to level less than n.} var i,j,player: integer; beststate,tempstate,otherstate,top, gametemp, movetemp: states; {movetemp tells the nature of the move leading to top} T: integer; begin for i:= 1 to numberrows do for j := 1 to numbercolumns do { for player := 1 to 2 do } begin {compute outcometype[n,i,j,player]} { writeln('Finding outcome for iteration ', n:2, ' payoffs (', rowpayoff[i,j]:2,colpayoff[i,j]:2, ') and player ', player);} { if player = 1 then {row decides} { begin {find list of possible direct moves T for Row from (i,j) and maximize from the point of view of Row} {player 1 calculations} top.row := 0; top.col := 0; movetemp.row := 0; movetemp.col := 0; for T := 1 to numberrows do begin if T <> i then begin {compute the quantities to be maximized over T from R's view} tempstate.row := T; tempstate.col := j; otherstate.row := outcometype[n-1,T,j,1].row; otherstate.col := outcometype[n-1,T,j,1].col; {COMPILER ERROR: IT DOES NOT WORK TO MAKE THE FOLLOWING CALL: MAXIMIZEROW(OUTCOMETYPE[N-1,T,J,1],TEMPSTATE); IN FACT, THE WRONG ENTRY IS PASSED TO THE SUBROUTINE.} maximizerow(otherstate,tempstate); beststate.row := betterstate.row; beststate.col := betterstate.col; otherstate.row := outcometype[n-1,T,j,2].row; otherstate.col := outcometype[n-1,T,j,2].col; maximizecol(otherstate,beststate); beststate.row := betterstate.row; beststate.col := betterstate.col; maximizerow(beststate,top); top.row := betterstate.row; top.col := betterstate.col; if betterindex = 1 then begin movetemp.row := T; movetemp.col := j; end; end; {if} end; {for} outcometype[n,i,j,1].row := top.row; outcometype[n,i,j,1].col := top.col; movereq[n,i,j,1].row := movetemp.row; movereq[n,i,j,1].col := movetemp.col; {now move[n,i,j,1] contains the appropriate move if one is required} { end {row decides} { else {col decides} { begin {find list of possible direct moves T for Col from (i,j) and maximize from the point of view of Col} {player 2 calculations} top.row := 0; top.col := 0; movetemp.row := 0; movetemp.col := 0; for T := 1 to numbercolumns do begin if T <> j then begin {compute the quantities to be maximized over T from C's view} tempstate.row := i; tempstate.col := T; otherstate.row := outcometype[n-1,i,T,2].row; otherstate.col := outcometype[n-1,i,T,2].col; maximizecol(otherstate,tempstate); beststate.row := betterstate.row; beststate.col := betterstate.col; otherstate.row := outcometype[n-1,i,T,1].row; otherstate.col := outcometype[n-1,i,T,1].col; maximizerow(otherstate,beststate); beststate.row := betterstate.row; beststate.col := betterstate.col; maximizecol(beststate,top); top.row := betterstate.row; top.col := betterstate.col; if betterindex = 1 then begin movetemp.row := i; movetemp.col := T; end; end; {if} end; {for} outcometype[n,i,j,2].row := top.row; outcometype[n,i,j,2].col := top.col; movereq[n,i,j,2].row := movetemp.row; movereq[n,i,j,2].col := movetemp.col; { end; {col decides} end; {for j := 1 to} {Now compute the game results and the version of the move strategy if the first player may pass .} for i:= 1 to numberrows do for j := 1 to numbercolumns do begin otherstate.row := outcometype[n,i,j,2].row; otherstate.col := outcometype[n,i,j,2].col; tempstate.row := i; tempstate.col := j; maximizecol(tempstate, otherstate); tempstate.row := betterstate.row; tempstate.col := betterstate.col; otherstate.row := outcometype[n,i,j,1].row; otherstate.col := outcometype[n,i,j,1].col; maximizerow(otherstate,tempstate); game[n,i,j,1].row := betterstate.row; game[n,i,j,1].col := betterstate.col; if ((betterindex = 1) and not tied) then begin movepass[n,i,j,1].row := movereq[n,i,j,1].row; movepass[n,i,j,1].col := movereq[n,i,j,1].col; end else {pass} { if ((otherstate.row <> tempstate.row) or (otherstate.col <> tempstate.col) ) then} begin movepass[n,i,j,1].row := 0; movepass[n,i,j,1].col := 0; {pass} end; otherstate.row := outcometype[n,i,j,1].row; otherstate.col := outcometype[n,i,j,1].col; tempstate.row := i; tempstate.col := j; maximizerow(tempstate, otherstate); tempstate.row := betterstate.row; tempstate.col := betterstate.col; otherstate.row := outcometype[n,i,j,2].row; otherstate.col := outcometype[n,i,j,2].col; maximizecol(otherstate,tempstate); game[n,i,j,2].row := betterstate.row; game[n,i,j,2].col := betterstate.col; if ((betterindex = 1) and not tied) then begin movepass[n,i,j,2].row := movereq[n,i,j,2].row; movepass[n,i,j,2].col := movereq[n,i,j,2].col; end else {pass } { if ((otherstate.row <> tempstate.row) or (otherstate.col <> tempstate.col) ) then} begin movepass[n,i,j,2].row := 0; movepass[n,i,j,2].col := 0; {pass} end; end; {for j = 1 etc.} {Now compute the final version of the move strategy under the assumption that the previous player passed.} for i:= 1 to numberrows do for j := 1 to numbercolumns do begin otherstate.row := outcometype[n,i,j,1].row; otherstate.col := outcometype[n,i,j,1].col; tempstate.row := i; tempstate.col := j; maximizerow(tempstate, otherstate); if ((betterindex = 1) or tied) then begin moveprevpass[n,i,j,1].row := 0; moveprevpass[n,i,j,1].col := 0; end else {make the right move} begin moveprevpass[n,i,j,1].row := movereq[n,i,j,1].row; moveprevpass[n,i,j,1].col := movereq[n,i,j,1].col; end; otherstate.row := outcometype[n,i,j,2].row; otherstate.col := outcometype[n,i,j,2].col; tempstate.row := i; tempstate.col := j; maximizecol(tempstate, otherstate); if ((betterindex = 1) or tied) then begin moveprevpass[n,i,j,2].row := 0; moveprevpass[n,i,j,2].col := 0; end else {make the right move} begin moveprevpass[n,i,j,2].row := movereq[n,i,j,2].row; moveprevpass[n,i,j,2].col := movereq[n,i,j,2].col; end; end; {for j = 1 etc.} end; {update} begin {main} rewrite(outfile, 'STDMove2.output'); {initialize the payoff matrix} numberrows := 2; numbercolumns := 3; {cyclic game} rowpayoff[1,1] := 1; rowpayoff[1,2] := 6; rowpayoff[1,3] := 4; rowpayoff[2,1] := 5; rowpayoff[2,2] := 2; rowpayoff[2,3] := 3; colpayoff[1,1] := 3; colpayoff[1,2] := 2; colpayoff[1,3] := 1; colpayoff[2,1] := 4; colpayoff[2,2] := 5; colpayoff[2,3] := 6; {prisoners' dilemma: rowpayoff[1,1] := 3; rowpayoff[1,2] := 1; rowpayoff[2,1] := 4; rowpayoff[2,2] := 2; colpayoff[1,1] := 3; colpayoff[1,2] := 4; colpayoff[2,1] := 1; colpayoff[2,2] := 2;} {Initialize via input from the keyboard.} writeln('Enter the number of rows--no more than ', maxrownumber:3); readln(numberrows); If numberrows > maxrownumber then numberrows := maxrownumber; writeln('Enter the number of columns--no more than ', maxcolumnnumber:3); readln(numbercolumns); if numbercolumns > maxcolumnnumber then numbercolumns := maxcolumnnumber; {give zero values of the entries a negative payoff for initialization} for i:= 0 to numberrows do begin rowpayoff[i,0] := -32000; colpayoff[i,0] := -32000; end; for i := 0 to numbercolumns do begin rowpayoff[0,i] := -32000; colpayoff[0,i] := -32000; end; for i:= 1 to numberrows do for j := 1 to numbercolumns do begin writeln('Enter the payoffs for Row and then Column in row number ', i:2, ' and column number ', j:2); readln(rowpayoff[i,j], colpayoff[i,j]); end; writeln('Enter the desired number of iterations, no more than ', maxiterations:2); readln(numberits); if numberits > maxiterations then numberits := maxiterations; {initialize the outcome vector} 20: for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin outcometype[0,i,j,player].row := i; outcometype[0,i,j,player].col := j; game[0,i,j,player].row := i; game[0,i,j,player].col := j; movereq[0,i,j,player].row := 0; movereq[0,i,j,player].col := 0; movepass[0,i,j,player].row := 0; movepass[0,i,j,player].col := 0; end; for n := 1 to numberits do update(n); writeln('Here is the payoff matrix:'); writeln(outfile, 'Here is the payoff matrix:'); for i := 1 to numberrows do begin for j := 1 to numbercolumns do begin write( '(', rowpayoff[i,j]:2, ',', colpayoff[i,j]:2, ') '); write(outfile, '(', rowpayoff[i,j]:2, ',', colpayoff[i,j]:2, ') '); end; writeln(outfile); writeln; end; writeln('Players may NOT move to the current cell.'); writeln('Ties are handled by the Generosity Convention.'); writeln('For ', numberits:2, ' moves:'); writeln('Following are outcomes if the initial player MUST move:'); writeln(outfile,'Players may NOT move to the current cell.'); writeln(outfile,'Ties are handled by the Generosity Convention.'); writeln(outfile, 'For ', numberits:2, ' moves:'); writeln(outfile, 'Following are outcomes if the initial player MUST move:'); for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 0 to numberits do begin k := outcometype[n,i,j,player].row; l := outcometype[n,i,j,player].col; writeln('Outcome[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is index(',k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1,')' ); writeln(outfile, 'Outcome[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is index(',k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1,')' ); end; {for n} writeln; writeln(outfile); end; {for player} writeln; writeln(outfile); writeln('If the initial player may pass instead of moving, the outcomes are:'); writeln; writeln(outfile,'If the initial player may pass instead of moving, the outcomes are:'); writeln(outfile); for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 0 to numberits do begin k := game[n,i,j,player].row; l := game[n,i,j,player].col; writeln('Outcome[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is index(',k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1,')' ); writeln(outfile, 'Outcome[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is index(',k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1,')' ); end; {for n} writeln; writeln(outfile); end; {for player} writeln(outfile, 'If the first player MUST move, then the best moves are as follows:'); writeln; for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 1 to numberits do begin write(outfile, 'Move[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is '); k := movereq[n,i,j,player].row; l := movereq[n,i,j,player].col; if k = 0 then begin writeln(outfile, 'pass'); end else begin writeln(outfile, 'to index(', k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1, ')'); end; end; {for n} writeln(outfile); end; {for player} writeln(outfile, 'If the first player may pass but the previous player did not pass'); writeln(outfile, 'so that a pass does not end the game, then the best moves are as follows:'); writeln(outfile); for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 1 to numberits do begin write(outfile, 'Move[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is '); k := movepass[n,i,j,player].row; l := movepass[n,i,j,player].col; if k = 0 then begin writeln(outfile, 'pass'); end else begin writeln(outfile, 'to index(', k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1, ')'); end; end; {for n} writeln(outfile); end; {for player} writeln(outfile, 'If the first player may pass and the previous player also passed'); writeln(outfile, 'so that a pass ends the game, then the best moves are as follows:'); writeln(outfile); for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 1 to numberits do begin write(outfile, 'Move[', n:2, ' if ', player:1, ' starts index(', i:1, ',', j:1, ')=payoff(', rowpayoff[i,j]:1, ',', colpayoff[i,j]:1, ') ] is '); k := moveprevpass[n,i,j,player].row; l := moveprevpass[n,i,j,player].col; if k = 0 then begin writeln(outfile, 'pass'); end else begin writeln(outfile, 'to index(', k:1, ',', l:1, ')=payoff(', rowpayoff[k,l]:1, ',', colpayoff[k,l]:1, ')'); end; end; {for n} writeln(outfile); end; {for player} writeln(outfile, 'Play is standard in that a player may NOT move to the current cell.'); { writeln('Outcomes indicated by row and column index values:'); writeln('For ', numberits:2, ' moves:'); for i:=1 to numberrows do for j := 1 to numbercolumns do for player := 1 to 2 do begin for n := 0 to numberits do begin writeln('Outcome [', n:2, ' moves, starter ', player:2, ', from index state (', i:2, ',', j:2, ') ] = (', outcometype[n,i,j,player].row:2, ',', outcometype[n,i,j,player].col:2, ')'); end; {for n} { writeln; end; {for player} writeln(outfile); 10: writeln('Enter twice to halt.'); writeln('Enter 1 to change the parameters.'); readln(xx); if xx <> '1' then begin close(outfile); halt; end; 30: writeln('Enter 3 to change the maximum number of moves allowed.'); writeln('Enter 4 to change the payoff matrix.'); writeln('Enter 5 if you are done making changes.'); readln(j); case j of 3: begin writeln('Enter the desired number of iterations, no more than ', maxiterations:2); readln(numberits); if numberits > maxiterations then numberits := maxiterations; end; 4: begin writeln('Enter the number of rows--no more than ', maxrownumber:3); readln(numberrows); If numberrows > maxrownumber then numberrows := maxrownumber; writeln('Enter the number of columns--no more than ', maxcolumnnumber:3); readln(numbercolumns); if numbercolumns > maxcolumnnumber then numbercolumns := maxcolumnnumber; for i:= 0 to numberrows do begin rowpayoff[i,0] := -1000; colpayoff[i,0] := -1000; end; for i := 0 to numbercolumns do begin rowpayoff[0,i] := -1000; colpayoff[0,i] := -1000; end; for i:= 1 to numberrows do for j := 1 to numbercolumns do begin writeln('Enter the payoffs for Row and then Column in row number ', i:2, ' and column number ', j:2); readln(rowpayoff[i,j], colpayoff[i,j]); end; end; 5: begin goto 20; end; end; goto 30; end.