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

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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]
OPTION _EXPLICIT
_TITLE "Connect 4 8x8: AI challenge" 'b+ 2020-12-14 rewrite

DEFLNG A-Z
CONST SQ = 60 '       square or grid cell
CONST SW = SQ * 10 '  screen width
CONST SH = SQ * 11 '  screen height
CONST N = 8 '         number of rows and columns
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"

SCREEN _NEWIMAGE(SW, SH, 32)
_SCREENMOVE 360, 60
DIM mb, mx, my, row, col, r
GameOn = -1: GoFirst = AI: Turn = AI
ShowGrid
WHILE GameOn
    IF Turn = P THEN
        WHILE _MOUSEINPUT: WEND
        mb = _MOUSEBUTTON(1): mx = _MOUSEX: my = _MOUSEY
        IF mb THEN 'get last place mouse button was down
            _DELAY .25 'for mouse release
            row = ((my - YO) / SQ - .5): col = ((mx - XO) / SQ - .5)
            IF col >= 0 AND col <= NM1 AND row >= 0 AND row < 8 THEN
                r = GetOpenRow(col) 'find next space open on board
                IF r <> N THEN
                    Grid(col, r) = P
                    Turn = AI
                END IF
            ELSE
                BEEP
            END IF
        END IF
    ELSE
        AIMove
        Turn = P
    END IF
    ShowGrid
    _DISPLAY
    _LIMIT 60
WEND

SUB AIMove
    ' 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.
    FOR c = 0 TO NM1
        openRow(c) = GetOpenRow(c)
        r = openRow(c)
        IF r <> N THEN
            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
                    NEXT iStep
                    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
                            EXIT SUB
                        ELSEIF cntP = 3 THEN 'next best move spoiler!
                            AIX = c: AIY = r 'set the move but don't exit there might be a winner
                        ELSEIF cntA = 0 AND cntP = 2 THEN
                            scores(c) = scores(c) + 6
                        ELSEIF cntA = 2 AND cntP = 0 THEN ' very good offense or defense
                            scores(c) = scores(c) + 5 'play this to connect 3 or prevent player from Connect 3
                        ELSEIF cntA = 0 AND cntP = 1 THEN
                            scores(c) = scores(c) + 4
                        ELSEIF (cntA = 1 AND cntP = 0) OR (cntA = 0 AND cntP = 1) THEN 'good offense or defense
                            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
                        END IF
                    END IF ' in the board
                NEXT i
            NEXT d
            IF Stupid(c, r) THEN scores(c) = -1000 + scores(c) ' poison because if played the human can win
        END IF
    NEXT
    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!
        EXIT SUB
    ELSE
        bestScore = -1000 ' a negative score indicates that the player can beat AI with their next move
        FOR c = 0 TO NM1
            r = openRow(c)
            IF r <> N THEN
                IF scores(c) > bestScore THEN bestScore = scores(c): AIY = r: AIX = c
            END IF
        NEXT
        IF AIX <> -1 THEN
            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
            END
        END IF
    END IF
END SUB

FUNCTION GetOpenRow (forCol)
    DIM i
    GetOpenRow = N 'assume none open
    IF forCol < 0 OR forCol > NM1 THEN EXIT FUNCTION
    FOR i = NM1 TO 0 STEP -1
        IF Grid(forCol, i) = 0 THEN GetOpenRow = i: EXIT FUNCTION
    NEXT
END FUNCTION

FUNCTION Stupid (c, r)
    DIM pr

    Grid(c, r) = AI
    pr = GetOpenRow(c)
    IF pr <> N THEN
        Grid(c, pr) = P
        IF CheckWin = 4 THEN Stupid = -1
        Grid(c, pr) = 0
    END IF
    Grid(c, r) = 0
END FUNCTION

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
    IF c < 0 OR c > NM1 OR r < 0 OR r > NM1 THEN GR = N ELSE GR = Grid(c, r)
END FUNCTION

SUB ShowGrid
    DIM i, r, c, check, s$, y$
    CLS
    FOR i = 0 TO N 'grid
        LINE (SQ * i + XO, YO)-STEP(0, N * SQ), &HFF00FF00
        LINE (XO, SQ * i + YO)-STEP(N * SQ, 0), &HFF00FF00
    NEXT
    FOR r = NM1 TO 0 STEP -1 'plays
        FOR c = 0 TO NM1
            'in grid rows are reversed 0 is top row
            IF Grid(c, r) = P THEN
                LINE (c * SQ + XO + 3, r * SQ + YO + 3)-STEP(SQ - 6, SQ - 6), &HFFFF0000, BF
            ELSEIF Grid(c, r) = AI THEN
                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
                ELSE
                    LINE (c * SQ + XO + 3, r * SQ + YO + 3)-STEP(SQ - 6, SQ - 6), &HFF0000FF, BF
                END IF
            END IF
        NEXT
    NEXT
    _DISPLAY
    check = CheckWin
    IF check THEN 'report end of round ad see if want to play again
        IF check = 4 OR check = -4 THEN
            FOR i = 0 TO 3
                LINE ((WinX + i * DX(WinD)) * SQ + XO + 5, (WinY + i * DY(WinD)) * SQ + YO + 5)-STEP(SQ - 10, SQ - 10), &HFFFFFFFF, B
            NEXT
        END IF
        IF check = -4 THEN
            s$ = "AI is Winner!"
        ELSEIF check = 4 THEN
            s$ = "Human is Winner!"
        ELSEIF check = N THEN
            s$ = "Board is full, no winner." ' keep Turn the same
        END IF
        LOCATE 2, 2: PRINT s$
        _DISPLAY
        LOCATE 4, 2: INPUT "Play again? just press enter quit with any other ", y$
        IF y$ = "" THEN
            REDIM Grid(NM1, NM1)
            IF GoFirst = P THEN GoFirst = AI ELSE GoFirst = P
            Turn = GoFirst
        ELSE
            GameOn = 0
        END IF
    END IF
END SUB

FUNCTION CheckWin
    DIM gridFull, r, c, s, i
    ' return WinX, WinY, WinD along with +/- score, returns N  if grid full, 0 if no win and grid not full
    gridFull = N
    FOR r = NM1 TO 0 STEP -1 'bottom to top
        FOR c = 0 TO NM1
            IF Grid(c, r) THEN 'check if c starts a row
                IF c < NM1 - 2 THEN
                    s = 0
                    FOR i = 0 TO 3
                        s = s + Grid(c + i, r)
                    NEXT
                    IF s = 4 OR s = -4 THEN
                        WinX = c: WinY = r: WinD = 0
                        CheckWin = s: EXIT FUNCTION
                    END IF
                END IF
                IF r > 2 THEN 'check if c starts a col
                    s = 0
                    FOR i = 0 TO 3
                        s = s + Grid(c, r - i)
                    NEXT
                    IF s = 4 OR s = -4 THEN
                        WinX = c: WinY = r: WinD = 6 'north
                        CheckWin = s: EXIT FUNCTION
                    END IF
                END IF
                IF r > 2 AND c < NM1 - 2 THEN 'check if c starts diagonal up to right
                    s = 0
                    FOR i = 0 TO 3
                        s = s + Grid(c + i, r - i)
                    NEXT
                    IF s = 4 OR s = -4 THEN ' north  east
                        WinX = c: WinY = r: WinD = 7
                        CheckWin = s: EXIT FUNCTION
                    END IF
                END IF
                IF r > 2 AND c > 2 THEN 'check if c starts a diagonal up to left
                    s = 0
                    FOR i = 0 TO 3
                        s = s + Grid(c - i, r - i)
                    NEXT
                    IF s = 4 OR s = -4 THEN ' north west
                        WinX = c: WinY = r: WinD = 5
                        CheckWin = s: EXIT FUNCTION
                    END IF
                END IF
            ELSE
                gridFull = 0 ' at least one enpty cell left
            END IF 'grid is something
        NEXT
    NEXT
    CheckWin = gridFull
END FUNCTION

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.
« Last Edit: October 18, 2021, 11:56:37 am by bplus »

Offline NOVARSEG

  • Forum Resident
  • Posts: 510
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

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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
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: 771
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

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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: 1125
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.

Offline bplus

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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: 1328
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

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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: 1328
Re: 8x8 Connect 4: AI Challenge
« Reply #10 on: December 14, 2020, 04:06:12 pm »
LOL OK. :)

Offline Dav

  • Forum Resident
  • Posts: 771
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

  • Forum Resident
  • Posts: 7602
  • b = b + ...
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: 1065
  • I am the absolute center of an ass.
Re: 8x8 Connect 4: AI Challenge
« Reply #13 on: December 14, 2020, 05:36:45 pm »
took two tries. computer went first
ss.png
You're not done when it works, you're done when it's right.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1065
  • I am the absolute center of an ass.
Re: 8x8 Connect 4: AI Challenge
« Reply #14 on: December 14, 2020, 05:40:11 pm »
another one
ss2.png
You're not done when it works, you're done when it's right.