8x8 Connect 4: AI Challenge

[bplus]

2021-10-18 Update: For Friends at Syntax Bomb attached below is most recent Connect 4 with AI for 8x8 board and source and program compiled for Windows.

Just finished an update of this old classic:

Code: QB64: [Select]

1. OPTION _EXPLICIT
2. _TITLE "Connect 4 8x8: AI challenge" 'b+ 2020-12-14 rewrite
3.  
4. DEFLNG A-Z
5. CONST SQ = 60 '       square or grid cell
6. CONST SW = SQ * 10 '  screen width
7. CONST SH = SQ * 11 '  screen height
8. CONST N = 8 '         number of rows and columns
9. CONST NM1 = N - 1 '   N minus 1
10. CONST P = 1 '       Player is 1 on grid
11. CONST AI = -1 '     AI is -1 on grid
12. CONST XO = SQ '     x offset for grid
13. CONST YO = 2 * SQ ' y offset for grid
14.  
15. REDIM SHARED Grid(NM1, NM1) ' 0 = empty  P=1 for Player,  AI=-1  for AI so -4 is win for AI..
16. REDIM SHARED DX(7), DY(7), WinX, WinY, WinD, GameOn, Turn, AIX, AIY, GoFirst ' if find a win, draw it in ShowGrid
17. DX(0) = 1: DY(0) = 0 ': DString$(0) = "East"
18. DX(1) = 1: DY(1) = 1 ': DString$(1) = "South East"
19. DX(2) = 0: DY(2) = 1 ': DString$(2) = "South"
20. DX(3) = -1: DY(3) = 1 ': DString$(3) = "South West"
21. DX(4) = -1: DY(4) = 0 ': DString$(4) = "West"
22. DX(5) = -1: DY(5) = -1 ': DString$(5) = "North West"
23. DX(6) = 0: DY(6) = -1 ': DString$(6) = "North"
24. DX(7) = 1: DY(7) = -1 ' : DString$(7) = "North East"
25.  
26. SCREEN _NEWIMAGE(SW, SH, 32)
27. _SCREENMOVE 360, 60
28. DIM mb, mx, my, row, col, r
29. GameOn = -1: GoFirst = AI: Turn = AI
30. ShowGrid
31. WHILE GameOn
32.     IF Turn = P THEN
33.         WHILE _MOUSEINPUT: WEND
34.         mb = _MOUSEBUTTON(1): mx = _MOUSEX: my = _MOUSEY
35.         IF mb THEN 'get last place mouse button was down
36.             _DELAY .25 'for mouse release
37.             row = ((my - YO) / SQ - .5): col = ((mx - XO) / SQ - .5)
38.             IF col >= 0 AND col <= NM1 AND row >= 0 AND row < 8 THEN
39.                 r = GetOpenRow(col) 'find next space open on board
40.                 IF r <> N THEN
41.                     Grid(col, r) = P
42.                     Turn = AI
43.                 END IF
44.             ELSE
45.                 BEEP
46.             END IF
47.         END IF
48.     ELSE
49.         AIMove
50.         Turn = P
51.     END IF
52.     ShowGrid
53.     _DISPLAY
54.     _LIMIT 60
55. WEND
56.  
57. SUB AIMove
58.     ' What this sub does in English:
59.     ' This sub assigns the value to playing each column, then plays the best value with following caveats:
60.     ' + If it finds a winning move, it will play that immediately.
61.     ' + If it finds a spoiler move, it will play that if no winning move was found.
62.     ' + It will poisen the column's scoring, if opponent can play a winning move if AI plays this column,
63.     '   but it might be the only legal move left.  We will have to play it if no better score was found.
64.  
65.     DIM c, r, d, cntA, cntP, bestScore, startR, startC, iStep, test, goodF, i
66.     DIM openRow(NM1) ' find open rows once
67.     DIM scores(NM1) ' evaluate each column's potential
68.     AIX = -1: AIY = -1 ' set these when AI makes move, they are signal to display procedure AI's move.
69.     FOR c = 0 TO NM1
70.         openRow(c) = GetOpenRow(c)
71.         r = openRow(c)
72.         IF r <> N THEN
73.             FOR d = 0 TO 3 ' 4 directions to build connect 4's that use cell c, r
74.                 startC = c + -3 * DX(d): startR = r + -3 * DY(d)
75.                 FOR i = 0 TO 3 ' here we backup from the potential connect 4 in opposite build direction of c, r
76.                     cntA = 0: cntP = 0: goodF = -1 ' reset counts and flag for good connect 4
77.                     'from this start position run 4 steps forward to count all connects involving cell c, r
78.                     FOR iStep = 0 TO 3 ' process a potential connect 4
79.                         test = GR(startC + i * DX(d) + iStep * DX(d), startR + i * DY(d) + iStep * DY(d))
80.                         IF test = N THEN goodF = 0: EXIT FOR 'cant get connect4 from here
81.                         IF test = AI THEN cntA = cntA + 1
82.                         IF test = P THEN cntP = cntP + 1
83.                     NEXT iStep
84.                     IF goodF THEN 'evaluate the Legal Connect4 we could build with c, r
85.                         IF cntA = 3 THEN ' we are done!  winner!
86.                             AIX = c: AIY = r ' <<< this is the needed 4th cell to win tell ShowGrid last cell
87.                             Grid(c, r) = AI '  <<< this is the needed 4th cell to win, add to grid this is AI move
88.                             EXIT SUB
89.                         ELSEIF cntP = 3 THEN 'next best move spoiler!
90.                             AIX = c: AIY = r 'set the move but don't exit there might be a winner
91.                         ELSEIF cntA = 0 AND cntP = 2 THEN
92.                             scores(c) = scores(c) + 6
93.                         ELSEIF cntA = 2 AND cntP = 0 THEN ' very good offense or defense
94.                             scores(c) = scores(c) + 5 'play this to connect 3 or prevent player from Connect 3
95.                         ELSEIF cntA = 0 AND cntP = 1 THEN
96.                             scores(c) = scores(c) + 4
97.                         ELSEIF (cntA = 1 AND cntP = 0) OR (cntA = 0 AND cntP = 1) THEN 'good offense or defense
98.                             scores(c) = scores(c) + 3 ' play this to connect 2 or prevent player from Connect 2
99.                         ELSEIF (cntA = 0 AND cntP = 0) THEN ' OK it's not a wasted move as it has potential for connect4
100.                             scores(c) = scores(c) + 1 ' this is good move because this can still be a Connect 4
101.                         END IF
102.                     END IF ' in the board
103.                 NEXT i
104.             NEXT d
105.             IF Stupid(c, r) THEN scores(c) = -1000 + scores(c) ' poison because if played the human can win
106.         END IF
107.     NEXT
108.     IF AIX <> -1 THEN ' we found a spoiler so move there since we haven't found a winner
109.         Grid(AIX, AIY) = AI ' make move on grid and done!
110.         EXIT SUB
111.     ELSE
112.         bestScore = -1000 ' a negative score indicates that the player can beat AI with their next move
113.         FOR c = 0 TO NM1
114.             r = openRow(c)
115.             IF r <> N THEN
116.                 IF scores(c) > bestScore THEN bestScore = scores(c): AIY = r: AIX = c
117.             END IF
118.         NEXT
119.         IF AIX <> -1 THEN
120.             Grid(AIX, AIY) = AI ' make first best score move we found
121.         ELSE 'We have trouble!  Oh but it could be there are no moves!!!
122.             ' checkWin is run after every move by AI or Player if there were no legal moves left it should have caught that.
123.             ' Just in case it didn't here is an error stop!
124.  
125.             'note: LOCATE here is Row, Column the reverse of Just Basic
126.             BEEP: LOCATE 4, 2: PRINT "AI has failed to find a proper move, pess any to end..."
127.             SLEEP ' <<< pause until user presses a key
128.             END
129.         END IF
130.     END IF
131. END SUB
132.  
133. FUNCTION GetOpenRow (forCol)
134.     DIM i
135.     GetOpenRow = N 'assume none open
136.     IF forCol < 0 OR forCol > NM1 THEN EXIT FUNCTION
137.     FOR i = NM1 TO 0 STEP -1
138.         IF Grid(forCol, i) = 0 THEN GetOpenRow = i: EXIT FUNCTION
139.     NEXT
140. END FUNCTION
141.  
142. FUNCTION Stupid (c, r)
143.     DIM pr
144.  
145.     Grid(c, r) = AI
146.     pr = GetOpenRow(c)
147.     IF pr <> N THEN
148.         Grid(c, pr) = P
149.         IF CheckWin = 4 THEN Stupid = -1
150.         Grid(c, pr) = 0
151.     END IF
152.     Grid(c, r) = 0
153. END FUNCTION
154.  
155. FUNCTION GR (c, r) ' if c, r are out of bounds returns N else returns grid(c, r)
156.     ' need to check the grid(c, r) but only if c, r is on the board
157.     IF c < 0 OR c > NM1 OR r < 0 OR r > NM1 THEN GR = N ELSE GR = Grid(c, r)
158. END FUNCTION
159.  
160. SUB ShowGrid
161.     DIM i, r, c, check, s$, y$
162.     CLS
163.     FOR i = 0 TO N 'grid
164.         LINE (SQ * i + XO, YO)-STEP(0, N * SQ), &HFF00FF00
165.         LINE (XO, SQ * i + YO)-STEP(N * SQ, 0), &HFF00FF00
166.     NEXT
167.     FOR r = NM1 TO 0 STEP -1 'plays
168.         FOR c = 0 TO NM1
169.             'in grid rows are reversed 0 is top row
170.             IF Grid(c, r) = P THEN
171.                 LINE (c * SQ + XO + 3, r * SQ + YO + 3)-STEP(SQ - 6, SQ - 6), &HFFFF0000, BF
172.             ELSEIF Grid(c, r) = AI THEN
173.                 IF c = AIX AND r = AIY THEN 'highlite last AI move
174.                     LINE (c * SQ + XO + 3, r * SQ + YO + 3)-STEP(SQ - 6, SQ - 6), &HFF5555FF, BF
175.                 ELSE
176.                     LINE (c * SQ + XO + 3, r * SQ + YO + 3)-STEP(SQ - 6, SQ - 6), &HFF0000FF, BF
177.                 END IF
178.             END IF
179.         NEXT
180.     NEXT
181.     _DISPLAY
182.     check = CheckWin
183.     IF check THEN 'report end of round ad see if want to play again
184.         IF check = 4 OR check = -4 THEN
185.             FOR i = 0 TO 3
186.                 LINE ((WinX + i * DX(WinD)) * SQ + XO + 5, (WinY + i * DY(WinD)) * SQ + YO + 5)-STEP(SQ - 10, SQ - 10), &HFFFFFFFF, B
187.             NEXT
188.         END IF
189.         IF check = -4 THEN
190.             s$ = "AI is Winner!"
191.         ELSEIF check = 4 THEN
192.             s$ = "Human is Winner!"
193.         ELSEIF check = N THEN
194.             s$ = "Board is full, no winner." ' keep Turn the same
195.         END IF
196.         LOCATE 2, 2: PRINT s$
197.         _DISPLAY
198.         LOCATE 4, 2: INPUT "Play again? just press enter quit with any other ", y$
199.         IF y$ = "" THEN
200.             REDIM Grid(NM1, NM1)
201.             IF GoFirst = P THEN GoFirst = AI ELSE GoFirst = P
202.             Turn = GoFirst
203.         ELSE
204.             GameOn = 0
205.         END IF
206.     END IF
207. END SUB
208.  
209. FUNCTION CheckWin
210.     DIM gridFull, r, c, s, i
211.     ' return WinX, WinY, WinD along with +/- score, returns N  if grid full, 0 if no win and grid not full
212.     gridFull = N
213.     FOR r = NM1 TO 0 STEP -1 'bottom to top
214.         FOR c = 0 TO NM1
215.             IF Grid(c, r) THEN 'check if c starts a row
216.                 IF c < NM1 - 2 THEN
217.                     s = 0
218.                     FOR i = 0 TO 3
219.                         s = s + Grid(c + i, r)
220.                     NEXT
221.                     IF s = 4 OR s = -4 THEN
222.                         WinX = c: WinY = r: WinD = 0
223.                         CheckWin = s: EXIT FUNCTION
224.                     END IF
225.                 END IF
226.                 IF r > 2 THEN 'check if c starts a col
227.                     s = 0
228.                     FOR i = 0 TO 3
229.                         s = s + Grid(c, r - i)
230.                     NEXT
231.                     IF s = 4 OR s = -4 THEN
232.                         WinX = c: WinY = r: WinD = 6 'north
233.                         CheckWin = s: EXIT FUNCTION
234.                     END IF
235.                 END IF
236.                 IF r > 2 AND c < NM1 - 2 THEN 'check if c starts diagonal up to right
237.                     s = 0
238.                     FOR i = 0 TO 3
239.                         s = s + Grid(c + i, r - i)
240.                     NEXT
241.                     IF s = 4 OR s = -4 THEN ' north  east
242.                         WinX = c: WinY = r: WinD = 7
243.                         CheckWin = s: EXIT FUNCTION
244.                     END IF
245.                 END IF
246.                 IF r > 2 AND c > 2 THEN 'check if c starts a diagonal up to left
247.                     s = 0
248.                     FOR i = 0 TO 3
249.                         s = s + Grid(c - i, r - i)
250.                     NEXT
251.                     IF s = 4 OR s = -4 THEN ' north west
252.                         WinX = c: WinY = r: WinD = 5
253.                         CheckWin = s: EXIT FUNCTION
254.                     END IF
255.                 END IF
256.             ELSE
257.                 gridFull = 0 ' at least one enpty cell left
258.             END IF 'grid is something
259.         NEXT
260.     NEXT
261.     CheckWin = gridFull
262. END FUNCTION
263.  

EDIT: oops, still clearing remnants of old code. Again, don't need debug stuff anymore either.

So far, I've only been able to tie the AI.

[NOVARSEG]

Sometime when I click on a square a different square goes red

[bplus]

Sometime when I click on a square a different square goes red

Interesting, when I switched from Single default to DEFLNG A-Z, I had to adjust line 37 by adding in the .5's, maybe your system doesn't need that?

[segura]

Sometime when I click on a square a different square goes red

Maybe you are having some resolution problem?

[Dav]

Nice.  Plays pretty strong!  I haven't won yet (but I even have a hard time with tic-tac-toe sometimes). Lol at Stupid FUNCTION name. 

- Dav

[bplus]

Welcome to the forum segura!

Nice.  Plays pretty strong!  I haven't won yet (but I even have a hard time with tic-tac-toe sometimes). Lol at Stupid FUNCTION name. 

- Dav

Thanks Dav, I haven't beaten it yet either. I was beating it regularly with one little trick then tweaked the scoring system to play more defensive by raising the scoring of such plays. I've tied it once :)

[SpriggsySpriggs]

Good job, @bplus

I cannot beat the AI. I tried several times and just couldn't do it. I'd get so close to winning and then suddenly I've lost. Excellent. Now we need @Ashish to make it in OpenGL so we can have 3D game pieces fall through the board.

[bplus]

Thanks Spriggsy,

so we can have 3D game pieces fall through the board

LOL, how about a button to blow up the board? If the AI is that good, one might be in the mood! ;-))

[SierraKen]

LOL there is no way to win this game! LOL Because as long as the computer plays first, he has the upper hand.

[bplus]

LOL there is no way to win this game! LOL Because as long as the computer plays first, he has the upper hand.

Well it has been proved mathematically a 7x6 can only be won by first player if both play perfect!

That is why I have 8x8, it hasn't been proven for that, that I've heard, but haven't checked recently.

Also the game alternates who goes first, AI starts first because I was testing and editing code for it ALLOT! but you get your chance to go first every other Turn, and you know you have the source code so you CAN go first always! You CAN win always ;-)) but what's the fun in fixing the system?

[SierraKen]

LOL OK. :)

[Dav]

I've enjoyed the challenge of this game.  Haven't won yet.  I was about to put my name in the Stupid function and quit, but played 1 more and reached a tie game.  So I'll keep trying....

- Dav

[bplus]

I've enjoyed the challenge of this game.  Haven't won yet.  I was about to put my name in the Stupid function and quit, but played 1 more and reached a tie game.  So I'll keep trying....

- Dav

I am thinking of a reward but I would need a screen shot and list of moves that I should be able replicate (no RND function was used in this code). Yeah I am talking serious prize, maybe donation to your favorite charity, 'tis the season after all! ;-))

[STxAxTIC]

took two tries. computer went first

[STxAxTIC]

another one