#pragma once
/*
Game.h
Tic-Tac-Toe AI
*/
//Comment out for 4x4 tic-tac-toe
//#define _3X3
//Comment out to store winning table in RAM (reduces CPU cyles in evaulation function)
//#define WINNING_MOVES_IN_RAM
//Comment out to use C version of evaluateBoard function
//#define EVAL_IN_ASSEMBLER
#include "Display.h"
#define FREE 0
#define DRAW 0
#define USER -1
#define AI 1
#define FULL -1
#define UNKNOWN -1
/*
The winningMoves array lists all possible winning sequences
Layout of LEDs
--------------
00 01 02 03
04 05 06 07
08 09 10 11
12 13 14 15
*/
#ifdef _3X3
#warning "3x3 board"
#define BOARD_SIZE 9
#define BOARD_DEPTH BOARD_SIZE //Depth that minmax tree can go
#define WIN_MOVES 8
#ifdef WINNING_MOVES_IN_RAM
const uint8_t winningMoves[WIN_MOVES][3] = {
#else
const uint8_t winningMoves[WIN_MOVES][3] PROGMEM = {
#endif
{0, 1, 2}, {3, 4, 5}, {6, 7, 8},
{0, 3, 6}, {1, 4, 7}, {2, 5, 8},
{0, 4, 8}, {2, 4, 6}
};
const uint8_t mapPhysical[BOARD_SIZE] = {0,1,2,4,5,6,8,9,10};
const uint8_t mapLogical[16] = {0,1,2,16,3,4,5,16,6,7,8,16,16,16,16,16};
#else
#warning "4x4 board"
#define BOARD_SIZE 16
#define BOARD_DEPTH 4 //Depth that minmax tree can go
#define WIN_MOVES 19
#ifdef WINNING_MOVES_IN_RAM
const uint8_t winningMoves[WIN_MOVES][4] = {
#else
const uint8_t winningMoves[WIN_MOVES][4] PROGMEM = {
#endif
{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15},
{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15},
{0, 5, 10, 15}, {3, 6, 9, 12},
{0, 1, 4, 5}, {1, 2, 5, 6}, {2, 3, 6, 7},
{4, 5, 8, 9}, {5, 6, 9, 10}, {6, 7, 10, 11},
{8, 9, 12, 13}, {9, 10, 13, 14}, {10, 11, 14, 15}
};
#endif
int8_t board[BOARD_SIZE]; //Current board
int8_t totalMoves; //Used to hold total moves in minmax tree
int8_t actualMoves; //The actual number of moves played
int8_t actualDepth; //The max depth that the minmax tree can go to
int8_t playerStarts; //0 = computer, -1 = player; used to even out minmax depth
int8_t lastWinningMove; //The winning move that caused the last win
bool gameOver; //True when game is over
int8_t result; //Function result defined as global to reduce local vars
//-------------------------------------------------------------------------
//Forward references
void setupGame(bool makeFirstMove);
void updateDisplay(bool flashOff);
bool makeMoveForUser(uint8_t move);
bool makeMoveForAI();
int8_t evaluteOutcomeForAI();
int8_t evaluteOutcomeForUser();
int8_t evaluateBoard();
//-------------------------------------------------------------------------
//Setup Game
void setupGame(bool makeFirstMove)
{
//Clear board
for (int i = 0; i < BOARD_SIZE; i++)
{
board[i] = FREE;
}
actualMoves = 0;
gameOver = false;
playerStarts = (makeFirstMove) ? 0 : -1; //When minmax depth is reduced, make depth even with who starts the game
if (makeFirstMove)
{
makeMoveForAI();
}
updateDisplay(false);
}
//-----------------------------------------------------------------------------------
// Transfer board to display buffer
// flashOff - true to not light any winning sequence
void updateDisplay(bool flashOff)
{
noInterrupts();
ledBuffer = 0;
int ix;
bool w0, w1, w2, w3;
for (int i = 0; i < BOARD_SIZE; i++)
{
#ifdef WINNING_MOVES_IN_RAM
w0 = (lastWinningMove == -1 || i == winningMoves[lastWinningMove][0]);
w1 = (lastWinningMove == -1 || i == winningMoves[lastWinningMove][1]);
w2 = (lastWinningMove == -1 || i == winningMoves[lastWinningMove][2]);
#else
w0 = (lastWinningMove == -1 || i == pgm_read_byte(&winningMoves[lastWinningMove][0]));
w1 = (lastWinningMove == -1 || i == pgm_read_byte(&winningMoves[lastWinningMove][1]));
w2 = (lastWinningMove == -1 || i == pgm_read_byte(&winningMoves[lastWinningMove][2]));
#endif
#ifdef _3X3
ix = mapPhysical[i];
if (!flashOff || (lastWinningMove != -1 && !w0 && !w1 && !w2))
{
#else
#ifdef WINNING_MOVES_IN_RAM
w3 = (lastWinningMove == -1 || i == winningMoves[lastWinningMove][3]);
#else
w3 = (lastWinningMove == -1 || i == pgm_read_byte(&winningMoves[lastWinningMove][3]));
#endif
ix = i;
if (!flashOff || (lastWinningMove != -1 && !w0 && !w1 && !w2 && !w3))
{
#endif
switch(board[i])
{
case USER: ledBuffer = ledBuffer | ((uint32_t)GRN_MASK << (ix << 1)); break;
case AI: ledBuffer = ledBuffer | ((uint32_t)RED_MASK << (ix << 1)); break;
}
}
}
interrupts();
}
//-------------------------------------------------------------------------
// Make the users move
// Returns true if move was made, false if square is already taken
bool makeMoveForUser(uint8_t move)
{
#ifdef _3X3
move = mapLogical[move];
if (move == 16)
{
return false;
}
#endif
bool result = false;
if (board[move] == FREE)
{
board[move] = USER; //Make the move
actualMoves++; //Keep count of all moves
result = true;
}
return result;
}
//-------------------------------------------------------------------------
// Make a move
// Returns true if move was made, false if no moves left
// 2m 30sec
bool makeMoveForAI()
{
int8_t bestMove = UNKNOWN;
if (actualMoves == 0)
{
bestMove = random(BOARD_SIZE); //Board empty so pick a square
}
else if (actualMoves == BOARD_SIZE)
{
return false; //No moves left
}
else
{
totalMoves = actualMoves;
actualDepth = min(actualMoves + playerStarts + BOARD_DEPTH, BOARD_SIZE); //Depth of minmax tree
for (int i = 0; i < BOARD_SIZE; i++)
{
if (board[i] == FREE)
{
board[i] = AI; //Make move
totalMoves++;
//updateDisplay(false);
//delay(500);
//noInterrupts();
result = evaluteOutcomeForUser(); //Find best USER counter move
//interrupts();
board[i] = FREE; //Restore board
totalMoves--;
if (result == AI)
{
bestMove = i; //No need to test other squares as this is a winning move
break;
}
else if (result == DRAW)
{
bestMove = i; //Best outcome is a draw otherwise a loss
}
}
if (bestMove == UNKNOWN)
{
bestMove = random(BOARD_SIZE);
while (board[bestMove] != FREE)
{
bestMove = (bestMove + 1) % BOARD_SIZE;
}
}
}
}
board[bestMove] = AI; //Make the best move we have
actualMoves++; //Keep count of all moves
return true;
}
//-------------------------------------------------------------------------
// Make a move and evaluate the outcome
// This uses the recursive minmax algorithm with pruning
// Returns DRAW if no winner, USER if user wins, AI if AI wins
// Note: result is defined as a global variable to save stack space during recursion
// Also the minmax function is split into two functions to save passing which player
// that is being evaulated via a parameter which is the case when using a single function.
//__attribute__((optimize("O0")))
int8_t evaluteOutcomeForAI()
{
int8_t bestResult = USER;
result = evaluateBoard();
if (result != DRAW || totalMoves == actualDepth)
{
return result; //User or AI has won
}
else
{
for (int i = 0; i < BOARD_SIZE; i++)
{
if (board[i] == FREE)
{
board[i] = AI; //Make move
totalMoves++;
result = evaluteOutcomeForUser(); //Find best AI move for this one
board[i] = FREE; //Restore board
totalMoves--;
if (result == AI)
{
return AI; //No need to test other squares as this is a winning move
}
else if (result == DRAW) //Next best result is a draw
{
bestResult = DRAW;
}
}
}
}
return bestResult;
}
//__attribute__((optimize("O0")))
int8_t evaluteOutcomeForUser()
{
int8_t bestResult = AI;
result = evaluateBoard();
if (result != DRAW || totalMoves == actualDepth)
{
return result; //User or AI has won
}
else
{
for (int i = 0; i < BOARD_SIZE; i++)
{
if (board[i] == FREE)
{
board[i] = USER; //Make move
totalMoves++;
result = evaluteOutcomeForAI(); //Find best AI move for this one
board[i] = FREE; //Restore board
totalMoves--;
if (result == USER)
{
return USER; //No need to test other squares as this is a winning move
}
else if (result == DRAW) //Next best result is a draw
{
bestResult = DRAW;
}
}
}
}
return bestResult;
}
//-------------------------------------------------------------------------
// Tests whether either the user or AI has won
// Returns DRAW if no winner, USER if user won, AI if AI won
#ifdef EVAL_IN_ASSEMBLER
int8_t evaluateBoard()
{
asm (
//Backup board pointer for quick restoration
"movw r6, r26 \n" //1 cycle
"loop: \n"
//Copying address of next winningMoves block into Z
"movw r30, r28 \n" //1 cycle
//Get the first board index into tmp
#ifdef WINNING_MOVES_IN_RAM
"ld __tmp_reg__, Z+ \n" //2 cycles
#else
"lpm __tmp_reg__, Z+ \n" //3 cycles
#endif
//Restore X pointer and add tmp
"movw r26, r6 \n" //1 cycle
"add r26, __tmp_reg__ \n" //1 cycle
"adc r27, __zero_reg__ \n" //1 cycle
//store board[winningMoves[y][0]] into r2
"ld r2, X \n" //2 cycles
//if r2 is 0 (draw) skip this test
"tst r2 \n" //1 cycle
"breq next \n" //1 (false), 2 (true) cycles
//Now test if board[winningMoves[y][1]] into r2
#ifdef WINNING_MOVES_IN_RAM
"ld __tmp_reg__, Z+ \n" //2 cycles
#else
"lpm __tmp_reg__, Z+ \n" //3 cycles
#endif
"movw r26, r6 \n" //1 cycle
"add r26, __tmp_reg__ \n" //1 cycle
"adc r27, __zero_reg__ \n" //1 cycle
"ld r3, X \n" //2 cycles
//board[winningMoves[y][1]] is now in r3 so compare with r2
"cp r2, r3 \n" //1 cycle
//if not equal, skip this test
"brne next \n" //1 (false), 2 (true) cycles
//Now test if board[winningMoves[y][2]] into r2
#ifdef WINNING_MOVES_IN_RAM
"ld __tmp_reg__, Z+ \n" //2 cycles
#else
"lpm __tmp_reg__, Z+ \n" //3 cycles
#endif
"movw r26, r6 \n" //1 cycle
"add r26, __tmp_reg__ \n" //1 cycle
"adc r27, __zero_reg__ \n" //1 cycle
"ld r3, X \n" //2 cycles
//board[winningMoves[y][2]] is now in r3 so compare with r2
"cp r2, r3 \n" //1 cycle
//if not equal, skip this test
"brne next \n" //1 (false), 2 (true) cycles
#ifndef _3X3
//Now test if board[winningMoves[y][3]] into r2
#ifdef WINNING_MOVES_IN_RAM
"ld __tmp_reg__, Z+ \n" //2 cycles
#else
"lpm __tmp_reg__, Z+ \n" //3 cycles
#endif
"movw r26, r6 \n" //1 cycle
"add r26, __tmp_reg__ \n" //1 cycle
"adc r27, __zero_reg__ \n" //1 cycle
"ld r3, X \n" //2 cycles
//board[winningMoves[y][3]] is now in r3 so compare with r2
"cp r2, r3 \n" //1 cycle
//if not equal, skip this test
"brne next \n" //1 (false), 2 (true) cycles
#endif
//We have found a matching row
"mov __tmp_reg__, r2 \n" //1 cycle
"rjmp done \n" //2 cycles
"next: \n"
#ifdef _3X3
//increase winningMoves by 3
"adiw r28, 3 \n" //2 cycles
#else
//increase winningMoves by 4
"adiw r28, 4 \n" //2 cycles
#endif
//decrease WIN_MOVES and loop until zero
"dec %3 \n" //1 cycle
"brne loop \n" //1 (false), 2 (true) cycles
//No matches so return DRAW
"clr __tmp_reg__ \n" //1 cycle
"done: \n"
//return __tmp_reg__
"mov %0, __tmp_reg__ \n" //1 cycle
: "=a" (result)
: "x" (board), "y" (winningMoves), "a" (WIN_MOVES)
: "r2", "r3", "r6", "r7", "r30", "r31"
);
return result;
}
#else
#ifdef WINNING_MOVES_IN_RAM
// C version that the above assembly language routine replaces
int8_t evaluateBoard(int* row)
{
const uint8_t* cellPtr;
lastWinningMove = -1;
for (uint8_t y = 0; y < WIN_MOVES; y++)
{
cellPtr = (const uint8_t*)&winningMoves[y];
result = board[*cellPtr++];
if (result != FREE)
{
if (result == board[*cellPtr++])
{
if (result == board[*cellPtr++])
{
#ifndef _3X3
if (result == board[*cellPtr++])
{
#endif
lastWinningMove = y;
return result;
#ifndef _3X3
}
#endif
}
}
}
}
return DRAW;
}
#else
// C version that the above assembly language routine replaces
int8_t evaluateBoard()
{
const uint8_t* cellPtr;
lastWinningMove = -1;
for (uint8_t y = 0; y < WIN_MOVES; y++)
{
cellPtr = (const uint8_t*)&winningMoves[y];
result = board[pgm_read_byte(cellPtr++)];
if (result != FREE)
{
if (result == board[pgm_read_byte(cellPtr++)])
{
if (result == board[pgm_read_byte(cellPtr++)])
{
#ifndef _3X3
if (result == board[pgm_read_byte(cellPtr++)])
{
#endif
lastWinningMove = y;
return result;
#ifndef _3X3
}
#endif
}
}
}
}
return DRAW;
}
#endif
#endif
Comments