_TITLE "Connect 4 8x8: AI challenge" 'b+ 2020-12-14 rewrite
CONST SQ
= 60 ' square or grid cell CONST N
= 7 ' number of rows and columns CONST SW
= SQ
* (N
+ 2) ' screen width CONST SH
= SQ
* (N
+ 3) ' screen height CONST NM1
= N
- 1 ' N minus 1 CONST P
= 1 ' Player is 1 on grid CONST AI
= -1 ' AI is -1 on grid CONST XO
= SQ
' x offset for grid CONST YO
= 2 * SQ
' y offset for grid
REDIM SHARED Grid
(NM1
, NM1
) ' 0 = empty P=1 for Player, AI=-1 for AI so -4 is win for AI.. REDIM SHARED DX
(7), DY
(7), WinX
, WinY
, WinD
, GameOn
, Turn
, AIX
, AIY
, GoFirst
' if find a win, draw it in ShowGrid DX(0) = 1: DY(0) = 0 ': DString$(0) = "East"
DX(1) = 1: DY(1) = 1 ': DString$(1) = "South East"
DX(2) = 0: DY(2) = 1 ': DString$(2) = "South"
DX(3) = -1: DY(3) = 1 ': DString$(3) = "South West"
DX(4) = -1: DY(4) = 0 ': DString$(4) = "West"
DX(5) = -1: DY(5) = -1 ': DString$(5) = "North West"
DX(6) = 0: DY(6) = -1 ': DString$(6) = "North"
DX(7) = 1: DY(7) = -1 ' : DString$(7) = "North East"
DIM mb
, mx
, my
, row
, col
, r
GameOn = -1: GoFirst = AI: Turn = AI
ShowGrid
IF mb
THEN 'get last place mouse button was down row = ((my - YO) / SQ - .5): col = ((mx - XO) / SQ - .5)
r = GetOpenRow(col) 'find next space open on board
Grid(col, r) = P
Turn = AI
AIMove
Turn = P
ShowGrid
' What this sub does in English:
' This sub assigns the value to playing each column, then plays the best value with following caveats:
' + If it finds a winning move, it will play that immediately.
' + If it finds a spoiler move, it will play that if no winning move was found.
' + It will poisen the column's scoring, if opponent can play a winning move if AI plays this column,
' but it might be the only legal move left. We will have to play it if no better score was found.
DIM c
, r
, d
, cntA
, cntP
, bestScore
, startR
, startC
, iStep
, test
, goodF
, i
DIM openRow
(NM1
) ' find open rows once DIM scores
(NM1
) ' evaluate each column's potential AIX = -1: AIY = -1 ' set these when AI makes move, they are signal to display procedure AI's move.
openRow(c) = GetOpenRow(c)
r = openRow(c)
FOR d
= 0 TO 3 ' 4 directions to build connect 4's that use cell c, r startC = c + -3 * DX(d): startR = r + -3 * DY(d)
FOR i
= 0 TO 3 ' here we backup from the potential connect 4 in opposite build direction of c, r cntA = 0: cntP = 0: goodF = -1 ' reset counts and flag for good connect 4
'from this start position run 4 steps forward to count all connects involving cell c, r
FOR iStep
= 0 TO 3 ' process a potential connect 4 test = GR(startC + i * DX(d) + iStep * DX(d), startR + i * DY(d) + iStep * DY(d))
IF test
= N
THEN goodF
= 0:
EXIT FOR 'cant get connect4 from here IF test
= AI
THEN cntA
= cntA
+ 1 IF test
= P
THEN cntP
= cntP
+ 1 IF goodF
THEN 'evaluate the Legal Connect4 we could build with c, r IF cntA
= 3 THEN ' we are done! winner! AIX = c: AIY = r ' <<< this is the needed 4th cell to win tell ShowGrid last cell
Grid(c, r) = AI ' <<< this is the needed 4th cell to win, add to grid this is AI move
AIX = c: AIY = r 'set the move but don't exit there might be a winner
scores(c) = scores(c) + 6
scores(c) = scores(c) + 5 'play this to connect 3 or prevent player from Connect 3
scores(c) = scores(c) + 4
scores(c) = scores(c) + 3 ' play this to connect 2 or prevent player from Connect 2
ELSEIF (cntA
= 0 AND cntP
= 0) THEN ' OK it's not a wasted move as it has potential for connect4 scores(c) = scores(c) + 1 ' this is good move because this can still be a Connect 4
IF Stupid
(c
, r
) THEN scores
(c
) = -1000 + scores
(c
) ' poison because if played the human can win IF AIX
<> -1 THEN ' we found a spoiler so move there since we haven't found a winner Grid(AIX, AIY) = AI ' make move on grid and done!
bestScore = -1000 ' a negative score indicates that the player can beat AI with their next move
r = openRow(c)
IF scores
(c
) > bestScore
THEN bestScore
= scores
(c
): AIY
= r: AIX
= c
Grid(AIX, AIY) = AI ' make first best score move we found
ELSE 'We have trouble! Oh but it could be there are no moves!!! ' checkWin is run after every move by AI or Player if there were no legal moves left it should have caught that.
' Just in case it didn't here is an error stop!
'note: LOCATE here is Row, Column the reverse of Just Basic
BEEP:
LOCATE 4, 2:
PRINT "AI has failed to find a proper move, pess any to end..." SLEEP ' <<< pause until user presses a key
GetOpenRow = N 'assume none open
Grid(c, r) = AI
pr = GetOpenRow(c)
Grid(c, pr) = P
IF CheckWin
= 4 THEN Stupid
= -1 Grid(c, pr) = 0
Grid(c, r) = 0
FUNCTION GR
(c
, r
) ' if c, r are out of bounds returns N else returns grid(c, r) ' need to check the grid(c, r) but only if c, r is on the board
DIM i
, r
, c
, check
, s$
, y$
LINE (SQ
* i
+ XO
, YO
)-STEP(0, N
* SQ
), &HFF00FF00 LINE (XO
, SQ
* i
+ YO
)-STEP(N
* SQ
, 0), &HFF00FF00 'in grid rows are reversed 0 is top row
LINE (c
* SQ
+ XO
+ 3, r
* SQ
+ YO
+ 3)-STEP(SQ
- 6, SQ
- 6), &HFFFF0000, BF
IF c
= AIX
AND r
= AIY
THEN 'highlite last AI move LINE (c
* SQ
+ XO
+ 3, r
* SQ
+ YO
+ 3)-STEP(SQ
- 6, SQ
- 6), &HFF5555FF, BF
LINE (c
* SQ
+ XO
+ 3, r
* SQ
+ YO
+ 3)-STEP(SQ
- 6, SQ
- 6), &HFF0000FF, BF
check = CheckWin
IF check
THEN 'report end of round ad see if want to play again LINE ((WinX
+ i
* DX
(WinD
)) * SQ
+ XO
+ 5, (WinY
+ i
* DY
(WinD
)) * SQ
+ YO
+ 5)-STEP(SQ
- 10, SQ
- 10), &HFFFFFFFF, B
s$ = "AI is Winner!"
s$ = "Human is Winner!"
s$ = "Board is full, no winner." ' keep Turn the same
LOCATE 4, 2:
INPUT "Play again? just press enter quit with any other ", y$
Turn = GoFirst
GameOn = 0
' return WinX, WinY, WinD along with +/- score, returns N if grid full, 0 if no win and grid not full
gridFull = N
IF Grid
(c
, r
) THEN 'check if c starts a row s = 0
s = s + Grid(c + i, r)
WinX = c: WinY = r: WinD = 0
IF r
> 2 THEN 'check if c starts a col s = 0
s = s + Grid(c, r - i)
WinX = c: WinY = r: WinD = 6 'north
IF r
> 2 AND c
< NM1
- 2 THEN 'check if c starts diagonal up to right s = 0
s = s + Grid(c + i, r - i)
WinX = c: WinY = r: WinD = 7
IF r
> 2 AND c
> 2 THEN 'check if c starts a diagonal up to left s = 0
s = s + Grid(c - i, r - i)
WinX = c: WinY = r: WinD = 5
gridFull = 0 ' at least one enpty cell left
END IF 'grid is something CheckWin = gridFull