Connect Four Game

/*
Game play
Author: John Bradnam (jbrad2089@gmail.com)
Purpose: AI for Connect Four
Based on code from mit-mit
(https://github.com/mit-mit-randomprojectlab/arduino_connect4)
*/
#pragma once

#include "Display.h"

#define COLOR_CPU COLOR_GRN
#define COLOR_USER COLOR_RED
#define COLOR_STATUS COLOR_BLU
#define COLOR_CLEAR COLOR_BLK

enum WIN_STATUS { WS_NONE, WS_DRAW, WS_WIN };

#define GB_COLS 8
#define GB_ROWS 6
#define PIECE(r,c) ((r << 3) + c)
enum GAME_BOARD { GB_EMPTY, GB_USER, GB_CPU };
GAME_BOARD board[GB_ROWS * GB_COLS];

#define NUM_MCTS_RUNS 500
#define SIMULATIONS 7
long simWins[SIMULATIONS];
long simLosses[SIMULATIONS];

//-------------------------------------------------------------------------
//Forward references
//-------------------------------------------------------------------------

int8_t getCpuPlay(GAME_BOARD player);
uint8_t getCurrentDisplay(GAME_BOARD gb[]);
void transferToDisplay(GAME_BOARD gb[]);
WIN_STATUS testForWin(GAME_BOARD gb[], uint8_t row, uint8_t col, GAME_BOARD player, uint8_t count);
int addPieceToColumn(GAME_BOARD gb[], uint8_t col, GAME_BOARD player);

//-------------------------------------------------------------------------
// CPU Play
//-------------------------------------------------------------------------

int8_t getCpuPlay(GAME_BOARD player) 
{
  int pieceCount;
  int simMoves;
  GAME_BOARD simPlayer;
  GAME_BOARD simOpponent;
  int8_t simRow;
  int8_t simCol;
  WIN_STATUS simWinStatus;
  long simScore, simBestScore;
  uint8_t simBestCol;

  simOpponent = (player == GB_CPU) ? GB_USER : GB_CPU;

  //Place current board into memory
  pieceCount = getCurrentDisplay(board);

  //Look for a CPU win
  for (int c = 0; c < COLS; c++) 
  {
    //Add a temporary piece to the board
    simRow = addPieceToColumn(board, c, GB_CPU);
    if (simRow != -1)
    {
      pieceCount++;
      simWinStatus = testForWin(board, simRow, c, GB_CPU, pieceCount);

      //Remove this piece from board
      board[PIECE(simRow, c)] = GB_EMPTY;
      pieceCount--;

      //Test if we won
      if (simWinStatus == WS_WIN)
      {
        return c;     //Return winning column
      }
    }
  }

  //Look for a square that stops a player win
  for (int c = 0; c < COLS; c++) 
  {
    //First look for the players winning move
    simRow = addPieceToColumn(board, c, GB_USER);
    if (simRow != -1)
    {
      pieceCount++;
      simWinStatus = testForWin(board, simRow, c, GB_USER, pieceCount);

      //Remove this piece from board
      board[PIECE(simRow,c)] = GB_EMPTY;
      pieceCount--;
      
      //Test if player won
      if (simWinStatus == WS_WIN)
      {
        return c;     //Return blocking column
      }
    }
  }

  //clear simulation tables
  for (int i = 0; i < SIMULATIONS; i++) 
  {
    simWins[i] = 0;
    simLosses[i] = 0;
  }

  simCol = 0;
  for (int i = 0; i < NUM_MCTS_RUNS; i++)
  {
    pieceCount = getCurrentDisplay(board);
    simPlayer = GB_CPU;
    // Make players first move
    simRow = addPieceToColumn(board, simCol, simPlayer);
    while (simRow == -1) 
    {
      simCol++;
      if (simCol == COLS) 
      {
        simCol = 0;
      }
      simRow = addPieceToColumn(board, simCol, simPlayer);
    }
    pieceCount++;
    if (testForWin(board, simRow, simCol, simPlayer, pieceCount) == WS_DRAW)
    {
      continue; //if draw, try next random move
    }
    
    // Loop through remaining moves until result
    simMoves = (ROWS * COLS) - pieceCount;
    while (true) 
    {
      // Swap  players
      simPlayer = (simPlayer == GB_CPU) ? GB_USER : GB_CPU;
      
      int8_t ranCol = random(0, COLS);
      int8_t ranRow = addPieceToColumn(board, ranCol, simPlayer);
      while (ranRow == -1) 
      {
        ranCol++;
        if (ranCol == COLS) 
        {
          ranCol = 0;
        }
        ranRow = addPieceToColumn(board, ranCol, simPlayer);
      }
      pieceCount++;
      simWinStatus = testForWin(board, ranRow, ranCol, simPlayer, pieceCount);
      if (simWinStatus == WS_WIN && simPlayer == player)
      { 
        // game resulted in win - record victory against this first played column
        simWins[simCol] += simMoves;
        // move to next random sample        
        break;
      }
      else if (simWinStatus == WS_WIN && simPlayer == simOpponent) 
      {
        // game resulted in loss - record defeat against this first played column
        simLosses[simCol] += simMoves;
        // move to next random sample
        break;
      }
      else if (simWinStatus == WS_DRAW) 
      { 
        // resulted in draw, move onto next sim
        break;
      }
      //Keep populating board
      simMoves--;
    }  //wend
    
    // Cycle through first-played cols
    simCol++;
    if (simCol == COLS) 
    {
      simCol = 0;
    }
  }
  
  // evaluate win/loss stats to determine best move
  simBestCol = 0;
  simBestScore = -49l * NUM_MCTS_RUNS;
  for (int c = 0; c < COLS; c++) 
  {
    simScore = simWins[c] - simLosses[c];
    if (simScore > simBestScore && displayGetPixel(0,c) == COLOR_CLEAR)
    {
      simBestCol = c;
      simBestScore = simScore;
    }
  }

  return simBestCol;
}

//-------------------------------------------------------------------------
// Copy current display to game array
//  Game board is a array of 48 bytes 6 row of 8 columns where coloum 8 is not used
//  gb - pointer to game board
//  returns count of pieces
//-------------------------------------------------------------------------

uint8_t getCurrentDisplay(GAME_BOARD gb[])
{
  uint32_t col;
  uint8_t count = 0;
  for (int r = 0; r < ROWS; r++)
  {
    for (int c = 0; c < COLS; c++)
    {
      col = displayGetPixel(((ROWS - 1) - r), c);
      gb[PIECE(r,c)] = (col == COLOR_USER) ? GB_USER : (col == COLOR_CPU) ? GB_CPU : GB_EMPTY;
      if (col != COLOR_CLEAR)
      {
        count++;
      }
    }
  }
  return count;
}

//-------------------------------------------------------------------------
// Copy current display to game array
//  Game board is a array of 48 bytes 6 row of 8 columns where coloum 8 is not used
//  gb - pointer to game board
//  returns count of pieces
//-------------------------------------------------------------------------

void transferToDisplay(GAME_BOARD gb[])
{
  GAME_BOARD player;
  for (int r = 0; r < ROWS; r++)
  {
    for (int c = 0; c < COLS; c++)
    {
      player = gb[PIECE(((ROWS - 1) - r),c)];
      displaySetPixel(r, c, (player == GB_USER) ? COLOR_USER : (player == GB_CPU) ? COLOR_CPU : COLOR_CLEAR);
    }
  }
}

//-------------------------------------------------------------------------
// Add a game piece to the board
//  gb - pointer to game board
//  col - column to add piece to (0 to 6)
//  player - GAME_BOARD constant
//  returns - row number where piece is added or -1 
//-------------------------------------------------------------------------

int addPieceToColumn(GAME_BOARD gb[], uint8_t col, GAME_BOARD player)
{
  int r = 0;
  while (r < ROWS && gb[PIECE(r, col)] != GB_EMPTY)
  {
      r++;
  };
  if (r < ROWS)
  {
      gb[PIECE(r, col)] = player;
      return r;
  }
  return -1;
}

//-------------------------------------------
// Test if 4 in a row made
//  gb - pointer to game board
//  row - 0 to 5 (0 = top, 5 = bottom) - piece dropped
//  col - 0 to 6 (0 = left, 6 = right) - piece dropped
//  player - GAME_BOARD constant
//  count - current number of moves
//  returns WIN_STATUS constant
//-------------------------------------------

WIN_STATUS testForWin(GAME_BOARD gb[], uint8_t row, uint8_t col, GAME_BOARD player, uint8_t count)
{
  WIN_STATUS result = WS_NONE;
  int8_t r, c, n;
  //Test vertical
  r = row;
  if (r > 0)
  {
    r--;
    while (r > 0 && gb[PIECE(r,col)] == player)
    {
      r--;
    }
    r = (gb[PIECE(r,col)] == player) ? r : r + 1;
  }
  n = 0;
  while (r < ROWS && n < 4 && gb[PIECE(r,col)] == player)
  {
    r++;
    n++;
  }
  if (n < 4)
  {
    //Test horizontal
    c = col;
    if (c > 0)
    {
      c--;
      while (c > 0 && gb[PIECE(row,c)] == player)
      {
        c--;
      }
      c = (gb[PIECE(row,c)] == player) ? c : c + 1;
    }
    n = 0;
    while (c < COLS && n < 4 && gb[PIECE(row,c)] == player)
    {
      c++;
      n++;
    }
    if (n < 4)
    {
      //Test diagonal top to bottom, left to right
      c = col;
      r = row;
      if (c > 0 && r > 0)
      {
        r--;
        c--;
        while (c > 0 && r > 0 && gb[PIECE(r,c)] == player)
        {
          c--;
          r--;
        }
        if (gb[PIECE(r,c)] != player)
        {
          c++;
          r++;
        }
      }
      n = 0;
      while (c < COLS && r < ROWS && n < 4 && gb[PIECE(r,c)] == player)
      {
        r++;
        c++;
        n++;
      }
      if (n < 4)
      {
        //Test diagonal bottom to top, left to right
        c = col;
        r = row;
        if (c > 0 && r < (ROWS - 1))
        {
          r++;
          c--;
          while (c > 0 && r < (ROWS - 1) && gb[PIECE(r,c)] == player)
          {
            r++;
            c--;
          }
          if (gb[PIECE(r,c)] != player)
          {
            r--;
            c++;
          }
        }
        n = 0;
        while (c < COLS && r >= 0 && n < 4 && gb[PIECE(r,c)] == player)
        {
          r--;
          c++;
          n++;
        }
      }
    }
  }

  if (n == 4)
  {
    result = WS_WIN;
  }
  else if (count == (ROWS * COLS))
  {
    result = WS_DRAW;
  }
  return result;
}

/*
Low Level Display Routines
Author: John Bradnam (jbrad2089@gmail.com)
Purpose: RGB Matrix display routines
*/
#pragma once

#include "Hardware.h"
#include "Font.h"
#include <tinyNeoPixel.h>

#define NUMLEDS 64
tinyNeoPixel leds = tinyNeoPixel(NUMLEDS, LEDS, NEO_GRB);

#define ANIMATE_DROP_DELAY 100
#define ANIMATE_WIN_DELAY 250
#define ANIMATE_WIN_COUNT 15

#define ROWS 6
#define COLS 7
#define COLSEL 57
#define PIXEL(r,c) (((c & 0x07) + 1) + ((r & 0x07) << 3))

#define COLOR_RED 0x003F0000
#define COLOR_GRN 0x00003F00
#define COLOR_BLU 0x0000003F
#define COLOR_BLK 0x00000000

#define SCROLL_SPEED 80               //Speed at which text is scrolled
String scrollText;                    //Used to store scrolling text
volatile int8_t scrollDelay;          //Used to store scroll delay
volatile uint8_t scrollCharPos;       //Current character position in text being scrolled
volatile int8_t scrollCharCol;        //Next column in character to display
volatile int8_t scrollOffScreen;      //Extra columns required to scroll last character off screen
volatile uint32_t scrollColor;        //String color
volatile uint8_t scrollAngle;         //Color angle

//-------------------------------------------------------------------------
//Forward references
void displaySetup();
void clearDisplay();
void displayRefresh();
void drawString(String s, uint32_t color);
void drawStringRepeat();
void scrollTextLeft();
void drawCharacter(int8_t x, char ch, uint32_t color);
void displaySetStatus(uint8_t c, uint32_t color);
uint32_t displayGetPixel(uint8_t row, uint8_t col);
void displaySetPixel(uint8_t row, uint8_t col, uint32_t color);
uint32_t Wheel(byte a, uint8_t brightness);

//-------------------------------------------------------------------------
//Initialise Hardware

void displaySetup()
{
  leds.begin();
  leds.clear();
  leds.show();

  //Set up display refresh timer
  //CLK_PER = 3.3MHz (303nS)
  TCB1.CCMP = 49152;   //Refresh value for display (67Hz)
  TCB1.INTCTRL = TCB_CAPT_bm;
  TCB1.CTRLA = TCB_ENABLE_bm;
}

//-------------------------------------------------------------------------
//Timer B Interrupt handler interrupt each mS - output segments
ISR(TCB1_INT_vect)
{
  //Handle scrolling of text
  if (scrollDelay != 0)
  {
    scrollDelay--;
    if (scrollDelay == 0)
    {
      scrollDelay = SCROLL_SPEED;
      scrollTextLeft();
    }
  }

  //Clear interrupt flag
  TCB1.INTFLAGS |= TCB_CAPT_bm; //clear the interrupt flag(to reset TCB1.CNT)
}

//-------------------------------------------
// Clear all pixels on display
//-------------------------------------------

void clearDisplay()
{
  leds.clear();
}

//---------------------------------------------------------------
//Transfers the working buffer to the display buffer
void displayRefresh()
{
  leds.show();
}

//---------------------------------------------------------------
//Draw string
// s = String to display
// col = color to show
void drawString(String s, uint32_t color)
{
  if (scrollDelay == 0)
  {
    scrollText = s;
    scrollColor = color;
    scrollCharPos = 0;
    scrollCharCol = 0;
    scrollOffScreen = 0;
    scrollAngle = 0;
    scrollDelay = SCROLL_SPEED;     //Starts scrolling
  }
}

//---------------------------------------------------------------
//Repeat last string
void drawStringRepeat()
{
  if (scrollDelay == 0)
  {
    scrollCharPos = 0;
    scrollCharCol = 0;
    scrollOffScreen = 0;
    scrollDelay = SCROLL_SPEED;     //Starts scrolling
  }
}

//---------------------------------------------------------------
//Scroll text left
void scrollTextLeft()
{
  uint8_t bits;
  uint8_t mask;

  //Scroll screen buffer left
  for (int8_t c = 0; c < COLS; c++)
  {
    for (int8_t r = 0; r < ROWS; r++)
    {
      displaySetPixel(r, c, (c == (COLS-1)) ? COLOR_BLK : displayGetPixel(r, c + 1));
    }
  }

  //Fifth character column is blank for letter spacing
  if (scrollOffScreen == 0 && scrollCharCol < 4)
  {
    char ch = scrollText[scrollCharPos];
    if (ch >= 48 && ch <= 90)
    {
      //Get bits in the next column and output to buffer
      bits = pgm_read_byte(&font4x6[ch-48][scrollCharCol]);
      mask = 0x20;
      for(int8_t r = 0; r < ROWS; r++)
      {
        if (bits & mask)
        {
          displaySetPixel((ROWS-1) - r, (COLS-1), (scrollColor != 0) ? scrollColor : Wheel(scrollAngle, 64));
        }
        mask = mask >> 1;
      }
    }
  }

  if (scrollOffScreen > 0)
  {
    scrollOffScreen--;
    if (scrollOffScreen == 0)
    {
      //Stop scrolling
      scrollDelay = 0;
    }
  }
  else
  {
    scrollCharCol++;
    if (scrollCharCol == 5)
    {
      scrollCharCol = 0;
      scrollCharPos++;
      if (scrollCharPos == scrollText.length())
      {
        //All text has been outputted, just wait until it is scrolled of the screen
        scrollOffScreen = 8;
      }
    }
  }
  displayRefresh();
  scrollAngle = (scrollAngle + 4) & 0xFF;
}

//---------------------------------------------------------------
//Draw character
// x = column (0-7) 0 being farest left hand and 7 being farest right
// ch = ASCII character
// col = color to show
void drawCharacter(int8_t x, char ch, uint32_t color)
{
  uint8_t bits;
  uint8_t mask;
  if (ch >= 48 && ch <= 90)
  {
    ch = ch - 48;
    for(int c = 0; c < 6; c++)
    {
      int8_t pos = c + x;
      if (pos >= 0 && pos < COLS)
      {
        if (c == 5)
        {
          //Blank column for character spacing
          for(int r = 0; r < ROWS; r++)
          {
            leds.setPixelColor(PIXEL(((ROWS-1) - r), pos), COLOR_BLK);
          }
        }
        else
        {
          bits = pgm_read_byte(&font4x6[(int)ch][c]);
          mask = 0x20;
          for(int r = 0; r < ROWS; r++)
          {
            if (bits & mask)
            {
              leds.setPixelColor(PIXEL(((ROWS-1) - r), pos), color);
            }
            mask = mask >> 1;
          }
        }
      }
    }
  }
}

//-------------------------------------------
// Display Status LED
//  col - 0 to 7 (0 = left, 7 = right)
//  color - leds.Color(R, G, B)
//-------------------------------------------

void displaySetStatus(uint8_t c, uint32_t color)
{
  leds.setPixelColor(COLSEL + c, color);
  leds.show();
}

//-------------------------------------------
// Get a pixel on the matrix
//  row - 0 to 7 (0 = top, 7 = bottom)
//  col - 0 to 7 (0 = left, 7 = right)
//  color - leds.Color(R, G, B)
//-------------------------------------------

uint32_t displayGetPixel(uint8_t row, uint8_t col)
{
  return leds.getPixelColor(PIXEL(row, col));
}

//-------------------------------------------
// Set a pixel on the matrix
//  row - 0 to 7 (0 = top, 7 = bottom)
//  col - 0 to 7 (0 = left, 7 = right)
//  color - leds.Color(R, G, B)
//  Note: leds.show() needs to be executed to display the pixel
//-------------------------------------------

void displaySetPixel(uint8_t row, uint8_t col, uint32_t color)
{
  leds.setPixelColor(PIXEL(row, col), color);
}

//-------------------------------------------------------------------------
// Input a value 0 to 255 to get a color value.
// The colours are a transition r - g - b - back to r.
//  a = angle (0 to 255)
//  brightness - (0 to 255)
//-------------------------------------------------------------------------

uint32_t Wheel(byte a, uint8_t brightness) 
{
  uint32_t pos = a;
  uint32_t r, g, b;
  pos = 255 - pos;
  if(pos < 85) 
  {
    r = 255 - pos * 3;
    g = 0;
    b = pos * 3;
  }
  else if(pos < 170) 
  {
    pos -= 85;
    r = 0;
    g = pos * 3;
    b = 255 - pos * 3;
  }
  else
  {
    pos -= 170;
    r = pos * 3;
    g = 255 - pos * 3;
    b = 0;
  }
  if (brightness != 0)
  {
    r = (r * brightness) >> 8;
    g = (g * brightness) >> 8;
    b = (b * brightness) >> 8;
  }
  return (r << 16) | (g << 8) | b;
}