Slide 5, a strategic game.
This web page contains the rules and complete Pascal source
code for the game Slide 5. This is based on a game issued by Milton Bradley.
HOW TO PLAY SLIDE, A STRATEGIC GAME
Slide is a simple strategic game that you play against the computer.
The game board is a 5-by-5 square:
1 2 3 4 5
---------
6 : : : : : :
---------
7 : : : : : :
---------
8 : : : : : :
---------
9 : : : : : :
---------
10 : : : : : :
---------
The game board as presented by the computer looks nicer than that.
A legal move is to push a player token into a column from the top,
or into a
row from the left side. The move numbers are shown in the figure above.
When you play, your token will be an 'O', and the computer's
token will be
an 'X'. A typical game position is shown below:
1 2 3 4 5
---------
6 :X:X:X: : :
---------
7 :O:X:O: : :
---------
8 :X O: : : :
---------
9 :O:X: : : :
---------
10 :O:X X: : :
---------
A player wins by getting 5 in a line, either in a row,
a column, or a
diagonal. Thus, if X makes move number 8 in the above situation, X wins.
We have a rule that if the moving player gets 5 in a line,
that player wins.
If the moving player doesn't win, but does make 5
in a line for the other player,
then the other player wins. In the situation in the figure above,
if O makes move number 8, then X wins in column 2.
TIES
It is possible to get into a loop in which the players repeat their moves
over and over. In our game, we declare a tie if both players repeat 4 moves in a row.
PLAYING THE GAME
The game is called slide.
The program will ask you for a limit of evaluation. This is the number of moves
ahead the program will look when it is deciding its best move. If you say
4, the program will look 4 moves ahead.
The program will show you which move sequences it is considering.
The greater the limit of evaluation, the longer a move will take, and the slower
the program will play. We recommend level 2 for beginners.
The program uses a method called minimax with alpha-beta pruning
to decide on its best move. The method is discussed in many books on artificial
intelligence.
Pascal source code
program slide5(input,output);
const
inf = 100;
infm = -100;
BACKSPACE = chr(8);
label 201,202,203,299;
type
token = -1..1;
bdim = 1..5;
board = array[1..5,1..5] of token;
var
n,i,j,limit,best,val,k,me,you,tie : integer;
moveseq : array[1..8] of integer;
position,nextpos : board;
pflag,sflag : boolean;
answer : char;
gridline: array[1..3] of string(11);
moveleft: string(3);
function tics: word; extern;
procedure initgrid;
var
pos: integer;
begin
gridline[1][1] := chr(201); { upper left corner }
gridline[1][11] := chr(187); { upper right corner }
gridline[2][1] := chr(199); { left tee }
gridline[2][11] := chr(182); { right tee }
gridline[3][1] := chr(200); { lower left corner }
gridline[3][11] := chr(188); { lower right corner }
pos := 2;
while pos < 11 do
begin
gridline[1][pos] := chr(205); { horizontal bar }
gridline[2][pos] := chr(196); { horizontal bar }
gridline[3][pos] := chr(205); { horizontal bar }
pos := pos + 2
end;
pos := 3;
while pos < 11 do
begin
gridline[1][pos] := chr(209); { top tee }
gridline[2][pos] := chr(197); { cross }
gridline[3][pos] := chr(207); { bottom tee }
pos := pos + 2
end
end;
function intg : integer;
var i,w,k : integer;
line : array[1..80] of char;
flag : boolean;
begin
flag := false;
while not flag do begin
w := 0;
i := 1;
while (i < 81) and (not eoln(input)) do begin read(line[i]); i := i + 1 end; readln;
k := i ;
i := 1;
while (i < k) and ((line[i] < '0') or (line[i] > '9')) do i := i + 1;
if i <> k then begin
flag := true;
while (line[i] >= '0') and (line[i] <= '9') and (i < k) do begin
n := ord(line[i]) - 48;
if w > ( (maxint - n) div 10) then begin i := k; flag := false end
else begin
w := w * 10 + n;
i := i + 1
end
end
end
end;
intg := w
end;
function diff(pos:board):integer;
var i,j,d1: integer;
begin
d1 := 0;
for i := 1 to 5 do for j := 1 to 5 do d1 := d1 + pos[i,j];
diff := d1
end;
function even(n: integer):boolean;
begin
if 2 * (n div 2) = n then even := true else even := false
end;
function istie:boolean;
var i : integer;
begin
istie := true;
for i := 1 to 3 do begin
if moveseq[2*i] <> moveseq[2*i + 2] then istie := false;
if moveseq[2*i - 1] <> moveseq[2*i + 1] then istie := false
end
end;
procedure updatemoves(mov : integer);
var i: integer;
begin
for i := 1 to 7 do moveseq[i] := moveseq[i+1];
moveseq[8] := mov
end;
function wins(pos:board) : integer;
var i,j,major,minor,q1,w1 : integer;
row,col : array[1..5] of integer;
t1,t2 : boolean;
begin
t1 := false; t2 := false;
for i := 1 to 5 do begin row[i] := 0; col[i] := 0 end;
major := 0; minor := 0; w1 := 0;
for i := 1 to 5 do begin
for j := 1 to 5 do begin
q1 := pos[i,j];row[i] := row[i] + q1; col[j] := col[j] + q1
end;
major := major + pos[i,i];
minor := minor + pos[i,6-i]
end;
for i := 1 to 5 do begin if (row [i] = 5) or (col[i] = 5) then t1 := true;
if (row[i] = -5 ) or (col[i] = -5) then t2 := true end;
if (minor = 5 ) or (major = 5) then t1 := true;
if (minor = -5) or (major = -5) then t2 := true;
if t1 then w1 := 1;
if t2 then w1 := w1 + 2;
wins := w1
end;
procedure pushrow(row : bdim; t : token; pos : board; var newpos: board);
var i,j : integer;
begin
for i := 1 to 5 do for j := 1 to 5 do newpos[i,j] := pos[i,j];
i := 1;
while (newpos[row,i] <> 0) and (i < 5) do i := i + 1;
for j := i downto 2 do newpos[row,j] := newpos[row,j-1];
newpos[row,1] := t
end;
procedure pushcol(col : bdim; t : token; pos : board; var newpos: board);
var i,j : integer;
begin
for i := 1 to 5 do for j := 1 to 5 do newpos[i,j] := pos[i,j];
i := 1;
while (newpos[i,col] <> 0) and (i < 5) do i := i + 1;
for j := i downto 2 do newpos[j,col] := newpos[j-1,col];
newpos[1,col] := t
end;
procedure successor (pos : board; move : integer; player : token; var newpos :
board);
begin
if move < 6 then pushcol(move,player,pos,newpos)
else pushrow(move-5,player,pos,newpos)
end;
procedure printboard(pos : board);
var i,j : integer;
begin
writeln(' 1 2 3 4 5');
writeln(' ',gridline[1]);
for i := 1 to 5 do begin
write(i + 5 : 2,' ',chr(186));
for j := 1 to 5 do
begin
case pos[i,j] of
1: write('X');
-1: write('O');
0: write(' ');
end;
if j < 5
then write(chr(179))
else write(chr(186))
end;
writeln; if i < 5 then writeln(' ',gridline[2])
else writeln(' ',gridline[3])
end;
writeln
end;
procedure printinfo (alpha,beta,level : integer);
begin
writeln(' alpha = ',alpha,' beta = ',beta,' level = ',level)
end;
procedure pmove(level,moveno: integer);
var i: integer;
begin
for i := 0 to level do write(' ');
write(moveno : 3)
end;
procedure minimax(alpha,beta,level : integer; position :board;
var bestmove: integer; var posvalue : integer);
label 102,101,999;
var moveno,w1,k,bmove,valb : integer;
nextpos : board;
begin
bestmove := 0;
moveno := 1;
if level = limit then begin
posvalue := diff(position); goto 999
end;
if even(level) then begin
repeat
write(moveno : 3);
successor(position,moveno,1,nextpos);
k := wins(nextpos);
if (k = 1) or (k = 3) then begin
bestmove := moveno; posvalue := inf; write(moveleft);goto 999
end;
if k = 2 then begin
goto 102
end;
minimax(alpha,beta,level + 1,nextpos,bmove,valb);
if valb = infm then goto 102;
if valb > alpha then begin
alpha := valb; bestmove := moveno
end;
if alpha >= beta then begin
posvalue := alpha; write(moveleft);goto 999
end;
102: moveno := moveno + 1; write(moveleft);
until moveno > 10;
posvalue := alpha; goto 999 end
else begin
repeat
write(moveno : 3);
successor(position,moveno,-1,nextpos);
k := wins(nextpos);
if k >= 2 then begin
bestmove := moveno; posvalue := infm; write(moveleft);goto 999
end;
if k = 1 then begin
goto 101
end;
minimax(alpha,beta,level + 1,nextpos,bmove,valb);
if valb = inf then goto 101;
if valb < beta then begin
beta := valb; bestmove := moveno
end;
if alpha >= beta then begin
posvalue := beta; write(moveleft);goto 999
end;
101: moveno := moveno + 1; write(moveleft);
until moveno > 10;
posvalue := beta end;
999: write(' ',moveleft)
end;
procedure domove(var pos : board);
var mov : integer;
begin
repeat writeln('Enter a move number (1-10):'); mov := intg;
until (mov <= 10) and (mov >= 1);
writeln; writeln('Your move is ',mov);writeln;
successor(pos,mov,-1,pos); printboard(pos);writeln;
updatemoves(mov);
end;
procedure init(var pos : board);
var i,j : integer;
begin
for i := 1 to 5 do
for j := 1 to 5 do
pos[i,j] := 0
end;
begin
moveleft[1] := BACKSPACE;
moveleft[2] := BACKSPACE;
moveleft[3] := BACKSPACE;
initgrid; { initialize char strings to print game grid }
you := 0; me := 0; tie := 0;
repeat
pflag := true; writeln('What limit of evaluation do you want?');
repeat begin limit := intg;
if limit < 2 then writeln('Must be >= 2; enter again:') end
until limit >= 2;
writeln('Limit of evaluation is ',limit:1,'.');
init(position);
for i := 1 to 8 do moveseq[i] := 0;
writeln('Do you want to move first?');
readln(answer);
if(answer) = 'y' then sflag := true else sflag := false;
if sflag
then begin
printboard(position); writeln;
domove(position)
end;
i := abs(ord(tics)) mod 10; i := i + 1;
writeln('My move is ',i);
updatemoves(i);
successor(position,i,1,position);
printboard(position); writeln;
domove(position);
i := abs(ord(tics)) mod 10; i := i + 1;
writeln('My move is ',i);
updatemoves(i);
successor(position,i,1,position);
printboard(position); writeln;
domove(position);
repeat
i := 1;
repeat
successor(position,i,1,nextpos);
k := wins(nextpos ); i := i+1
until (i > 10) or (k = 1) or (k = 3);
if (k = 1) or (k = 3) then begin
writeln('My move is ',i-1);
printboard(nextpos);
goto 202;
end
else
begin
minimax(infm,inf,0,position,best,val);
if best = 0 then best := 1;
writeln('My move is ',best);
writeln;
successor(position,best,1,position);
printboard(position);
writeln;
updatemoves(best);
k := wins(position);
if k = 2 then goto 201 ;
if istie then goto 203;
domove(position);
k := wins(position);
if k = 2 then goto 201;
if k > 0 then goto 202;
if istie then goto 203;
end;
until false;
201: writeln('You win!'); you := you + 1; goto 299;
202: writeln('I win!'); me := me + 1; goto 299;
203: writeln('This is a tie game.'); tie := tie + 1;
299: writeln('You have won ',you:1,' and I have won ',me:1);
writeln('There have been ',tie:1,' ties.');
writeln('Do you want another game?');
readln(answer)
until answer <> 'y'
end.