Yet Another Connect Four

Game development specific discussions.
badidea
Posts: 1999
Joined: May 24, 2007 22:10
Location: The Netherlands

Yet Another Connect Four

Postby badidea » May 21, 2020 23:13

I put my miner game on hold for now, and work on a series of smaller games. Today "Connect Four" or "Four in a Row".
It has been done before, see: Velena (Four-in-a-row)
My version:

Code: Select all

#include "fbgfx.bi"

'-------------------------------------------------------------------------------

type int2d
   as integer x, y
   declare constructor
   declare constructor(x as integer, y as integer)
end type

constructor int2d
end constructor

constructor int2d(x as integer, y as integer)
   this.x = x : this.y = y
end constructor

operator + (a as int2d, b as int2d) as int2d
   return type(a.x + b.x, a.y + b.y)
end operator

operator - (a as int2d, b as int2d) as int2d
   return type(a.x - b.x, a.y - b.y)
end operator

operator * (a as int2d, mul as integer) as int2d
   return type(a.x * mul, a.y * mul)
end operator

operator \ (a as int2d, divider as integer) as int2d
   return type(a.x \ divider, a.y \ divider)
end operator

'-------------------------------------------------------------------------------

#define MIN(a, b) iif((a) < (b), (a), (b))
#define MAX(a, b) iif((a) > (b), (a), (b))

const as string KEY_LE = chr(255, 75) 'K
const as string KEY_RI = chr(255, 77) 'M
const as string KEY_ESC = chr(27)
const as string KEY_SPACE = chr(32) '0x20

const as ulong C_BLACK = rgb(0, 0, 0)
const as ulong C_YELLOW = rgb(175, 175, 0)
const as ulong C_BLUE_1 = rgb(0, 70, 160)
const as ulong C_BLUE_2 = rgb(0, 50, 120)
const as ulong C_RED = rgb(175, 0, 0)
const as ulong C_WHITE = rgb(250, 250, 250)

sub drawSquare(scrnPos as int2d, size as integer, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size - 1, size - 1), c, bf
end sub

sub drawRect(scrnPos as int2d, size as int2d, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size.x - 1, size.y - 1), c, bf
end sub

sub drawCircle(scrnPos as int2d, r as integer, c as ulong)
   circle(scrnPos.x, scrnPos.y), r, c,,,,f
end sub

sub printAt(scrnPos as int2d, text as string, c as ulong)
   draw string(scrnPos.x, scrnPos.y), text, c
end sub

sub clearScreen(c as ulong)
   dim as integer w, h
   screeninfo w, h
   line(0, 0)-(w - 1, h - 1), c, bf
end sub

'-------------------------------------------------------------------------------

type board_type
   public:
   const BRD_W = 7, BRD_H = 6
   const EMPTY = 0, RED = 1, YELLOW = 2
   dim as ulong discColor(0 to 3) = {C_BLACK, C_RED, C_YELLOW}
   dim as int2d scrnOffs, scrnArea 'screen area size to use
   dim as integer gridSize
   dim as integer hole(BRD_W - 1, BRD_H - 1)
   public:
   declare function validPos(gridPos as int2d) as boolean
   declare function getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   declare function getGridPos(scrnPos as int2d) as int2d
   declare function rowFreeIndex(row as integer) as integer
   declare function checkWinner(playerColor as integer) as boolean
   declare sub init(scrnPos as int2d, scrnSize as int2d)
   declare sub drawDisc(scrnPos as int2d, discType as integer)
   declare sub render()
end type

function board_type.validPos(gridPos as int2d) as boolean
   if gridPos.x < 0 or gridPos.x >= BRD_W then return false
   if gridPos.y < 0 or gridPos.y >= BRD_H then return false
   return true
end function

function board_type.getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   if center = 0 then
      return scrnOffs + gridPos * gridSize
   else
      return scrnOffs + gridPos * gridSize + int2d(gridSize \ 2, gridSize \ 2)
   end if
end function

function board_type.getGridPos(scrnPos as int2d) as int2d
   return (scrnPos - scrnOffs) \ gridSize
end function

'get higest vacancy position index for row
function board_type.rowFreeIndex(row as integer) as integer
   for yi as integer = 0 to BRD_H - 1
      if hole(row, yi) <> EMPTY then return yi - 1
   next
   return BRD_H - 1
end function

function board_type.checkWinner(playerColor as integer) as boolean
   dim as integer count
   'check horizontally
   for yi as integer = 0 to BRD_H - 1
      count = 0
      for xi as integer = 0 to BRD_W - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check vertically
   for xi as integer = 0 to BRD_W - 1
      count = 0
      for yi as integer = 0 to BRD_H - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check diagonally \ direction
   for i as integer = -(BRD_H - 4) to (BRD_W - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i + yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   '~ 'check diagonally / direction
   for i as integer = 3 to (BRD_W - 1) + (BRD_H - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i - yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   return false
end function

sub board_type.init(scrnPos as int2d, scrnSize as int2d)
   'set board dimensions, using a small downward shift
   gridSize = MIN(scrnSize.x \ (BRD_W + 1), scrnSize.y \ (BRD_H + 2))
   scrnOffs.x = scrnPos.x + (scrnSize.x - (gridSize * BRD_W)) \ 2
   scrnOffs.y = scrnPos.y + (scrnSize.y - (gridSize * (BRD_H - 1))) \ 2
   scrnArea = int2d(gridSize * BRD_W, gridSize * BRD_H)
   'clear grid
   dim as integer xi, yi
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      'hole(xi, yi) = int(rnd * 3)
      hole(xi, yi) = EMPTY
   next : next
end sub

sub board_type.drawDisc(scrnPos as int2d, discType as integer)
   drawCircle(scrnPos, gridSize * 0.40, discColor(discType))
end sub

sub board_type.render()
   dim as integer xi, yi
   dim as ulong c
   dim as int2d scrnPos = getScrnPos(int2d(0, 0))
   dim as int2d border = int2d(gridSize * 0.05, gridSize * 0.05)
   'draw large blue rectangle
   drawRect(scrnPos - border, scrnArea + border * 2, C_BLUE_1)
   drawRect(scrnPos, scrnArea, C_BLUE_2)
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      scrnPos = getScrnPos(int2d(xi, yi), 1)
      'draw blue circle
      drawCircle(scrnPos, gridSize * 0.45 , C_BLUE_1)
      'draw discs & gaps
      drawDisc(scrnPos, hole(xi, yi))
   next : next
end sub

'-------------------------------------------------------------------------------

const SCRN_W = 800, SCRN_H = 600
screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16

dim as board_type board
dim as integer quit = 0, selCol = 0, tarRow, falling = 0
dim as int2d selDiscPos, tarDiscPos 'positions on screen
dim as single yFall, vFall = 2000.0 'px/s
dim as string key, winnerStr
dim as double tNow = timer, tPrev = timer, tStep = 0
dim as integer playerId = board.RED

board.init(int2d(0, 0), int2d(SCRN_W - 1, SCRN_H - 1))
selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
while quit = 0
   key = inkey()
   select case key
   case KEY_ESC
      quit = 1
   case KEY_LE
      if falling = 0 then if selCol > 0 then selCol -= 1
   case KEY_RI
      if falling = 0 then if selCol < (board.BRD_W - 1) then selCol += 1
   case KEY_SPACE
      if falling = 0 then
         if board.hole(selCol, 0) = board.EMPTY then
            falling = 1
            yFall = selDiscPos.y 'convert to single
            tarRow = board.rowFreeIndex(selCol)
            tarDiscPos = board.getScrnPos(int2d(selCol, tarRow), 1)
         end if
      end if
   end select
   if falling = 0 then
      selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
   else
      yFall += vFall * tStep
      selDiscPos.y = cint(yfall)
      if selDiscPos.y >= tarDiscPos.y then
         falling = 0
         board.hole(selCol, tarRow) = playerId
         if board.checkWinner(playerId) then
            winnerStr = iif(playerId = board.RED, "RED", "YELLOW")
            quit = 2
         end if
         playerId = iif(playerId = board.RED, board.YELLOW, board.RED)
         selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
      end if
   end if

   screenlock
   clearScreen(C_BLACK)
   locate 1,1 : print "Connect four / May 2020"
   locate 2,1 : print "Keys: Left, Right, Space, Escape"
   board.render()
   if quit = 0 then board.drawDisc(selDiscPos, playerId)
   screenunlock

   sleep 1
   tPrev = tNow
   tNow = timer
   tStep = tNow - tPrev
wend

print !"\nEND: " & iif(quit = 1, "ABORTED", "A WINNER: " & winnerStr)
while getkey() <> 27: wend

Next step: An AI opponent.

Image
Last edited by badidea on May 23, 2020 10:48, edited 1 time in total.
BasicCoder2
Posts: 3524
Joined: Jan 01, 2009 7:03

Re: Yet Another Connect Four

Postby BasicCoder2 » May 22, 2020 3:44

Nice implementation :)
Previous attempts,
viewtopic.php?f=8&t=21659&
sero
Posts: 30
Joined: Mar 06, 2018 13:26
Location: USA

Re: Yet Another Connect Four

Postby sero » May 22, 2020 4:59

badidea wrote:Next step: An AI opponent.

Image
badidea
Posts: 1999
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Yet Another Connect Four

Postby badidea » May 23, 2020 10:42

I have added an AI, it is not the brightest however:

Code: Select all

#include "fbgfx.bi"

dim shared as string debugStr

'-------------------------------------------------------------------------------

type int2d
   as integer x, y
   declare constructor
   declare constructor(x as integer, y as integer)
end type

constructor int2d
end constructor

constructor int2d(x as integer, y as integer)
   this.x = x : this.y = y
end constructor

operator + (a as int2d, b as int2d) as int2d
   return type(a.x + b.x, a.y + b.y)
end operator

operator - (a as int2d, b as int2d) as int2d
   return type(a.x - b.x, a.y - b.y)
end operator

operator * (a as int2d, mul as integer) as int2d
   return type(a.x * mul, a.y * mul)
end operator

operator \ (a as int2d, divider as integer) as int2d
   return type(a.x \ divider, a.y \ divider)
end operator

'-------------------------------------------------------------------------------

#define MIN(a, b) iif((a) < (b), (a), (b))
#define MAX(a, b) iif((a) > (b), (a), (b))

const as string KEY_LE = chr(255, 75) 'K
const as string KEY_RI = chr(255, 77) 'M
const as string KEY_ESC = chr(27)
const as string KEY_SPACE = chr(32) '0x20

const as ulong C_BLACK = rgb(0, 0, 0)
const as ulong C_YELLOW = rgb(175, 175, 0)
const as ulong C_BLUE_1 = rgb(0, 70, 160)
const as ulong C_BLUE_2 = rgb(0, 50, 120)
const as ulong C_RED = rgb(175, 0, 0)
const as ulong C_WHITE = rgb(250, 250, 250)

sub drawSquare(scrnPos as int2d, size as integer, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size - 1, size - 1), c, bf
end sub

sub drawRect(scrnPos as int2d, size as int2d, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size.x - 1, size.y - 1), c, bf
end sub

sub drawCircle(scrnPos as int2d, r as integer, c as ulong)
   circle(scrnPos.x, scrnPos.y), r, c,,,,f
end sub

sub printAt(scrnPos as int2d, text as string, c as ulong)
   draw string(scrnPos.x, scrnPos.y), text, c
end sub

sub clearScreen(c as ulong)
   dim as integer w, h
   screeninfo w, h
   line(0, 0)-(w - 1, h - 1), c, bf
end sub

'-------------------------------------------------------------------------------

type board_type
   public:
   const BRD_W = 7, BRD_H = 6
   const EMPTY = 0, RED = 1, YELLOW = 2
   dim as ulong discColor(0 to 3) = {C_BLACK, C_RED, C_YELLOW}
   dim as int2d scrnOffs, scrnArea 'screen area size to use
   dim as integer gridSize
   dim as integer hole(BRD_W - 1, BRD_H - 1)
   public:
   declare function validPos(gridPos as int2d) as boolean
   declare function getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   declare function getGridPos(scrnPos as int2d) as int2d
   declare function rowFreeIndex(row as integer) as integer
   declare function checkWinner(playerColor as integer) as boolean
   declare function findBest(playerColor as integer) as integer
   declare function evaluate(playerColor as integer) as integer
   declare sub init(scrnPos as int2d, scrnSize as int2d)
   declare sub drawDisc(scrnPos as int2d, discType as integer)
   declare sub render()
end type

function board_type.validPos(gridPos as int2d) as boolean
   if gridPos.x < 0 or gridPos.x >= BRD_W then return false
   if gridPos.y < 0 or gridPos.y >= BRD_H then return false
   return true
end function

function board_type.getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   if center = 0 then
      return scrnOffs + gridPos * gridSize
   else
      return scrnOffs + gridPos * gridSize + int2d(gridSize \ 2, gridSize \ 2)
   end if
end function

function board_type.getGridPos(scrnPos as int2d) as int2d
   return (scrnPos - scrnOffs) \ gridSize
end function

'get higest vacancy position index for column, ret -1 = full
function board_type.rowFreeIndex(row as integer) as integer
   for yi as integer = 0 to BRD_H - 1
      if hole(row, yi) <> EMPTY then return yi - 1
   next
   return BRD_H - 1 'column fully empty
end function

function board_type.checkWinner(playerColor as integer) as boolean
   dim as integer count
   'check horizontally
   for yi as integer = 0 to BRD_H - 1
      count = 0
      for xi as integer = 0 to BRD_W - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check vertically
   for xi as integer = 0 to BRD_W - 1
      count = 0
      for yi as integer = 0 to BRD_H - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check diagonally \ direction
   for i as integer = -(BRD_H - 4) to (BRD_W - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i + yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   '~ 'check diagonally / direction
   for i as integer = 3 to (BRD_W - 1) + (BRD_H - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i - yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   return false
end function

function board_type.findBest(playerColor as integer) as integer
   dim as integer row, col, score, bestScore = -1, bestCol = -1
   for col = 0 to BRD_W - 1
      row = rowFreeIndex(col)
      if row > 0 then
         'place
         hole(col, row) = playerColor
         'test
         score = evaluate(playerColor) + (3 - abs(3 - col))
         if score > bestScore then
            bestScore = score
            bestCol = col
         end if
         'remove
         hole(col, row) = EMPTY
      end if
   next
   debugStr = "Best: " & bestScore & " at: " & bestCol
   return bestCol '-1 if board full
end function

function board_type.evaluate(playerColor as integer) as integer
   dim as integer count
   dim as integer num2 = 0, num3 = 0, num4 = 0
   'check horizontally
   for yi as integer = 0 to BRD_H - 1
      count = 0
      for xi as integer = 0 to BRD_W - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 2 then num2 += 1
            if count = 3 then num3 += 1
            if count = 4 then num4 += 1
         else
            count = 0
         end if
      next
   next
   'check vertically
   for xi as integer = 0 to BRD_W - 1
      count = 0
      for yi as integer = 0 to BRD_H - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 2 then num2 += 1
            if count = 3 then num3 += 1
            if count = 4 then num4 += 1
         else
            count = 0
         end if
      next
   next
   'check diagonally \ direction
   for i as integer = -(BRD_H - 4) to (BRD_W - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i + yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 2 then num2 += 1
               if count = 3 then num3 += 1
               if count = 4 then num4 += 1
            else
               count = 0
            end if
         end if
      next
   next
   '~ 'check diagonally / direction
   for i as integer = 3 to (BRD_W - 1) + (BRD_H - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i - yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 2 then num2 += 1
               if count = 3 then num3 += 1
               if count = 4 then num4 += 1
            else
               count = 0
            end if
         end if
      next
   next
   'debugStr = "num4: " & num4 & " num3: " & num3 & " num2: " & num2
   return num4 * 1000 + num3 * 100 + num2 * 10
end function

sub board_type.init(scrnPos as int2d, scrnSize as int2d)
   'set board dimensions, using a small downward shift
   gridSize = MIN(scrnSize.x \ (BRD_W + 1), scrnSize.y \ (BRD_H + 2))
   scrnOffs.x = scrnPos.x + (scrnSize.x - (gridSize * BRD_W)) \ 2
   scrnOffs.y = scrnPos.y + (scrnSize.y - (gridSize * (BRD_H - 1))) \ 2
   scrnArea = int2d(gridSize * BRD_W, gridSize * BRD_H)
   'clear grid
   dim as integer xi, yi
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      'hole(xi, yi) = int(rnd * 3)
      hole(xi, yi) = EMPTY
   next : next
end sub

sub board_type.drawDisc(scrnPos as int2d, discType as integer)
   drawCircle(scrnPos, gridSize * 0.40, discColor(discType))
end sub

sub board_type.render()
   dim as integer xi, yi
   dim as ulong c
   dim as int2d scrnPos = getScrnPos(int2d(0, 0))
   dim as int2d border = int2d(gridSize * 0.05, gridSize * 0.05)
   'draw large blue rectangle
   drawRect(scrnPos - border, scrnArea + border * 2, C_BLUE_1)
   drawRect(scrnPos, scrnArea, C_BLUE_2)
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      scrnPos = getScrnPos(int2d(xi, yi), 1)
      'draw blue circle
      drawCircle(scrnPos, gridSize * 0.45 , C_BLUE_1)
      'draw discs & gaps
      drawDisc(scrnPos, hole(xi, yi))
   next : next
end sub

'-------------------------------------------------------------------------------

const SCRN_W = 800, SCRN_H = 600
screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16

dim as board_type board
dim as integer quit = 0, selCol = 0, tarRow, falling = 0
dim as int2d selDiscPos, tarDiscPos 'positions on screen
dim as single yFall, vFall = 1500.0 'px/s
dim as string key, winnerStr
dim as double tNow = timer, tPrev = timer, tStep = 0
dim as integer playerId = board.RED

randomize timer
board.init(int2d(0, 0), int2d(SCRN_W - 1, SCRN_H - 1))
selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
while quit = 0
   key = inkey()
   if falling = 0 then
      if playerId = board.RED then
      'human plays red first
         select case key
         case KEY_ESC
            quit = 1
         case KEY_LE
            if selCol > 0 then selCol -= 1
         case KEY_RI
            if selCol < (board.BRD_W - 1) then selCol += 1
         case KEY_SPACE
            if board.hole(selCol, 0) = board.EMPTY then
               falling = 1
               yFall = selDiscPos.y 'convert to single
               tarRow = board.rowFreeIndex(selCol)
               tarDiscPos = board.getScrnPos(int2d(selCol, tarRow), 1)
            end if
         end select
         selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
      else
      'computer plays yellow
         selCol = board.findBest(playerId)
         if selCol = -1 then
            quit = 1
         else
            selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
            falling = 1
            yFall = selDiscPos.y
            tarRow = board.rowFreeIndex(selCol)
            tarDiscPos = board.getScrnPos(int2d(selCol, tarRow), 1)
         end if
      end if
   else 'falling = 1
      yFall += vFall * tStep
      selDiscPos.y = cint(yfall)
      if selDiscPos.y >= tarDiscPos.y then
         falling = 0
         board.hole(selCol, tarRow) = playerId
         if board.checkWinner(playerId) then
            winnerStr = iif(playerId = board.RED, "RED", "YELLOW")
            quit = 2
         end if
         'next player
         playerId = iif(playerId = board.RED, board.YELLOW, board.RED)
         selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
      end if
   end if

   screenlock
   clearScreen(C_BLACK)
   locate 1,1 : print "Connect four / May 2020"
   locate 2,1 : print "Keys: Left, Right, Space, Escape"
   locate 3,1 : print debugStr
   board.render()
   if quit = 0 then board.drawDisc(selDiscPos, playerId)
   screenunlock

   sleep 1
   tPrev = tNow
   tNow = timer
   tStep = tNow - tPrev
wend

print !"\nEND: " & iif(quit = 1, "ABORTED", "A WINNER: " & winnerStr)
while getkey() <> 27: wend

Next step: A minimax algorithm... Mostly behaving like artificial stupidity_ at the moment.
I think I should change the game in "Do not connect four", or maybe "Do not connect three" to make it more challenging.
I gets worse, the AI now aborts the game on first turn.

Edit: Bug in forum software
Last edited by badidea on May 27, 2020 23:03, edited 1 time in total.
badidea
Posts: 1999
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Yet Another Connect Four

Postby badidea » May 27, 2020 0:24

minimax algorithm working better now, but still not right.
MAX_DEPTH must be even (2, 4, 6), but then still random acts of sagacity (<- WHAT IS going on? What is sagacity? I write stupidity_!).

Code: Select all

#include "simple_logger.bi"

'-------------------------------------------------------------------------------

type int2d
   as integer x, y
   declare constructor
   declare constructor(x as integer, y as integer)
end type

constructor int2d
end constructor

constructor int2d(x as integer, y as integer)
   this.x = x : this.y = y
end constructor

operator + (a as int2d, b as int2d) as int2d
   return type(a.x + b.x, a.y + b.y)
end operator

operator - (a as int2d, b as int2d) as int2d
   return type(a.x - b.x, a.y - b.y)
end operator

operator * (a as int2d, mul as integer) as int2d
   return type(a.x * mul, a.y * mul)
end operator

operator \ (a as int2d, divider as integer) as int2d
   return type(a.x \ divider, a.y \ divider)
end operator

'-------------------------------------------------------------------------------

#define MIN(a, b) iif((a) < (b), (a), (b))
#define MAX(a, b) iif((a) > (b), (a), (b))

const as string KEY_LE = chr(255, 75) 'K
const as string KEY_RI = chr(255, 77) 'M
const as string KEY_ESC = chr(27)
const as string KEY_SPACE = chr(32) '0x20

const as ulong C_BLACK = rgb(0, 0, 0)
const as ulong C_YELLOW = rgb(175, 175, 0)
const as ulong C_BLUE_1 = rgb(0, 70, 160)
const as ulong C_BLUE_2 = rgb(0, 50, 120)
const as ulong C_RED = rgb(175, 0, 0)
const as ulong C_WHITE = rgb(250, 250, 250)

sub drawSquare(scrnPos as int2d, size as integer, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size - 1, size - 1), c, bf
end sub

sub drawRect(scrnPos as int2d, size as int2d, c as ulong)
   line(scrnPos.x, scrnPos.y)-step(size.x - 1, size.y - 1), c, bf
end sub

sub drawCircle(scrnPos as int2d, r as integer, c as ulong)
   circle(scrnPos.x, scrnPos.y), r, c,,,,f
end sub

sub printAt(scrnPos as int2d, text as string, c as ulong)
   draw string(scrnPos.x, scrnPos.y), text, c
end sub

sub clearScreen(c as ulong)
   dim as integer w, h
   screeninfo w, h
   line(0, 0)-(w - 1, h - 1), c, bf
end sub

type score_type
   dim as integer value
   dim as integer move
end type

'-------------------------------------------------------------------------------

type board_type
   public:
   const BRD_W = 7, BRD_H = 6
   'const BRD_W = 10, BRD_H = 7
   const EMPTY = 0, RED = 1, YELLOW = 2
   const MAX_DEPTH = 6 'must be even
   dim as integer bestMove
   dim as ulong discColor(0 to 3) = {C_BLACK, C_RED, C_YELLOW}
   dim as int2d scrnOffs, scrnArea 'screen area size to use
   dim as integer gridSize
   dim as integer hole(BRD_W - 1, BRD_H - 1)
   public:
   declare function opponent(playerColor as integer) as integer
   declare function validPos(gridPos as int2d) as boolean
   declare function getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   declare function getGridPos(scrnPos as int2d) as int2d
   declare function rowFreeIndex(row as integer) as integer
   declare function checkWinner(playerColor as integer) as boolean
   declare function minimax(depth as integer, playerColor as integer) as integer
   declare function evaluate(playerColor as integer) as integer
   declare sub init(scrnPos as int2d, scrnSize as int2d)
   declare sub drawDisc(scrnPos as int2d, discType as integer)
   declare sub render()
end type

function board_type.opponent(playerColor as integer) as integer
   return iif(playerColor = RED, YELLOW, RED)
end function

function board_type.validPos(gridPos as int2d) as boolean
   if gridPos.x < 0 or gridPos.x >= BRD_W then return false
   if gridPos.y < 0 or gridPos.y >= BRD_H then return false
   return true
end function

function board_type.getScrnPos(gridPos as int2d, center as integer = 0) as int2d
   if center = 0 then
      return scrnOffs + gridPos * gridSize
   else
      return scrnOffs + gridPos * gridSize + int2d(gridSize \ 2, gridSize \ 2)
   end if
end function

function board_type.getGridPos(scrnPos as int2d) as int2d
   return (scrnPos - scrnOffs) \ gridSize
end function

'get higest vacancy position index for column, ret -1 = full
function board_type.rowFreeIndex(row as integer) as integer
   for yi as integer = 0 to BRD_H - 1
      if hole(row, yi) <> EMPTY then return yi - 1
   next
   return BRD_H - 1 'column fully empty
end function

function board_type.checkWinner(playerColor as integer) as boolean
   dim as integer count
   'check horizontally
   for yi as integer = 0 to BRD_H - 1
      count = 0
      for xi as integer = 0 to BRD_W - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check vertically
   for xi as integer = 0 to BRD_W - 1
      count = 0
      for yi as integer = 0 to BRD_H - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 4 then return true
         else
            count = 0
         end if
      next
   next
   'check diagonally \ direction
   for i as integer = -(BRD_H - 4) to (BRD_W - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i + yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   '~ 'check diagonally / direction
   for i as integer = 3 to (BRD_W - 1) + (BRD_H - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i - yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 4 then return true
            else
               count = 0
            end if
         end if
      next
   next
   return false
end function

'~ function minimax(node, depth, maximizingPlayer) is
    '~ if depth = 0 or node is a terminal node then
        '~ return the heuristic value of node
    '~ if maximizingPlayer then
        '~ value := −∞
        '~ for each child of node do
            '~ value := max(value, minimax(child, depth − 1, FALSE))
        '~ return value
    '~ else (* minimizing player *)
        '~ value := +∞
        '~ for each child of node do
            '~ value := min(value, minimax(child, depth − 1, TRUE))
        '~ return value

'AI always plays with YELLOW
function board_type.minimax(depth as integer, playerColor as integer) as integer
   dim as integer value, row, col, score, bestValue, bestCol = -1
   dim as integer opponentColor = iif(playerColor = RED, YELLOW, RED)

   if depth = MAX_DEPTH then
      'note swapped on previous depth
      if playerColor = RED then
         value = evaluate(YELLOW)
      else
         value = -evaluate(RED)
      end if
      'value = evaluate(YELLOW) - evaluate(RED)
      return value
   else
      if playerColor = YELLOW then
         bestValue = -9999999
         for col = 0 to BRD_W - 1
            row = rowFreeIndex(col)
            if row >= 0 then
               hole(col, row) = playerColor
               value = minimax(depth + 1, opponentColor)
               if value > bestValue then
                  bestValue = value
                  bestCol = col
               end if
               hole(col, row) = EMPTY
            end if
         next
      else 'RED
         bestValue = +9999999
         for col = 0 to BRD_W - 1
            row = rowFreeIndex(col)
            if row >= 0 then
               hole(col, row) = playerColor
               value = minimax(depth + 1, opponentColor)
               if value < bestValue then
                  bestValue = value
                  bestCol = col
               end if
               hole(col, row) = EMPTY
            end if
         next
      end if
      '
      if depth = 0 then this.bestMove = bestCol
      return bestValue
   end if
end function

function board_type.evaluate(playerColor as integer) as integer
   dim as integer count
   dim as integer num2 = 0, num3 = 0, num4 = 0
   'check horizontally
   for yi as integer = 0 to BRD_H - 1
      count = 0
      for xi as integer = 0 to BRD_W - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 2 then num2 += 1
            if count = 3 then num3 += 1
            if count = 4 then num4 += 1
         else
            count = 0
         end if
      next
   next
   'check vertically
   for xi as integer = 0 to BRD_W - 1
      count = 0
      for yi as integer = 0 to BRD_H - 1
         if hole(xi, yi) = playerColor then
            count += 1
            if count = 2 then num2 += 1
            if count = 3 then num3 += 1
            if count = 4 then num4 += 1
         else
            count = 0
         end if
      next
   next
   'check diagonally \ direction
   for i as integer = -(BRD_H - 4) to (BRD_W - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i + yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 2 then num2 += 1
               if count = 3 then num3 += 1
               if count = 4 then num4 += 1
            else
               count = 0
            end if
         end if
      next
   next
   '~ 'check diagonally / direction
   for i as integer = 3 to (BRD_W - 1) + (BRD_H - 4)
      count = 0
      for yi as integer = 0 to BRD_H - 1
         dim as integer xi = i - yi
         if validPos(int2d(xi, yi)) then
            if hole(xi, yi) = playerColor then
               count += 1
               if count = 2 then num2 += 1
               if count = 3 then num3 += 1
               if count = 4 then num4 += 1
            else
               count = 0
            end if
         end if
      next
   next
   return num4 * 10000 + num3 * 100 + num2 * 10  + int(rnd * 5)
end function

sub board_type.init(scrnPos as int2d, scrnSize as int2d)
   'set board dimensions, using a small downward shift
   gridSize = MIN(scrnSize.x \ (BRD_W + 1), scrnSize.y \ (BRD_H + 2))
   scrnOffs.x = scrnPos.x + (scrnSize.x - (gridSize * BRD_W)) \ 2
   scrnOffs.y = scrnPos.y + (scrnSize.y - (gridSize * (BRD_H - 1))) \ 2
   scrnArea = int2d(gridSize * BRD_W, gridSize * BRD_H)
   'clear grid
   dim as integer xi, yi
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      'hole(xi, yi) = int(rnd * 3)
      hole(xi, yi) = EMPTY
   next : next
end sub

sub board_type.drawDisc(scrnPos as int2d, discType as integer)
   drawCircle(scrnPos, gridSize * 0.40, discColor(discType))
end sub

sub board_type.render()
   dim as integer xi, yi
   dim as ulong c
   dim as int2d scrnPos = getScrnPos(int2d(0, 0))
   dim as int2d border = int2d(gridSize * 0.05, gridSize * 0.05)
   'draw large blue rectangle
   drawRect(scrnPos - border, scrnArea + border * 2, C_BLUE_1)
   drawRect(scrnPos, scrnArea, C_BLUE_2)
   for xi = 0 to BRD_W - 1 : for yi = 0 to BRD_H - 1
      scrnPos = getScrnPos(int2d(xi, yi), 1)
      'draw blue circle
      drawCircle(scrnPos, gridSize * 0.45 , C_BLUE_1)
      'draw discs & gaps
      drawDisc(scrnPos, hole(xi, yi))
   next : next
end sub

'-------------------------------------------------------------------------------

type loop_timer_type
   dim as double tNow, tPrev, tStep
   declare constructor()
   declare sub update()
   declare function dt() as double
end type

constructor loop_timer_type()
   tNow = timer
   update()
end constructor

sub loop_timer_type.update()
   tPrev = tNow
   tNow = timer
   tStep = tNow - tPrev
end sub

function loop_timer_type.dt() as double
   return tStep
end function

'-------------------------------------------------------------------------------

const SCRN_W = 800, SCRN_H = 600
screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16

dim as board_type board
dim as integer quit = 0, selCol = 0, tarRow, falling = 0
dim as int2d selDiscPos, tarDiscPos 'positions on screen
dim as single yFall, vFall = 1500.0 'px/s
dim as string key, winnerStr
dim as integer playerId = board.RED
dim as loop_timer_type loopTimer

randomize timer
board.init(int2d(0, 0), int2d(SCRN_W - 1, SCRN_H - 1))
selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
while quit = 0
   key = inkey()
   if falling = 0 then
      if playerId = board.RED then
         'human plays red first
         select case key
         case KEY_ESC
            quit = 1
         case KEY_LE
            if selCol > 0 then selCol -= 1
         case KEY_RI
            if selCol < (board.BRD_W - 1) then selCol += 1
         case KEY_SPACE
            if board.hole(selCol, 0) = board.EMPTY then
               falling = 1
               yFall = selDiscPos.y 'convert to single
               tarRow = board.rowFreeIndex(selCol)
               tarDiscPos = board.getScrnPos(int2d(selCol, tarRow), 1)
            end if
         end select
         selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
      else
         'computer plays yellow
         locate 3,1 : print "Thinking..."
         board.minimax(0, board.YELLOW)
         selCol = board.bestMove
         if selCol = -1 then
            quit = 3
         else
            selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
            falling = 1
            yFall = selDiscPos.y
            tarRow = board.rowFreeIndex(selCol)
            tarDiscPos = board.getScrnPos(int2d(selCol, tarRow), 1)
         end if
         loopTimer.update() 'reset long timeStep for falling animation
      end if
   else 'falling = 1
      yFall += vFall * loopTimer.dt()
      selDiscPos.y = cint(yfall)
      if selDiscPos.y >= tarDiscPos.y then
         falling = 0
         board.hole(selCol, tarRow) = playerId
         if board.checkWinner(playerId) then
            winnerStr = iif(playerId = board.RED, "RED", "YELLOW")
            quit = 2
         end if
         'next player
         playerId = iif(playerId = board.RED, board.YELLOW, board.RED)
         selDiscPos = board.getScrnPos(int2d(selCol, -1), 1)
      end if
   end if

   screenlock
   clearScreen(C_BLACK)
   locate 1, 1 : print "Connect four / May 2020"
   locate 2, 1 : print "Keys: Left, Right, Space, Escape"
   board.render()
   if quit = 0 then board.drawDisc(selDiscPos, playerId)
   screenunlock

   sleep 1
   loopTimer.update()
wend

print "End: ";
select case quit
case 1 : print "USER ABORT"
case 2 : print "A WINNER: " & winnerStr
case 3 : print "AI ERROR"
end select

while getkey() <> 27: wend
BasicCoder2
Posts: 3524
Joined: Jan 01, 2009 7:03

Re: Yet Another Connect Four

Postby BasicCoder2 » May 29, 2020 9:48

You might get some AI ideas if you google,
how to win at connect 4
badidea
Posts: 1999
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Yet Another Connect Four

Postby badidea » May 29, 2020 14:43

I don't google. But anyway, the recursive minimax algorithm only requires an evaluation of the board status (which is relative simple for connect 4) and should find the best move of all possible moves for a given depth. No further knowledge like strategies needed. For a search depth of ~8 or more the AI should be almost unbeatable (unless you are a professional connect 4 player :-).
But something does not seem right in my minimax implementation. Also the evaluation process is currently too slow for a search depth of 8, but that can be solved.
I implemented a minimax algorithm before (A Checkers / Draughts program) which did work a lot better (but with some trouble for crowned pieces). So I could compare the 2 implementations, but that is not a very exiting task. And I want to move to a next game...
BasicCoder2
Posts: 3524
Joined: Jan 01, 2009 7:03

Re: Yet Another Connect Four

Postby BasicCoder2 » May 29, 2020 19:21

Although I dislike the monopoly of google I must confess I use it all the time. The internet is a rich source of information on many topics.

So you don't use any search engine? Although I used to gain all my knowledge through books Amazon has destroyed the ability of physical outlets to stock the technical books I used to buy and limited Australians access to books over tax issues.

Just as choosing the middle square is a good first move in tic tac toe so too is choosing the center column in connect 4. Apparently the person who moves first in connect 4 can always win if they play the game correctly.

Yes you need to find something to program that you can get excited about.
badidea
Posts: 1999
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Yet Another Connect Four

Postby badidea » May 29, 2020 20:51

BasicCoder2 wrote:Although I dislike the monopoly of google I must confess I use it all the time. So you don't use any search engine? Although I used to gain all my knowledge through books Amazon has destroyed the ability of physical outlets to stock the technical books I used to buy and limited Australians access to books over tax issues. The internet is a rich source of information on many topics.

I do. I switched the default browser search-engine to Duck-Duck-Go years ago. If you don't like the results, you can change the search term to "blabla g!" and it fetches the Google results. But I rarely use this option. DDG says: "We don't store your personal info". But even if they do, I prefer them over Google, because Google has many other ways to collect data on you. I try to limit the data I give to (big) companies, without making my own life too hard.
- GNU/Linux instead of Microsoft OS or Apple OS.
- Firefox or Chromium instead of Chrome / Edge / Internet explorer (PC and smartphone)
- uBlock Origin add blocker with social media stuff blocker (PC and smartphone)
- Delete all history, cache, cookies on browser exit (can be annoying, but you can accept all the cookies in the world, they will be trashed anyway)
- Sailfish OS on phone with some android support, but no Google Play store, which can be a challenge [1].
- etc.
[1] If a bank makes a payment 'app', you cannot find it on the bank's website. Why? Because your Google or Apple phone only trusts the software in there own 'app' store. So you and the bank have trust Google/Apple. If Google/Apple does not like your bank, or company or whatever, bad luck.

BasicCoder2 wrote:The brute force look ahead of the minimax method, which I have implemented on a chess game, doesn't seem like "intelligence" to me. We do it ourselves to a limited extent but ultimately we use intuition (maybe like a trained neural net) and strategies to come up with good moves.

Well, define "intelligence" please :-) Is AlphaGo intelligent? Or just AlphaGo programmers? Is a dolphin intelligent? Would it be able to play 'connect four'? If the 'dumbest' algorithm thinkable running on a million computers parallel can beat every human, is it intelligent?

BasicCoder2 wrote:Just as choosing the middle square is a good first move in tic tac toe so too is choosing the center column in connect 4.

Yes, I made my first simple AI to prefer the center.

BasicCoder2 wrote:Apparently the person who moves first in connect 4 can always win if they play the game correctly.

Yes, the problem is that the most exciting things are also the most work, and my excitement goes down after a while. So my idea was to make a bunch of smaller games to get more experience and code to use, so that I can do a larger project more quickly. Not sure if this will work...
BasicCoder2
Posts: 3524
Joined: Jan 01, 2009 7:03

Re: Yet Another Connect Four

Postby BasicCoder2 » May 30, 2020 0:12

badidea wrote:Well, define "intelligence" please :-) Is AlphaGo intelligent? Or just AlphaGo programmers? Is a dolphin intelligent? Would it be able to play 'connect four'? If the 'dumbest' algorithm thinkable running on a million computers parallel can beat every human, is it intelligent?

A neural net is a computing unit used in a wider context, just as an adder circuit (which you could evolve from a neural net) might be used for many different purposes. The ANN is an evolved evaluator serving the same purpose as the evaluator function in a chess program. The downside with current neural nets is we don't really know how they "solve" the problem.

Is an adder circuit intelligent because it can add two numbers? An adding machine can beat an intelligent human at adding thousands of numbers in a short period of time. The fact is computers have a speed advantage but aren't doing anything we couldn't do if given pen and paper and thousands of years to carry it out. Like the computer program we could also carry out the computations to compute weights for an ANN without any understanding or purpose. Human intelligence involves purpose and understanding what and why it does something. I think that is part of what we mean by human level intelligence.

In human terms I think we see "being intelligent" as having a clear global representation of what is out there, how it works and how to use the representation to achieve some goal.

Yes, the problem is that the most exciting things are also the most work, and my excitement goes down after a while. So my idea was to make a bunch of smaller games to get more experience and code to use, so that I can do a larger project more quickly. Not sure if this will work...

My excitement also seems to go down after spending time on a programming project. Sometimes I come back to it, sometimes I don't. The little game demos I posted in this Games section were written out of flights of boredom.

Return to “Game Dev”

Who is online

Users browsing this forum: No registered users and 6 guests