| 1 |
(* Copyright (C) 2007 Free Software Foundation, Inc. *) |
| 2 |
(* This file is part of GNU Modula-2. |
| 3 |
|
| 4 |
GNU Modula-2 is free software; you can redistribute it and/or modify it under |
| 5 |
the terms of the GNU General Public License as published by the Free |
| 6 |
Software Foundation; either version 2, or (at your option) any later |
| 7 |
version. |
| 8 |
|
| 9 |
GNU Modula-2 is distributed in the hope that it will be useful, but WITHOUT ANY |
| 10 |
WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 11 |
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 12 |
for more details. |
| 13 |
|
| 14 |
You should have received a copy of the GNU General Public License along |
| 15 |
with gm2; see the file COPYING. If not, write to the Free Software |
| 16 |
Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *) |
| 17 |
|
| 18 |
MODULE pegfive ; |
| 19 |
|
| 20 |
|
| 21 |
FROM SYSTEM IMPORT BYTE ; |
| 22 |
FROM NumberIO IMPORT WriteCard, StrToCard, WriteInt ; |
| 23 |
FROM StrIO IMPORT ReadString, WriteString, WriteLn ; |
| 24 |
FROM StdIO IMPORT Write ; |
| 25 |
FROM StrLib IMPORT StrLen, StrRemoveWhitePrefix, StrEqual ; |
| 26 |
FROM Selective IMPORT Timeval, GetTimeOfDay, GetTime, InitTime, KillTime ; |
| 27 |
FROM FIO IMPORT FlushBuffer, StdOut ; |
| 28 |
|
| 29 |
|
| 30 |
CONST |
| 31 |
EnableGame = FALSE ; (* Set to TRUE if you want to play |
| 32 |
the game. *) |
| 33 |
BoardX = 16 ; |
| 34 |
BoardY = 16 ; |
| 35 |
BoardSize = BoardX * BoardY ; |
| 36 |
AreaRadius = 1 ; |
| 37 |
MaxScore = 100000 ; |
| 38 |
MinScore = -100000 ; |
| 39 |
OpenFour = 10000 ; |
| 40 |
OpenThree = 1000 ; |
| 41 |
OpenTwo = 100 ; |
| 42 |
WinScore = MaxScore ; |
| 43 |
LooseScore = -WinScore ; |
| 44 |
MaxTimePerMove = 8 ; |
| 45 |
MinTimePerMove = 3 ; |
| 46 |
|
| 47 |
TYPE |
| 48 |
Squares = [0..BoardSize-1] ; |
| 49 |
|
| 50 |
Moves = RECORD |
| 51 |
NoOfPegs: CARDINAL ; |
| 52 |
Tiles : ARRAY [0..BoardSize] OF BYTE ; |
| 53 |
END ; |
| 54 |
|
| 55 |
Board = RECORD |
| 56 |
Pegs : Moves ; |
| 57 |
Colours : SetOfSquare ; |
| 58 |
END ; |
| 59 |
|
| 60 |
SetOfSquare = SET OF Squares ; |
| 61 |
|
| 62 |
Colour = (black, white) ; |
| 63 |
|
| 64 |
|
| 65 |
VAR |
| 66 |
count, |
| 67 |
NoOfPlies: CARDINAL ; |
| 68 |
|
| 69 |
|
| 70 |
(* |
| 71 |
InitBoard - initialize the board. |
| 72 |
*) |
| 73 |
|
| 74 |
PROCEDURE InitBoard (VAR b: Board) ; |
| 75 |
BEGIN |
| 76 |
b.Pegs.NoOfPegs := 0 ; |
| 77 |
b.Colours := SetOfSquare{} |
| 78 |
END InitBoard ; |
| 79 |
|
| 80 |
|
| 81 |
(* |
| 82 |
CreateListOfMachineMoves - given board, b, generate a list of possible |
| 83 |
moves to consider in, m, for colour, c. |
| 84 |
*) |
| 85 |
|
| 86 |
PROCEDURE CreateListOfMoves (VAR b: Board; VAR m: Moves; c: Colour) ; |
| 87 |
VAR |
| 88 |
i : CARDINAL ; |
| 89 |
t, j, n: INTEGER ; |
| 90 |
BEGIN |
| 91 |
m.NoOfPegs := 0 ; |
| 92 |
n := 0 ; |
| 93 |
i := 0 ; |
| 94 |
WHILE i<b.Pegs.NoOfPegs DO |
| 95 |
t := VAL(INTEGER, b.Pegs.Tiles[i]) ; |
| 96 |
FOR j := 1 TO AreaRadius DO |
| 97 |
IfFreeAdd(b, m, (t-1)*j, c) ; |
| 98 |
IfFreeAdd(b, m, (t+1)*j, c) ; |
| 99 |
IfFreeAdd(b, m, (t-BoardX)*j, c) ; |
| 100 |
IfFreeAdd(b, m, (t+BoardX)*j, c) ; |
| 101 |
IfFreeAdd(b, m, (t-(BoardX+1))*j, c) ; |
| 102 |
IfFreeAdd(b, m, (t+(BoardX+1))*j, c) ; |
| 103 |
IfFreeAdd(b, m, (t-(BoardX-1))*j, c) ; |
| 104 |
IfFreeAdd(b, m, (t+(BoardX-1))*j, c) |
| 105 |
END ; |
| 106 |
INC(i) |
| 107 |
END |
| 108 |
END CreateListOfMoves ; |
| 109 |
|
| 110 |
|
| 111 |
(* |
| 112 |
IfFreeAdd - tests to see whether position, i, is legal |
| 113 |
and adds it to the list of moves, m. |
| 114 |
*) |
| 115 |
|
| 116 |
PROCEDURE IfFreeAdd (VAR b: Board; VAR m: Moves; i: INTEGER; c: Colour) ; |
| 117 |
VAR |
| 118 |
n: CARDINAL ; |
| 119 |
BEGIN |
| 120 |
IF (i>=0) AND (i<BoardSize) |
| 121 |
THEN |
| 122 |
n := 0 ; |
| 123 |
WHILE n<b.Pegs.NoOfPegs DO |
| 124 |
IF VAL(INTEGER, b.Pegs.Tiles[n])=i |
| 125 |
THEN |
| 126 |
RETURN |
| 127 |
END ; |
| 128 |
INC(n) |
| 129 |
END ; |
| 130 |
(* it is free, so add it to, m *) |
| 131 |
m.Tiles[m.NoOfPegs] := VAL(BYTE, i) ; |
| 132 |
INC(m.NoOfPegs) ; |
| 133 |
END |
| 134 |
END IfFreeAdd ; |
| 135 |
|
| 136 |
|
| 137 |
(* |
| 138 |
MaximumScore - returns TRUE if the maximim score was found. |
| 139 |
*) |
| 140 |
|
| 141 |
PROCEDURE MaximumScore (score: INTEGER) : BOOLEAN ; |
| 142 |
BEGIN |
| 143 |
IF (score<=MinScore) OR (score>=MaxScore) |
| 144 |
THEN |
| 145 |
RETURN TRUE |
| 146 |
ELSE |
| 147 |
RETURN FALSE |
| 148 |
END |
| 149 |
END MaximumScore ; |
| 150 |
|
| 151 |
|
| 152 |
(* |
| 153 |
IsPositionCol - returns TRUE if position, pos, on board, b, contains a peg |
| 154 |
of colour, c. |
| 155 |
*) |
| 156 |
|
| 157 |
PROCEDURE IsPositionCol (VAR b: Board; pos: CARDINAL; c: Colour) : BOOLEAN ; |
| 158 |
VAR |
| 159 |
p: CARDINAL ; |
| 160 |
BEGIN |
| 161 |
p := b.Pegs.NoOfPegs ; |
| 162 |
WHILE p>0 DO |
| 163 |
DEC(p) ; |
| 164 |
IF VAL(CARDINAL, b.Pegs.Tiles[p])=pos |
| 165 |
THEN |
| 166 |
IF c=white |
| 167 |
THEN |
| 168 |
RETURN pos IN b.Colours |
| 169 |
ELSE |
| 170 |
RETURN NOT (pos IN b.Colours) |
| 171 |
END |
| 172 |
END |
| 173 |
END ; |
| 174 |
RETURN FALSE |
| 175 |
END IsPositionCol ; |
| 176 |
|
| 177 |
|
| 178 |
(* |
| 179 |
IsPositionEmpty - returns TRUE if position, pos, on board, b, is empty. |
| 180 |
*) |
| 181 |
|
| 182 |
PROCEDURE IsPositionEmpty (VAR b: Board; pos: CARDINAL) : BOOLEAN ; |
| 183 |
VAR |
| 184 |
p: CARDINAL ; |
| 185 |
BEGIN |
| 186 |
p := b.Pegs.NoOfPegs ; |
| 187 |
WHILE p>0 DO |
| 188 |
DEC(p) ; |
| 189 |
IF VAL(CARDINAL, b.Pegs.Tiles[p])=pos |
| 190 |
THEN |
| 191 |
RETURN FALSE |
| 192 |
END |
| 193 |
END ; |
| 194 |
RETURN TRUE |
| 195 |
END IsPositionEmpty ; |
| 196 |
|
| 197 |
|
| 198 |
(* |
| 199 |
CheckDir - search back to at most square, begin, and then search forward to |
| 200 |
at most position, end, for a run of pegs. |
| 201 |
*) |
| 202 |
|
| 203 |
PROCEDURE CheckDir (VAR b: Board; pos: INTEGER; |
| 204 |
col: Colour; dec, inc: INTEGER; |
| 205 |
begin, end: INTEGER; score: INTEGER) : INTEGER ; |
| 206 |
VAR |
| 207 |
newscore: INTEGER ; |
| 208 |
open, |
| 209 |
count : CARDINAL ; |
| 210 |
BEGIN |
| 211 |
WITH b DO |
| 212 |
IF (pos>=begin) AND IsPositionCol(b, pos, col) |
| 213 |
THEN |
| 214 |
WHILE (pos>=begin) AND IsPositionCol(b, pos, col) DO |
| 215 |
pos := pos + dec |
| 216 |
END ; |
| 217 |
open := 0 ; |
| 218 |
IF (pos>=begin) AND IsPositionEmpty(b, pos) |
| 219 |
THEN |
| 220 |
(* open this end *) |
| 221 |
open := 1 |
| 222 |
END ; |
| 223 |
pos := pos + inc * 2 ; |
| 224 |
count := 1 ; |
| 225 |
WHILE (pos<=end) AND IsPositionCol(b, pos, col) DO |
| 226 |
pos := pos + inc ; |
| 227 |
INC(count) |
| 228 |
END ; |
| 229 |
IF (pos<end) AND IsPositionEmpty(b, pos) |
| 230 |
THEN |
| 231 |
(* open this end *) |
| 232 |
INC(open) |
| 233 |
END ; |
| 234 |
IF open>1 |
| 235 |
THEN |
| 236 |
DEC(open) |
| 237 |
END ; |
| 238 |
CASE count OF |
| 239 |
|
| 240 |
2: newscore := open*OpenTwo | |
| 241 |
3: newscore := open*OpenThree | |
| 242 |
4: newscore := open*OpenFour | |
| 243 |
5: IF col=white |
| 244 |
THEN |
| 245 |
RETURN MaxScore |
| 246 |
ELSE |
| 247 |
RETURN MinScore |
| 248 |
END |
| 249 |
ELSE |
| 250 |
newscore := 0 |
| 251 |
END ; |
| 252 |
IF col=white |
| 253 |
THEN |
| 254 |
RETURN score+newscore |
| 255 |
ELSE |
| 256 |
RETURN score-newscore |
| 257 |
END |
| 258 |
ELSE |
| 259 |
RETURN score |
| 260 |
END |
| 261 |
END |
| 262 |
END CheckDir ; |
| 263 |
|
| 264 |
|
| 265 |
(* |
| 266 |
RemoveScore - removes the value of a line of pegs starting at position, pos, |
| 267 |
from the, score, and returns the new score. |
| 268 |
*) |
| 269 |
|
| 270 |
PROCEDURE RemoveScore (VAR b: Board; pos: INTEGER; |
| 271 |
dec, inc: INTEGER; |
| 272 |
begin, end: INTEGER; score: INTEGER) : INTEGER ; |
| 273 |
VAR |
| 274 |
col: Colour ; |
| 275 |
BEGIN |
| 276 |
IF (pos >= 0) AND (pos < BoardSize) |
| 277 |
THEN |
| 278 |
IF IsPositionEmpty(b, pos) |
| 279 |
THEN |
| 280 |
RETURN score |
| 281 |
ELSE |
| 282 |
IF IsPositionCol(b, pos, white) |
| 283 |
THEN |
| 284 |
col := white |
| 285 |
ELSE |
| 286 |
col := black |
| 287 |
END ; |
| 288 |
score := score - CheckDir(b, pos, col, dec, inc, begin, end, 0) |
| 289 |
END |
| 290 |
END ; |
| 291 |
RETURN score |
| 292 |
END RemoveScore ; |
| 293 |
|
| 294 |
|
| 295 |
(* |
| 296 |
CalcScore - returns the new score if move, pos, is played |
| 297 |
by colour, col. |
| 298 |
*) |
| 299 |
|
| 300 |
PROCEDURE CalcScore (VAR b: Board; score: INTEGER; |
| 301 |
pos: INTEGER; col: Colour) : INTEGER ; |
| 302 |
VAR |
| 303 |
s : INTEGER ; |
| 304 |
x, y, |
| 305 |
lup, rdown, |
| 306 |
ldown, rup, |
| 307 |
up, down, |
| 308 |
left, right: CARDINAL ; |
| 309 |
BEGIN |
| 310 |
x := pos MOD BoardX ; |
| 311 |
y := pos DIV BoardX ; |
| 312 |
left := y * BoardX ; |
| 313 |
right := left+BoardX-1 ; |
| 314 |
down := x ; |
| 315 |
up := down + (BoardX*(BoardY-1)) ; |
| 316 |
|
| 317 |
(* diag left down *) |
| 318 |
IF x>y |
| 319 |
THEN |
| 320 |
ldown := x-y |
| 321 |
ELSE |
| 322 |
ldown := (y-x) * BoardY |
| 323 |
END ; |
| 324 |
(* diag right up *) |
| 325 |
IF x>y |
| 326 |
THEN |
| 327 |
rup := (BoardX-x+y)*BoardY-1 |
| 328 |
ELSE |
| 329 |
rup := ((BoardY-1)-y+x) + (BoardY-1)*BoardY |
| 330 |
END ; |
| 331 |
(* diag left up *) |
| 332 |
IF x>=BoardY-y |
| 333 |
THEN |
| 334 |
lup := (BoardY-1)*BoardX+(x-(BoardY-1-y)) |
| 335 |
ELSE |
| 336 |
lup := (y+x)*BoardY |
| 337 |
END ; |
| 338 |
(* diag right down *) |
| 339 |
IF y >= BoardX-x |
| 340 |
THEN |
| 341 |
rdown := (y-(BoardX-x-1))*BoardY+BoardX-1 |
| 342 |
ELSE |
| 343 |
rdown := x+y |
| 344 |
END ; |
| 345 |
|
| 346 |
(* firstly remove previous score for both colours from adjacent pegs *) |
| 347 |
score := RemoveScore(b, pos-1, -1, +1, left, right, score) ; |
| 348 |
score := RemoveScore(b, pos+1, +1, -1, left, right, score) ; |
| 349 |
score := RemoveScore(b, pos-BoardX, -BoardX, +BoardX, down, up, score) ; |
| 350 |
score := RemoveScore(b, pos+BoardX, +BoardX, -BoardX, down, up, score) ; |
| 351 |
|
| 352 |
score := RemoveScore(b, pos+(BoardX-1), +(BoardX-1), -(BoardX-1), rdown, lup, score) ; |
| 353 |
score := RemoveScore(b, pos-(BoardX-1), -(BoardX-1), +(BoardX-1), rdown, lup, score) ; |
| 354 |
score := RemoveScore(b, pos+(BoardX+1), +(BoardX+1), -(BoardX+1), ldown, rup, score) ; |
| 355 |
score := RemoveScore(b, pos-(BoardX+1), -(BoardX+1), +(BoardX+1), ldown, rup, score) ; |
| 356 |
|
| 357 |
(* now add our new peg *) |
| 358 |
ApplyMove(b, col, pos) ; |
| 359 |
|
| 360 |
(* and calculate the new score *) |
| 361 |
|
| 362 |
s := CheckDir(b, pos, col, -1, +1, left, right, 0) ; |
| 363 |
IF MaximumScore(s) |
| 364 |
THEN |
| 365 |
RETURN s |
| 366 |
END ; |
| 367 |
score := score + s ; |
| 368 |
|
| 369 |
s := CheckDir(b, pos, col, -BoardX, +BoardX, down, up, 0) ; |
| 370 |
IF MaximumScore(s) |
| 371 |
THEN |
| 372 |
RETURN s |
| 373 |
END ; |
| 374 |
score := score + s ; |
| 375 |
|
| 376 |
s := CheckDir(b, pos, col, -(BoardX+1), +(BoardX+1), ldown, rup, 0) ; |
| 377 |
IF MaximumScore(s) |
| 378 |
THEN |
| 379 |
RETURN s |
| 380 |
END ; |
| 381 |
score := score + s ; |
| 382 |
|
| 383 |
s := CheckDir(b, pos, col, -(BoardX-1), +(BoardX-1), rdown, lup, 0) ; |
| 384 |
IF MaximumScore(s) |
| 385 |
THEN |
| 386 |
RETURN s |
| 387 |
END ; |
| 388 |
score := score + s ; |
| 389 |
|
| 390 |
RETURN score |
| 391 |
END CalcScore ; |
| 392 |
|
| 393 |
|
| 394 |
(* |
| 395 |
DisplayBoard - displays the pegfive board. |
| 396 |
*) |
| 397 |
|
| 398 |
PROCEDURE DisplayBoard (VAR b: Board) ; |
| 399 |
VAR |
| 400 |
pos, |
| 401 |
i, x, y: CARDINAL ; |
| 402 |
written: BOOLEAN ; |
| 403 |
BEGIN |
| 404 |
WriteString(' A B C D E F G H I J K L M N O P') ; WriteLn ; |
| 405 |
WriteString(' +---------------------------------+') ; WriteLn ; |
| 406 |
FOR y := BoardY TO 1 BY -1 DO |
| 407 |
WriteCard(y, 2) ; Write('|') ; |
| 408 |
FOR x := 0 TO BoardX-1 DO |
| 409 |
i := b.Pegs.NoOfPegs ; |
| 410 |
written := FALSE ; |
| 411 |
WHILE i>0 DO |
| 412 |
pos := VAL(CARDINAL, b.Pegs.Tiles[i-1]) ; |
| 413 |
IF pos=((y-1)*BoardX)+x |
| 414 |
THEN |
| 415 |
written := TRUE ; |
| 416 |
IF pos IN b.Colours |
| 417 |
THEN |
| 418 |
WriteString(' O') |
| 419 |
ELSE |
| 420 |
WriteString(' X') |
| 421 |
END |
| 422 |
END ; |
| 423 |
DEC(i) |
| 424 |
END ; |
| 425 |
IF NOT written |
| 426 |
THEN |
| 427 |
WriteString(' .') |
| 428 |
END |
| 429 |
END ; |
| 430 |
WriteString(' |') ; WriteCard(y, 0) ; WriteLn |
| 431 |
END ; |
| 432 |
WriteString(' +---------------------------------+') ; WriteLn ; |
| 433 |
WriteString(' A B C D E F G H I J K L M N O P') ; WriteLn |
| 434 |
END DisplayBoard ; |
| 435 |
|
| 436 |
|
| 437 |
(* |
| 438 |
WriteColour - displays the colour, c. |
| 439 |
*) |
| 440 |
|
| 441 |
PROCEDURE WriteColour (c: Colour) ; |
| 442 |
BEGIN |
| 443 |
CASE c OF |
| 444 |
|
| 445 |
white: WriteString('naughts') | |
| 446 |
black: WriteString('crosses') |
| 447 |
|
| 448 |
END |
| 449 |
END WriteColour ; |
| 450 |
|
| 451 |
|
| 452 |
(* |
| 453 |
ApplyMove - adds move, pos, to board. |
| 454 |
*) |
| 455 |
|
| 456 |
PROCEDURE ApplyMove (VAR b: Board; c: Colour; pos: CARDINAL) ; |
| 457 |
BEGIN |
| 458 |
IF b.Pegs.NoOfPegs<BoardSize |
| 459 |
THEN |
| 460 |
b.Pegs.Tiles[b.Pegs.NoOfPegs] := VAL(BYTE, pos) ; |
| 461 |
INC(b.Pegs.NoOfPegs) ; |
| 462 |
IF c=white |
| 463 |
THEN |
| 464 |
INCL(b.Colours, pos) |
| 465 |
END |
| 466 |
END |
| 467 |
END ApplyMove ; |
| 468 |
|
| 469 |
|
| 470 |
(* |
| 471 |
RetractMove - removes the last move from the board. |
| 472 |
*) |
| 473 |
|
| 474 |
PROCEDURE RetractMove (VAR b: Board) ; |
| 475 |
VAR |
| 476 |
pos: CARDINAL ; |
| 477 |
BEGIN |
| 478 |
IF b.Pegs.NoOfPegs>0 |
| 479 |
THEN |
| 480 |
DEC(b.Pegs.NoOfPegs) ; |
| 481 |
pos := VAL(CARDINAL, b.Pegs.Tiles[b.Pegs.NoOfPegs]) ; |
| 482 |
EXCL(b.Colours, pos) |
| 483 |
END |
| 484 |
END RetractMove ; |
| 485 |
|
| 486 |
|
| 487 |
(* |
| 488 |
AskMove - returns a move entered. |
| 489 |
*) |
| 490 |
|
| 491 |
PROCEDURE AskMove (VAR b: Board; c: Colour) : CARDINAL ; |
| 492 |
VAR |
| 493 |
s : ARRAY [0..80] OF CHAR ; |
| 494 |
x : CHAR ; |
| 495 |
y, m: CARDINAL ; |
| 496 |
BEGIN |
| 497 |
LOOP |
| 498 |
WriteString('Please enter your move, ') ; |
| 499 |
WriteColour(c) ; |
| 500 |
WriteString(': ') ; |
| 501 |
LOOP |
| 502 |
ReadString(s) ; |
| 503 |
StrRemoveWhitePrefix(s, s) ; |
| 504 |
IF StrEqual (s, 'exit') OR StrEqual (s, 'quit') |
| 505 |
THEN |
| 506 |
WriteString ('goodbye') ; WriteLn ; |
| 507 |
HALT (0) |
| 508 |
ELSIF StrLen(s)>0 |
| 509 |
THEN |
| 510 |
x := CAP(s[0]) ; |
| 511 |
IF (x>='A') AND (x<='P') |
| 512 |
THEN |
| 513 |
m := ORD (x) - ORD ('A') ; |
| 514 |
s[0] := ' ' ; |
| 515 |
StrRemoveWhitePrefix(s, s) ; |
| 516 |
IF StrLen(s)>0 |
| 517 |
THEN |
| 518 |
StrToCard(s, y) ; |
| 519 |
IF (y=0) OR (y>BoardY) |
| 520 |
THEN |
| 521 |
WriteString('Please enter a number between [1-16]') ; WriteLn |
| 522 |
ELSE |
| 523 |
m := m+(y-1)*BoardY ; |
| 524 |
EXIT |
| 525 |
END |
| 526 |
END |
| 527 |
ELSE |
| 528 |
WriteString('please enter a letter [A-P] followed by a number [1-16]') ; WriteLn |
| 529 |
END |
| 530 |
END |
| 531 |
END ; |
| 532 |
IF IsPositionEmpty(b, m) |
| 533 |
THEN |
| 534 |
RETURN m |
| 535 |
END ; |
| 536 |
IF IsPositionCol(b, m, c) |
| 537 |
THEN |
| 538 |
WriteString('You have already moved into that position') ; WriteLn |
| 539 |
ELSE |
| 540 |
WriteString('That position is occupied by your opponent') ; WriteLn |
| 541 |
END |
| 542 |
END |
| 543 |
END AskMove ; |
| 544 |
|
| 545 |
|
| 546 |
(* |
| 547 |
Opponent - returns the opposite colour. |
| 548 |
*) |
| 549 |
|
| 550 |
PROCEDURE Opponent (col: Colour) : Colour ; |
| 551 |
BEGIN |
| 552 |
IF col=white |
| 553 |
THEN |
| 554 |
RETURN black |
| 555 |
ELSE |
| 556 |
RETURN white |
| 557 |
END |
| 558 |
END Opponent ; |
| 559 |
|
| 560 |
|
| 561 |
(* |
| 562 |
AlphaBeta - returns the score estimated should move, pos, be chosen. |
| 563 |
The board, b, and score is in the state _before_ move pos |
| 564 |
is made. |
| 565 |
*) |
| 566 |
|
| 567 |
PROCEDURE AlphaBeta (pos: CARDINAL; VAR b: Board; col: Colour; |
| 568 |
depth: CARDINAL; |
| 569 |
alpha, beta, score: INTEGER) : INTEGER ; |
| 570 |
VAR |
| 571 |
try : INTEGER ; |
| 572 |
i, n : CARDINAL ; |
| 573 |
m : Moves ; |
| 574 |
newBoard: Board ; |
| 575 |
BEGIN |
| 576 |
score := CalcScore(b, score, pos, col) ; (* make move and update score *) |
| 577 |
IF (depth=0) OR MaximumScore(score) |
| 578 |
THEN |
| 579 |
RetractMove(b) ; |
| 580 |
INC(count) ; |
| 581 |
IF col=white |
| 582 |
THEN |
| 583 |
RETURN score+VAL(INTEGER, depth) |
| 584 |
ELSE |
| 585 |
RETURN score-VAL(INTEGER, depth) |
| 586 |
END |
| 587 |
ELSE |
| 588 |
col := Opponent(col) ; |
| 589 |
CreateListOfMoves(b, m, col) ; |
| 590 |
i := 0 ; |
| 591 |
IF col=white |
| 592 |
THEN |
| 593 |
WHILE i<m.NoOfPegs DO |
| 594 |
try := AlphaBeta(VAL(CARDINAL, m.Tiles[i]), |
| 595 |
b, white, depth-1, alpha, beta, score) ; |
| 596 |
IF try > alpha |
| 597 |
THEN |
| 598 |
(* found a better move *) |
| 599 |
alpha := try |
| 600 |
END ; |
| 601 |
IF alpha >= beta |
| 602 |
THEN |
| 603 |
RetractMove(b) ; |
| 604 |
RETURN alpha |
| 605 |
END ; |
| 606 |
INC(i) |
| 607 |
END ; |
| 608 |
RetractMove(b) ; |
| 609 |
RETURN alpha |
| 610 |
ELSE |
| 611 |
(* black to move, move is possible, continue searching *) |
| 612 |
WHILE i<m.NoOfPegs DO |
| 613 |
try := AlphaBeta(VAL(CARDINAL, m.Tiles[i]), |
| 614 |
b, black, depth-1, alpha, beta, score) ; |
| 615 |
IF try < beta |
| 616 |
THEN |
| 617 |
(* found a better move *) |
| 618 |
beta := try |
| 619 |
END ; |
| 620 |
IF alpha >= beta |
| 621 |
THEN |
| 622 |
(* no point searching further as WHITE would choose |
| 623 |
a different previous move *) |
| 624 |
RetractMove(b) ; |
| 625 |
RETURN beta |
| 626 |
END ; |
| 627 |
INC(i) |
| 628 |
END ; |
| 629 |
RetractMove(b) ; |
| 630 |
RETURN beta (* the best score for a move BLACK has found *) |
| 631 |
END |
| 632 |
END |
| 633 |
END AlphaBeta ; |
| 634 |
|
| 635 |
|
| 636 |
(* |
| 637 |
MakeMove - computer makes a move for colour, col. |
| 638 |
*) |
| 639 |
|
| 640 |
PROCEDURE MakeMove (VAR b: Board; col: Colour; score: INTEGER) : INTEGER ; |
| 641 |
VAR |
| 642 |
start, end: Timeval ; |
| 643 |
try, |
| 644 |
r, best : INTEGER ; |
| 645 |
secS, usec, |
| 646 |
secE, i, |
| 647 |
move : CARDINAL ; |
| 648 |
m : Moves ; |
| 649 |
BEGIN |
| 650 |
start := InitTime(0, 0) ; |
| 651 |
end := InitTime(0, 0) ; |
| 652 |
|
| 653 |
WriteString("I'm going to look ") ; |
| 654 |
WriteCard(NoOfPlies, 0) ; WriteString(' moves ahead') ; WriteLn ; |
| 655 |
|
| 656 |
r := GetTimeOfDay(start) ; |
| 657 |
best := MinScore-1 ; |
| 658 |
|
| 659 |
count := 0 ; |
| 660 |
i := 0 ; |
| 661 |
CreateListOfMoves(b, m, col) ; |
| 662 |
WHILE i<m.NoOfPegs DO |
| 663 |
try := AlphaBeta(VAL(CARDINAL, m.Tiles[i]), b, col, NoOfPlies, |
| 664 |
MinScore, MaxScore, score) ; |
| 665 |
IF try>best |
| 666 |
THEN |
| 667 |
best := try ; |
| 668 |
move := VAL(CARDINAL, m.Tiles[i]) |
| 669 |
END ; |
| 670 |
INC(i) |
| 671 |
END ; |
| 672 |
|
| 673 |
r := GetTimeOfDay(end) ; |
| 674 |
GetTime(start, secS, usec) ; |
| 675 |
GetTime(end, secE, usec) ; |
| 676 |
|
| 677 |
IF best >= WinScore |
| 678 |
THEN |
| 679 |
WriteString('I think I can force a win') ; WriteLn |
| 680 |
END ; |
| 681 |
IF best <= LooseScore |
| 682 |
THEN |
| 683 |
WriteString('You should be able to force a win') ; WriteLn |
| 684 |
END ; |
| 685 |
|
| 686 |
WriteString('I took ') ; WriteCard(secE-secS, 0) ; |
| 687 |
WriteString(' seconds and evaluated ') ; |
| 688 |
WriteCard(count, 0) ; WriteString(' positions,') ; WriteLn ; |
| 689 |
|
| 690 |
IF secE-secS > MaxTimePerMove |
| 691 |
THEN |
| 692 |
WriteString('sorry about the wait, I took too long so') ; WriteLn ; |
| 693 |
WriteString('I will reduce my search next go..') ; WriteLn ; |
| 694 |
IF NoOfPlies >= 3 |
| 695 |
THEN |
| 696 |
DEC(NoOfPlies) |
| 697 |
END |
| 698 |
ELSE |
| 699 |
IF secE-secS < MinTimePerMove |
| 700 |
THEN |
| 701 |
INC(NoOfPlies) |
| 702 |
END |
| 703 |
END ; |
| 704 |
|
| 705 |
start := KillTime(start) ; |
| 706 |
end := KillTime(end) ; |
| 707 |
RETURN move |
| 708 |
END MakeMove ; |
| 709 |
|
| 710 |
|
| 711 |
(* |
| 712 |
Play - |
| 713 |
*) |
| 714 |
|
| 715 |
PROCEDURE Play ; |
| 716 |
VAR |
| 717 |
b: Board ; |
| 718 |
c: Colour ; |
| 719 |
s: INTEGER ; |
| 720 |
m: CARDINAL ; |
| 721 |
BEGIN |
| 722 |
InitBoard(b) ; |
| 723 |
NoOfPlies := 3 ; |
| 724 |
c := black ; |
| 725 |
s := 0 ; |
| 726 |
DisplayBoard(b) ; |
| 727 |
REPEAT |
| 728 |
m := AskMove(b, c) ; |
| 729 |
s := CalcScore(b, s, m, c) ; |
| 730 |
DisplayBoard(b) ; |
| 731 |
WriteString('Current score = ') ; WriteInt(s, 0) ; WriteLn ; |
| 732 |
FlushBuffer(StdOut) ; |
| 733 |
IF s<=MinScore |
| 734 |
THEN |
| 735 |
WriteString('Well done you win') ; WriteLn ; |
| 736 |
RETURN |
| 737 |
END ; |
| 738 |
c := Opponent(c) ; |
| 739 |
m := MakeMove(b, c, s) ; |
| 740 |
s := CalcScore(b, s, m, c) ; |
| 741 |
|
| 742 |
WriteString('I am going to move to position: ') ; |
| 743 |
Write(CHR(ORD('a')+m MOD BoardY)) ; |
| 744 |
WriteCard(m DIV BoardX+1, 0) ; |
| 745 |
WriteLn ; |
| 746 |
DisplayBoard(b) ; |
| 747 |
WriteString('Current score = ') ; WriteInt(s, 0) ; WriteLn ; |
| 748 |
IF s>=MaxScore |
| 749 |
THEN |
| 750 |
WriteString('Good try, but I win') ; WriteLn ; |
| 751 |
RETURN |
| 752 |
END ; |
| 753 |
c := Opponent(c) |
| 754 |
UNTIL b.Pegs.NoOfPegs=BoardSize ; |
| 755 |
WriteString('The game has ended in a draw as the board is full') ; WriteLn |
| 756 |
END Play ; |
| 757 |
|
| 758 |
|
| 759 |
BEGIN |
| 760 |
IF EnableGame |
| 761 |
THEN |
| 762 |
Play |
| 763 |
ELSE |
| 764 |
WriteString ('to enable the game - edit line 31 in pegfive.mod and recompile') ; |
| 765 |
WriteLn |
| 766 |
END |
| 767 |
END pegfive. |