This is my first microcontroller project (aside from a couple of Hello World's after I received my Tiva), but I've been programming professionally for more than 30 years -- less so in the last decade.
Tic Tac Toe, called noughts and crosses elsewhere in the world, is a pretty simple strategy game, and I thought it would be well suited for a first project.
tic tac toe by joelfinkle, on Flickr
There are 18 LEDs (9 each of red and green), not counting the onboard RGB (used for status). While there are plenty of pins on the Tiva, it seemed worth learning Charlieplexing.
That provided an additional challenge, getting LEDs to line up nicely in the limited space of a standard breadboard, while getting in all the wires. I mostly succeeded, although the grid is a little skewed.
The project uses a 4x4 keypad bought off Amazon for under $2 shipped (not realizing it would take weeks to arrive from China).
There are two slider switches used to determine whether there is a computer player, and whether the computer is first or second. I could probably modify it to have both players be computer, but given that the strategy is deterministic (nothing random), it would be pretty dull -- every game would end the same way.
I decided to program using Energia, mainly because I had trouble getting the TI dev environment to work, and I'm lazy.
I'd looked at [roadrunner]'s charlieplexing module, but it added a lot of unneeded complexity, and I settled for a simple tick routine that changed which cell of the tic tac toe board it was looking at each time around the loop routine.
i plan on upgrading the code to use more direct access to the pins (like [roadrunner] does), but thought I'd get it to work on a more pure Wiring program first.
The strategy is clearly laid out in the code, using the suggestion of http://www.instructables.com/id/How-to-make-a-TIC-TAC-TOE-game-using-C/all/?lang=zh'>this Instructables post of storing a game state as empty=2, player 1=3 and player 2=5, and multiplying cell values together to get a state (winning is 27 or 125). I enhanced it to look for fork and fork-blocking moves.
The onboard LED is blinked at intervals (also done using a routine called from loop, but could be an interrupt in future versions), with different colors to indicate player's turn, invalid move, win of player 1 or 2 and cat's game (draw).
Enjoy!
////////////////////////////////////////////////////////////////////////
//
// Tic Tac Toe for Tiva - Energia Implementation
//
// (CC) Creative Commons Attribution Non-Commercial 2013 Joel Finkle
// Recipients of this code may copy, distribute, display, and perform the work and make derivative works based on it only for noncommercial purposes
//
// Hardware requirements:
// TI Tiva C development board
// 18 LEDs, 9 each of red and green
// 4x4 keypad
// Five 330-ohm resistors
// Two slider switches
// Breadboard and wires
#include <Keypad.h>
// Game state globals
int curPos = 0;
int curScanRow = 0;
int curPlayer = 0; // start with player 1
int blinkType = 0; // 0 = no blink, 1 = error, 2 = P1 win, 3 = P2 win, 4 = P1 turn, 5 = p2 turn, 6 = Cat's Game
int blinkCtr = -1;
int blinkTimer = 0;
long blinker = -1000;
int game[9] = {2,2,2,2,2,2,2,2,2}; // 2 = neither, 3 = P1, 5 = P2 for items 0-8
int humans[2] = {1,1};
int movesmade = 0;
boolean stillplaying = true;
// Constants for the value of a given move
#define WINMOVE 0
#define BLOCKMOVE 1
#define FORKMOVE 2
#define FORKBLOCKMOVE 3
#define CENTERMOVE 4
#define OPPOMOVE 5
#define CORNERMOVE 6
#define EDGEMOVE 7
#define NOMOVE 999
// Charlieplexed LED Data
#define PIN_COUNT 5
int pinlist[PIN_COUNT] = {PE_1,PE_2,PE_3,PE_4,PE_5};
// pinpairs provides a shortcut for charlieplexing,
// since the alternate players use the same pair of pins with reversed polarity.
// Each of the nine cells indicates the pair of pins in pinlist
// with the direction indicated by the player.
// Pins were chosen to all be in one set, for future changes to use register operations
// instead of the Wiring routines
int pinpairs[3][3][2] = {
{ { 0, 1 }, { 1, 2 }, { 2, 3 } },
{ { 3, 4 }, { 4, 0 }, { 0, 2 } },
{ { 2, 4 }, { 4, 1 }, { 1, 3 } }
};
// Keypad data
const byte ROWS = 4; // use 4X4 keypad for both instances
const byte COLS = 4;
char keys[ROWS][COLS] = {
{'1','2','3','A'},
{'4','5','6','B'},
{'7','8','9','C'},
{'*','0','#','D'}
};
// Pins chosen below were the only set of eight in as row that don't have another function
// so that the keypad's header could be plugged directly into the Tiva board
byte rowPins[ROWS] = {38,37,36,35}; //connect to the row pinouts of the keypad
byte colPins[COLS] = {34,33,32,31}; //co/nnect to the column pinouts of the keypad
Keypad keypad( makeKeymap(keys), rowPins, colPins, ROWS, COLS );
////////////////////////////////////////////////////////////////////////
// Setup - set the initial game state, other than the data initialization above
void setup()
{
// setup code here, to run once:
int i = 0;
for (i=0;i<PIN_COUNT;i++) { pinMode(pinlist[i], INPUT); }
pinMode(PA_3, INPUT); // Play against computer?
pinMode(PA_2, INPUT); // Which player is computer?
pinMode(RED_LED, OUTPUT); // all three of these for statuses
pinMode(GREEN_LED, OUTPUT);
pinMode(BLUE_LED, OUTPUT);
if (digitalRead(PA_3) == LOW) { // Yes, play against computer
humans[digitalRead(PA_2) == HIGH ? 0 : 1] = 0; // set either player 1 or player 2 as computer player
}
updateBlink(blinkCtr, blinkType, blinkTimer);
// Player 1's turn
blinkType = 4; // 0 = no blink, 1 = error, 2 = P1 win, 3 = P2 win, 4 = P1 turn, 5 = p2 turn
blinkCtr = 6;
blinkTimer = 250;
updateBlink(blinkCtr, blinkType, blinkTimer);
}
////////////////////////////////////////////////////////////////////////
// loop - main event loop
void loop()
{
int move = NOMOVE;
// Give time to the charlieplex display
tickDisplay(curPos++);
if (curPos > 8) { curPos = 0; }
// Give time to the blinker handler
updateBlink(blinkCtr, blinkType, blinkTimer);
// Whose turn is it? Fetch a move
if (stillplaying) {
if (humans[curPlayer]) {
move = humanplayer();
} else {
move = computerplayer();
}
}
// If a move occurred (which should always happen if it's the computer's turn, but might not have yet for human)...
if (move != NOMOVE) {
// Was it a winning move?
if (move == WINMOVE) { // game over
blinkType = 2 + curPlayer;
blinkCtr = 10;
blinkTimer = 250;
stillplaying = false;
} else {
// If not a winning move, update the game state
movesmade++;
// cats game
if (movesmade > 8) {
blinkType = 6;
blinkCtr = 6;
blinkTimer = 250;
stillplaying = false;
// or need another move
} else {
switchplayer();
}
}
}
}
////////////////////////////////////////////////////////////////////////
// humanplayer - Fetch a move from the keypad
int humanplayer() {
char key = keypad.getKey();
int button = -1;
int move = NOMOVE;
// The keypad is a 16-key pad, ignore right column (A-D) and bottom row (* 0 #)
if (key >= '1' && key <= '9') { button = (byte)key - 49; } // subtract 1 extra to make it 0-based
// If we got real input...
if (button >= 0) {
// Make sure the position isn't already used
if (game[button] != 2) {
// error -- already in use
blinkCtr = 4; // three times on and off
blinkType = 1;
blinkTimer = 250; // milliseconds
move = NOMOVE;
// Then update the game board, and check whether it's a winning move
} else {
game[button] = curPlayer ? 5 : 3; // set to 5 for player 2 (value 1), 3 for player 1 (value 0)
// did they win?
move = bestmove(button, curPlayer, 0);
}
return move;
} else {
return NOMOVE;
}
}
////////////////////////////////////////////////////////////////////////
// computerplayer - calculate best move
int computerplayer() {
int best = NOMOVE;
int bestpos = -1;
for (int j=0; j<9; j++) {
// Since this can be time consuming, keep the screen updated
tickDisplay(curPos++);
if (curPos > 8) { curPos = 0; }
updateBlink(blinkCtr, blinkType, blinkTimer);
// end of screen update
// Only check the value of a move where we actually can move
if (game[j] == 2) { // spot is empty
int thismove = bestmove(j, curPlayer, 1);
// If this move is better than other ones we've chosen, keep it
if (thismove < best) { // lower values are better
bestpos = j;
best = thismove;
}
}
}
// Update board and return the quality of the move (which indicates winning)
game[bestpos] = curPlayer ? 5 : 3; // set to 5 for player 2 (value 1), 3 for player 1 (value 0)
return best;
}
////////////////////////////////////////////////////////////////////////
// switchplayer - blink for the other guy
void switchplayer() {
// change players -- this shamefully works on globals
curPlayer ^= 1; // XOR toggles between 0 and 1
blinkType = 4 + curPlayer; // 4 = P1 turn, 5 = p2 turn
blinkCtr = 6;
blinkTimer = 250;
}
////////////////////////////////////////////////////////////////////////
// tickDisplay -- give time to the Charlieplex
void tickDisplay( int position) { // display the next LED
if (game[position] != 2) { // there's something there
displaySquare( position % 3, position / 3, (game[position])); // pass position value to permit clearing
}
if (game[position] == 8) { game[position] = 2; } // reset if needed
}
////////////////////////////////////////////////////////////////////////
// displaySquare -- update the output lines for the particular cell
// TODO: switch to using internal registers instead of Wiring routines, for speed
void displaySquare( int row, int col, int value) {
int player = 0;
switch (value) {
case (3) : player = 0;
break;
case (5) : player = 1;
}
// set all pins to low and input to ensure that we don't have old junk sitting around
for (int i = 0; i < PIN_COUNT; i++) { digitalWrite(pinlist[i], LOW); pinMode( pinlist[i], INPUT);}
// set particular pins to output, and raise one of them high
if (value != 8) { // don't do this if clearing
pinMode(pinlist[pinpairs[row][col][0]], OUTPUT);
pinMode(pinlist[pinpairs[row][col][1]], OUTPUT);
digitalWrite( pinlist[pinpairs[row][col][player]], HIGH);
}
}
////////////////////////////////////////////////////////////////////////
// updateBlink - change the blinker periodically.
//
// Todo: Change to interrupt-driven blinker
void updateBlink( int &bCount, int bType, int bTimer) {
if (bCount < 0) {
blinker = 0;
return;
}
// If bTimer expired then
if (blinker + bTimer < millis()) { // timer expired
// a) Toggle LED based on bType
switch (bType) {
case (0) : // nothing
digitalWrite(RED_LED, LOW);
digitalWrite(GREEN_LED, LOW);
digitalWrite(BLUE_LED, LOW);
break;
case (1) : // error - yellow
digitalWrite(RED_LED, (bCount & 1) ? LOW : HIGH);
digitalWrite(GREEN_LED, (bCount & 1) ? LOW : HIGH);
break;
case (2) : // P1 Win - alternate red and blue
digitalWrite(RED_LED, (bCount & 1) ? LOW : HIGH);
digitalWrite(BLUE_LED, (bCount & 1) ? HIGH : LOW);
break;
case (3) : // P2 win - alternate green and blue
digitalWrite(GREEN_LED, (bCount & 1) ? LOW : HIGH);
digitalWrite(BLUE_LED, (bCount & 1) ? HIGH : LOW);
break;
case (4) : // P1 turn - red
digitalWrite(RED_LED, (bCount & 1) ? LOW : HIGH);
break;
case (5) : // P2 turn - green
digitalWrite(GREEN_LED, (bCount & 1) ? LOW : HIGH);
break;
case (6) : // Cat's Game - alternate yellow and blue
digitalWrite(RED_LED, (bCount & 1) ? LOW : HIGH);
digitalWrite(GREEN_LED, (bCount & 1) ? LOW : HIGH);
digitalWrite(BLUE_LED, (bCount & 1) ? HIGH : LOW);
}
// Decrement bCount
bCount--;
if (bCount < 0) {
digitalWrite(GREEN_LED, LOW);
digitalWrite(RED_LED, LOW);
digitalWrite(BLUE_LED, LOW);
blinker = -1;
} else {
// c) reset bTimer
blinker = millis();
}
}
}
/*
Strategy: Wikipedia suggests the following priority:
1) Win: If the player has two in a row, they can place a third to get three in a row. (same as posswin)
2) Block: If the [opponent] has two in a row, the player must play the third themself to block the opponent.
3) Fork: Create an opportunity where the player has two threats to win (two non-blocked lines of 2).
4) Blocking an opponent's fork:
Option 1: The player should create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork.
For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well,
"O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)
Option 2: If there is a configuration where the opponent can fork, the player should block that fork.
5) Center: A player marks the center. (If it is the first move of the game, playing on a corner gives "O" more opportunities to make a mistake and may therefore be the better choice;
however, it makes no difference between perfect players.)
6) Opposite corner: If the opponent is in the corner, the player plays the opposite corner.
7) Empty corner: The player plays in a corner square.
8) Empty side: The player plays in a middle square on any of the 4 sides.
The bestmove routine here uses 2 for an empty cell, 3 for a player-one cell, 5 for a player 2 cell, and calculates the product of three cells in a row
There are four possible results from any cell:
Three in a row,
three in a column,
three in a sinister diagonal (top right to bottom left),
three in a dexter diagonal (top left to bottom right)
Possible products for any set of 3 cells (row, col, sinister, dexter) a*b*c:
8 Nothing there (don't care)
12 One cell of player 1 (low priority)
18 Two of player 1, one empty = could indicate a fork if there's another
20 One cell of player 2 (low priority)
27 Three of player 1 = winner
30 One Player 1, One Player 2, One Empty = could indicate an opponent fork that could be blocked, if there's another
45 Two of player 1, one Player 2 = block for player 2
50 Two of player 2, one empty = forkable
75 Two of player 2, one Player 1 = block for player 1
125 Three of player 2 = winner
999 Invalid (i.e. looking for sinister when in any cell except the right to left diagonal [2,4,6])
So for each give empty square, look at the set of row, col, sin, dex
a) if there's an 27/125 (for player 1 or 2), choose it and win
if there are any 75/45, choose it and block
c) if there are two 18/50, choose it and fork
d) if there are two 30, choose it and prevent fork
e) if given square is a corner, and opposite corner is not self, choose it
f) if given square is corner, take it
g) if given square is edge, take it
*/
////////////////////////////////////////////////////////////////////////
// bestmove - use above strategy to find the best possible move
// TODO: make the first move more random? You can still force a win or cats from any cell
int bestmove(int cell, int player, boolean testcell) {
int row = int(cell / 3) * 3;
int col = cell % 3;
int oldCell = game[cell];
int forkcnt = 0;
int forkblkcnt = 0;
int thismove = NOMOVE;
boolean block = false;
int forks = 0;
int forkblocks = 0;
// If testcell is true, we're looking for a best move, versus just whether we won
// in which case, pretend the move is made by filling the cell
if (testcell) { game[cell] = (player ? 5 : 3); }
// Check the four directions: Row, Col, Dexter, Sinister
for (int dir=0; dir<4; dir++) {
switch (dir) {
case 0: // row
thismove = game[row] * game[row+1] * game[row+2];
break;
case 1: // column
thismove = game[col] * game[col+3] * game[col+6];
break;
case 2: // dexter diagonal
if (cell % 4 == 0) { // cells 0, 4 or 8
thismove = game[0] * game[4] * game[8];
} else {
thismove = NOMOVE;
}
break;
case 3: // sinister diagonal
if (cell == 2 || cell == 4 || cell == 6) { // no cute calculation here
thismove = game[2] * game[4] * game[6];
} else {
thismove = NOMOVE;
}
}
// evaluate results
if (thismove == 125 || thismove == 27) { // winner
if (testcell) { game[cell] = oldCell; }
return WINMOVE; // no need to keep testing, we've got a winner
} else if ((thismove == 75 && player == 0) || (thismove == 45 && player == 1)) { // blocker, keep track
block = true;
} else if (thismove == 18 || thismove == 50) { // possible fork
forks++;
} else if (thismove == 30) { // possible forkblock
forkblocks++;
}
}
// now that we've looked at all 4, what's the best outcome of this spot (we've already returned if we would win)
// BLOCK
if (block) {
thismove = BLOCKMOVE;
// FORK if two directions found
} else if (forks > 1) {
thismove = FORKMOVE;
// FORK BLOCK if two directions found
} else if (forkblocks > 1) {
thismove = FORKBLOCKMOVE;
// CENTER
} else if (cell == 4) {
thismove = CENTERMOVE;
// OPPOSITE CORNER
} else if (cell % 2 == 0) { // all the corners are even, plus center which we already counted
if (game[3*((row+2) & 3) + ((col+2) & 3)] != 2) {
thismove = OPPOMOVE;
} else {
// CORNER
thismove = CORNERMOVE;
}
// EDGE
} else {
thismove = EDGEMOVE;
}
// Reset the test cell
if (testcell) { game[cell] = oldCell; };
return thismove;
}
Schematic -- if anyone has a Fritzing file for the Tiva/Stellaris, I'd appreciate it. I had to hack the SVG files for the Launchpad headers to get this to work, and it's still a little funky.
tictactoe with keypad_schem by joelfinkle, on Flickr
joelfinkle got a reaction from abecedarian in [Energia Library] Charlieplexing (and more) library