119 lines
3.4 KiB
QBasic
119 lines
3.4 KiB
QBasic
|
1 REM Tic Tac Toe solving app that learns what WOPR learned: you can't win
|
||
|
|
2 REM Only three starting positions are examined. Others are just reflections of these
|
||
|
|
3 REM b% -- The board
|
||
|
|
4 REM al% -- Alpha, for pruning
|
||
|
|
5 REM be% -- Beta, for pruning
|
||
|
|
6 REM l% -- Top-level loop iteration
|
||
|
|
7 REM wi% -- The winning piece (0 none, 1 X, 2, O )
|
||
|
|
8 REM re% -- Resulting score of 4000/minmax board position. 5 draw, 6 X win, 4 Y win
|
||
|
|
9 REM sx% -- Stack array for "recursion" X can be P, V, A, or B for those variables.
|
||
|
|
10 REM v% -- Value of a board position
|
||
|
|
11 REM st% -- Stack Pointer. Even for alpha/beta pruning Minimize plys, Odd for Maximize
|
||
|
|
12 REM p% -- Current position where a new piece is played
|
||
|
|
14 REM rw% -- Row in the Winner function (2000)
|
||
|
|
15 REM cw% -- Column in the Winner function (2000)
|
||
|
|
18 REM mc% -- Move count total for debugging. Should be a multiple of 6493
|
||
|
|
19 REM Note: Can't use real recursion with GOSUB because stack is limited to roughly 5 deep
|
||
|
|
20 REM BASIC doesn't support goto/gosub using arrays for target line numbers
|
||
|
|
30 DIM b%(9)
|
||
|
|
32 DIM sp%(10)
|
||
|
|
34 DIM sv%(10)
|
||
|
|
36 DIM sa%(10)
|
||
|
|
37 DIM sb%(10)
|
||
|
|
38 mc% = 0
|
||
|
|
39 PRINT "start time: "; TIME$
|
||
|
|
40 FOR l% = 1 TO 100
|
||
|
|
41 mc% = 0
|
||
|
|
42 al% = 2
|
||
|
|
43 be% = 9
|
||
|
|
44 b%(0) = 1
|
||
|
|
45 GOSUB 4000
|
||
|
|
58 al% = 2
|
||
|
|
59 be% = 9
|
||
|
|
60 b%(0) = 0
|
||
|
|
61 b%(1) = 1
|
||
|
|
62 GOSUB 4000
|
||
|
|
68 al% = 2
|
||
|
|
69 be% = 9
|
||
|
|
70 b%(1) = 0
|
||
|
|
71 b%(4) = 1
|
||
|
|
72 GOSUB 4000
|
||
|
|
73 b%(4) = 0
|
||
|
|
74 REM print "mc: "; mc%; " l is "; l%
|
||
|
|
80 NEXT l%
|
||
|
|
85 PRINT "for "; l% - 1; " iterations"
|
||
|
|
86 PRINT "end time: "; TIME$
|
||
|
|
87 PRINT "final move count "; mc%
|
||
|
|
88 SYSTEM
|
||
|
|
100 END
|
||
|
|
|
||
|
|
2000 wi% = b%(0)
|
||
|
|
2010 IF 0 = wi% GOTO 2100
|
||
|
|
2020 IF wi% = b%(1) AND wi% = b%(2) THEN RETURN
|
||
|
|
2030 IF wi% = b%(3) AND wi% = b%(6) THEN RETURN
|
||
|
|
2100 wi% = b%(3)
|
||
|
|
2110 IF 0 = wi% GOTO 2200
|
||
|
|
2120 IF wi% = b%(4) AND wi% = b%(5) THEN RETURN
|
||
|
|
2200 wi% = b%(6)
|
||
|
|
2210 IF 0 = wi% GOTO 2300
|
||
|
|
2220 IF wi% = b%(7) AND wi% = b%(8) THEN RETURN
|
||
|
|
2300 wi% = b%(1)
|
||
|
|
2310 IF 0 = wi% GOTO 2400
|
||
|
|
2320 IF wi% = b%(4) AND wi% = b%(7) THEN RETURN
|
||
|
|
2400 wi% = b%(2)
|
||
|
|
2410 IF 0 = wi% GOTO 2500
|
||
|
|
2420 IF wi% = b%(5) AND wi% = b%(8) THEN RETURN
|
||
|
|
2500 wi% = b%(4)
|
||
|
|
2510 IF 0 = wi% THEN RETURN
|
||
|
|
2520 IF wi% = b%(0) AND wi% = b%(8) THEN RETURN
|
||
|
|
2530 IF wi% = b%(2) AND wi% = b%(6) THEN RETURN
|
||
|
|
2540 wi% = 0
|
||
|
|
2550 RETURN
|
||
|
|
|
||
|
|
4000 REM minmax function to find score of a board position
|
||
|
|
4010 REM recursion is simulated with gotos
|
||
|
|
4030 st% = 0
|
||
|
|
4040 v% = 0
|
||
|
|
4060 re% = 0
|
||
|
|
4100 mc% = mc% + 1
|
||
|
|
4102 REM gosub 3000
|
||
|
|
4104 IF st% < 4 THEN GOTO 4150
|
||
|
|
4105 GOSUB 2000
|
||
|
|
4106 IF 0 = wi% THEN GOTO 4140
|
||
|
|
4110 IF wi% = 1 THEN re% = 6: GOTO 4280
|
||
|
|
4115 re% = 4
|
||
|
|
4116 GOTO 4280
|
||
|
|
4140 IF st% = 8 THEN re% = 5: GOTO 4280
|
||
|
|
4150 IF st% AND 1 THEN v% = 2 ELSE v% = 9
|
||
|
|
4160 p% = 0
|
||
|
|
4180 IF 0 <> b%(p%) THEN GOTO 4500
|
||
|
|
4200 IF st% AND 1 THEN b%(p%) = 1 ELSE b%(p%) = 2
|
||
|
|
4210 sp%(st%) = p%
|
||
|
|
4230 sv%(st%) = v%
|
||
|
|
4245 sa%(st%) = al%
|
||
|
|
4246 sb%(st%) = be%
|
||
|
|
4260 st% = st% + 1
|
||
|
|
4270 GOTO 4100
|
||
|
|
4280 st% = st% - 1
|
||
|
|
4290 p% = sp%(st%)
|
||
|
|
4310 v% = sv%(st%)
|
||
|
|
4325 al% = sa%(st%)
|
||
|
|
4326 be% = sb%(st%)
|
||
|
|
4328 b%(p%) = 0
|
||
|
|
4330 IF st% AND 1 THEN GOTO 4340
|
||
|
|
4331 IF re% = 4 THEN GOTO 4530
|
||
|
|
4332 IF re% < v% THEN v% = re%
|
||
|
|
4334 IF v% < be% THEN be% = v%
|
||
|
|
4336 IF be% <= al% THEN GOTO 4520
|
||
|
|
4338 GOTO 4500
|
||
|
|
4340 IF re% = 6 THEN GOTO 4530
|
||
|
|
4341 IF re% > v% THEN v% = re%
|
||
|
|
4342 IF v% > al% THEN al% = v%
|
||
|
|
4344 IF al% >= be% THEN GOTO 4520
|
||
|
|
4500 p% = p% + 1
|
||
|
|
4505 IF p% < 9 THEN GOTO 4180
|
||
|
|
4520 re% = v%
|
||
|
|
4530 IF st% = 0 THEN RETURN
|
||
|
|
4540 GOTO 4280
|
||
|
|
|