Debian Codegraph @

gcc/testsuite/gm2/projects/pim/run/pass/pegfive/pegfive.mod

raw
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.