Author Topic: 8x8 Connect 4: AI Challenge  (Read 9307 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

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

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.
First Tie.PNG
* First Tie.PNG (Filesize: 18.33 KB, Dimensions: 604x688, Views: 241)
* Connect 4 (8x8) v2020-12-16.zip (Filesize: 822.95 KB, Downloads: 160)
« Last Edit: October 18, 2021, 11:56:37 am by bplus »

Offline NOVARSEG

  • Forum Resident
  • Posts: 509
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #1 on: December 14, 2020, 01:18:18 am »
Sometime when I click on a square a different square goes red

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #2 on: December 14, 2020, 01:23:52 am »
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?

Offline segura

  • Newbie
  • Posts: 3
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #3 on: December 14, 2020, 05:23:51 am »
Sometime when I click on a square a different square goes red
Maybe you are having some resolution problem?

Offline Dav

  • Forum Resident
  • Posts: 792
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #4 on: December 14, 2020, 08:41:43 am »
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

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #5 on: December 14, 2020, 10:02:43 am »
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 :)

Offline SpriggsySpriggs

  • Forum Resident
  • Posts: 1145
  • Larger than life
    • View Profile
    • GitHub
Re: 8x8 Connect 4: AI Challenge
« Reply #6 on: December 14, 2020, 10:41:12 am »
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.
Shuwatch!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #7 on: December 14, 2020, 11:14:00 am »
Thanks Spriggsy,

Quote
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! ;-))

Offline SierraKen

  • Forum Resident
  • Posts: 1454
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #8 on: December 14, 2020, 12:58:05 pm »
LOL there is no way to win this game! LOL Because as long as the computer plays first, he has the upper hand.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #9 on: December 14, 2020, 03:45:16 pm »
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?
« Last Edit: December 14, 2020, 03:46:24 pm by bplus »

Offline SierraKen

  • Forum Resident
  • Posts: 1454
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #10 on: December 14, 2020, 04:06:12 pm »
LOL OK. :)

Offline Dav

  • Forum Resident
  • Posts: 792
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #11 on: December 14, 2020, 04:23:31 pm »
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

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #12 on: December 14, 2020, 04:46:56 pm »
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! ;-))

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #13 on: December 14, 2020, 05:36:45 pm »
took two tries. computer went first
ss.png
* ss.png (Filesize: 13.46 KB, Dimensions: 605x688, Views: 216)
You're not done when it works, you're done when it's right.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: 8x8 Connect 4: AI Challenge
« Reply #14 on: December 14, 2020, 05:40:11 pm »
another one
ss2.png
* ss2.png (Filesize: 13.78 KB, Dimensions: 603x686, Views: 206)
You're not done when it works, you're done when it's right.