What Matters 2 Me

The continuation of my 3D TicTacToe LED Matrix project.  See Introduction and Part 2.

Download the code directly here: LED_Matrix_TTT4.pde

Some general notes:

1. The AI is based on game theory taken from a book I read about 20 years ago. Unfortunately I don’t remember the name of it. It uses a Minimax algorithm as well as Alpha-beta pruning to decrease the number of nodes that need to be evaluated. Wikipedia offers a concise description of these with many external links. I spent about a month learning the algorithms and coding them, so I’m sure they can be greatly enhanced, especially since more than 20 years has past. However, I am proud to say that pitting this program up against another 3D TTT I found online, that mine trounced the other.

2. I wanted the LED matrix cube to be constantly displaying the player LED spot selection, the current cube moves, or the computer thinking (LEDs going on and off). In order to do this, even while the Arduino is off doing other things, I needed to use interrupts.  Using the MsTimer2 library I was able to set up a routine, disp_LED_cube, that was called every 200 ms with 1 of 4 states:

• state 0: Default display of all moves
• state 1: setting up player’s move
• state 3: blinking last computer move
• state 4: computer “thinking”

3. The current program uses a keypad to make the moves. The keys 1-4 are for selection of the player’s move. It first uses a ‘wall’ to select the z-direction, with the keys moving the wall. After the proper wall is selected, the ’5′ key will then lock-in that wall, and display a column that represents the y-direction. Again, the 1-4 keys allow for the selection of the wished-upon column. Player then pushes ’5′ key to lock-in column. Finally, user selects for the specific LED in column they wish to use as their move. Pressing the ’5′ key will begin the Arduino deciding its move. I’m currently working on code to use a thumbstick rather than the keypad.

4. The code is GPL. Please use it as you like and definitely improve upon it. I would, of course, really like you to credit me for the work I’ve put into it should you use it.

Here is the code:

/*

	LED_Matrix_TTT4.C - An AI version of Tic-Tac-Toe, played on a 4x4x4 LED matrix
        powered by an Arduino

    Copyright (C) 2011  Jeffrey R. Gilmour, Ph.D.

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <Sprite.h>
#include <Matrix.h>
#include <MsTimer2.h>	// Uses pins 3 & 11, so DON'T USE those

const int loadPin = 4;
const int clockPin = 5;
const int dataPin = 6;

Matrix myMatrix = Matrix(dataPin, clockPin, loadPin);

#define FALSE 0
#define TRUE !FALSE
boolean OLedsOn = TRUE;

char cube0[4][4][4], cube1[4][4][4], cube2[4][4][4], cube3[4][4][4], human_symbol='X', comp_symbol='O';

const int period = 200;

const int numRows = 2;
const int rowPins[numRows] = { 7, 8 };		// Keypad pins 1 & 2, attached to Arduino pins 7 & 8

const int numCols = 3;
const int colPins[numCols] = { 9, 10, 12 };	// Keypad pins 5, 6 & 7

const int debounceTime = 200;

const char keymap[numRows][numCols] = {		// USE PINS 1, 2, 5, 6, 7 on keypad
	{ '1', '2', '3' },
	{ '4', '5', '6' }
};

char key = 0;

int state = 0, state1x = 5, state1y = 5, state1z = 5;
int	bestmovex, bestmovey, bestmovez;

char getKey() {
	key = 0;	

	for (int column = 0; column < numCols; column++) {
		digitalWrite(colPins[column], LOW);
		for (int row = 0; row < numRows; row++) {
			if(digitalRead(rowPins[row]) == LOW) {
				delay(debounceTime);
				while(digitalRead(rowPins[row]) == LOW) ;
				key = keymap[row][column];
			}
		}
		digitalWrite(colPins[column], HIGH);
	}

	return key;
}

char check(char board[4][4]) {

	int i;

	for (i=0;i<4;i++)		/* check rows */
		if (board[i][0]==board[i][1] &&
		   board[i][0]==board[i][2] &&
		   board[i][0]==board[i][3]) if (board[i][0]!=' ')
		   	return board[i][1];

	for (i=1;i<=4;i++)		/* check columns */
		if (board[0][i]==board[1][i] &&
		   board[0][i]==board[2][i] &&
		   board[0][i]==board[3][i]) if (board[0][i]!=' ')
		   	return board[1][i];

	/* test diagonals */
	if (board[0][0]==board[1][1] && board[1][1]==board[2][2] &&
	   board[2][2]==board[3][3] && board[0][0]!=' ')
		return board[1][1];

	if (board[0][3]==board[1][2] && board[1][2]==board[2][1] &&
	   board[2][1]==board[3][0] && board[0][3]!=' ')
		 return board[1][2];

	return ' ';
}

void disp_LED_cube(void) {

	if (state == 0) {		// Default display of all moves
		for (int z=0;z<4;z++)
			for (int y=0;y<4;y++)
				for (int x=0;x<4;x++) {
					if (OLedsOn) {
						if (cube0[x][y][z] == 'O') {
							if (z == 0) {
								myMatrix.write(y, x, LOW);
							} else if (z == 1) {
								myMatrix.write(y, x+4, LOW);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, LOW);
							} else if (z == 3) {
								myMatrix.write(y+4, x, LOW);
							}
						}
					} else {
						if (cube0[x][y][z] != ' ') {
							if (z == 0) {
								myMatrix.write(y, x, HIGH);
							} else if (z == 1) {
								myMatrix.write(y, x+4, HIGH);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, HIGH);
							} else if (z == 3) {
								myMatrix.write(y+4, x, HIGH);
							}
						}
					}
				}
		OLedsOn = !OLedsOn;
	}

	if (state == 1) {	// setting up player's move
		myMatrix.clear();
		if (state1z < 5) {

						if (state1z == 0) {
							myMatrix.write(state1y, state1x, HIGH);
						} else if (state1z == 1) {
							myMatrix.write(state1y, state1x+4, HIGH);
						} else if (state1z == 2) {
							myMatrix.write(state1y+4, state1x+4, HIGH);
						} else if (state1z == 3) {
							myMatrix.write(state1y+4, state1x, HIGH);
						}

		} else
		if (state1y < 5) {
				for (int z=0;z<4;z++)
						if (z == 0) {
							myMatrix.write(state1y, state1x, HIGH);
						} else if (z == 1) {
							myMatrix.write(state1y, state1x+4, HIGH);
						} else if (z == 2) {
							myMatrix.write(state1y+4, state1x+4, HIGH);
						} else if (z == 3) {
							myMatrix.write(state1y+4, state1x, HIGH);
						}
		} else
		if (state1x < 5) {
				for (int z=0;z<4;z++)
					for (int y=0;y<4;y++) {
						if (z == 0) {
							myMatrix.write(y, state1x, HIGH);
						} else if (z == 1) {
							myMatrix.write(y, state1x+4, HIGH);
						} else if (z == 2) {
							myMatrix.write(y+4, state1x+4, HIGH);
						} else if (z == 3) {
							myMatrix.write(y+4, state1x, HIGH);
						}
					}
		}
	}

	if (state == 3) {		// blinking last computer move

		if (OLedsOn) {
			if (bestmovez == 0) {
				myMatrix.write(bestmovey, bestmovex, LOW);
			} else if (bestmovez == 1) {
				myMatrix.write(bestmovey, bestmovex+4, LOW);
			} else if (bestmovez == 2) {
				myMatrix.write(bestmovey+4, bestmovex+4, LOW);
			} else if (bestmovez == 3) {
				myMatrix.write(bestmovey+4, bestmovex, LOW);
			}
		} else {
			if (bestmovez == 0) {
				myMatrix.write(bestmovey, bestmovex, HIGH);
			} else if (bestmovez == 1) {
				myMatrix.write(bestmovey, bestmovex+4, HIGH);
			} else if (bestmovez == 2) {
				myMatrix.write(bestmovey+4, bestmovex+4, HIGH);
			} else if (bestmovez == 3) {
				myMatrix.write(bestmovey+4, bestmovex, HIGH);
			}
		}
		OLedsOn = !OLedsOn;
	}

	if (state == 4) {		// computer "thinking"
		myMatrix.clear();
		for (int z=0;z<4;z++)
			for (int y=0;y<4;y++)
				for (int x=0;x<4;x++) {
					if (OLedsOn) {
						if (cube3[x][y][z] == 'O') {
							if (z == 0) {
								myMatrix.write(y, x, LOW);
							} else if (z == 1) {
								myMatrix.write(y, x+4, LOW);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, LOW);
							} else if (z == 3) {
								myMatrix.write(y+4, x, LOW);
							}
						}
					} else {
						if (cube3[x][y][z] != ' ') {
							if (z == 0) {
								myMatrix.write(y, x, HIGH);
							} else if (z == 1) {
								myMatrix.write(y, x+4, HIGH);
							} else if (z == 2) {
								myMatrix.write(y+4, x+4, HIGH);
							} else if (z == 3) {
								myMatrix.write(y+4, x, HIGH);
							}
						}
					}
				}
		OLedsOn = !OLedsOn;
	}

}

char check_cube(char cube[4][4][4]) {

	int x, y, z, n=0;
	char done, board[4][4];

	for (z=0;z<4;z++) {	/* boards in Z direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][y][z];
		done=check(board);
		if (done!=' ') return done;
	}

	for (z=0;z<4;z++) {	/* boards in Y direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][z][y];
		done=check(board);
		if (done!=' ') return done;
	}

	for (z=0;z<4;z++) {	/* boards in X direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[z][y][x];
		done=check(board);
		if (done!=' ') return done;
	}

	/* 3D diagonal 1 */
	if (cube[0][0][0]==cube[1][1][1] && cube[0][0][0]==cube[2][2][2]
		&& cube[0][0][0]==cube[3][3][3] && cube[0][0][0]!=' ')
		return cube[0][0][0];

	/* 3D diagonal 2 */
	if (cube[0][0][3]==cube[1][1][2] && cube[0][0][3]==cube[2][2][1]
		&& cube[0][0][3]==cube[3][3][0] && cube[0][0][3]!=' ')
		return cube[0][0][3];

	/* 3D diagonal 3 */
	if (cube[3][0][0]==cube[2][1][1] && cube[3][0][0]==cube[1][2][2]
		&& cube[3][0][0]==cube[0][3][3] && cube[3][0][0]!=' ')
		return cube[3][0][0];

	/* 3D diagonal 4 */
	if (cube[0][3][0]==cube[1][2][1] && cube[0][3][0]==cube[2][1][2]
		&& cube[0][3][0]==cube[3][0][3] && cube[0][3][0]!=' ')
		return cube[0][3][0];

	for (z=0;z<4;z++)	/* if no spaces are empty, game is a draw */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				if (cube[x][y][z]==' ') n++;
	if (n==0) {
		// Game is a draw - how to communicate to player?
		loop();
	}

	return done;
}

void copy_cube(char b2[4][4][4], char b1[4][4][4]) {

	int x,y,z;

	for (z=0;z<4;z++)
		for (y=0;y<4;y++)
			for (x=0;x<4;x++) b2[x][y][z]=b1[x][y][z];

}

void get_computer_move(void) {

	long int	s0=-100000, s1, s2;
	int		test=0, x1, y1, z1, x2, y2, z2, x3, y3, z3, NoGood, NoGood2;
	int		score;
	char	done;

	state = 4;		// computer "thinking" LED display

	for (z1=0;z1<4;z1++)
	    for (y1=0;y1<4;y1++)
		for (x1=0;x1<4;x1++) {

		    s1=100000;
		    NoGood=FALSE;

		    if (cube0[x1][y1][z1]==' ') {
			copy_cube(cube1,cube0);
			cube1[x1][y1][z1]=comp_symbol;

			done = check_cube(cube1);	// Computer has WON!
			if (done==comp_symbol) {
				bestmovex = x1;
				bestmovey = y1;
				bestmovez = z1;

				state = 3;		// blinking last move of computer
				while (getKey() == 0) ;
				state = 0;

				copy_cube(cube0,cube1);

				while (getKey() == 0) ;
				loop();

			}

			for (z2=0;z2<4 && !NoGood;z2++)
			    for (y2=0;y2<4 && !NoGood;y2++)
					for (x2=0;x2<4 && !NoGood;x2++) {

				    	s2=-100000;
				    	NoGood2=FALSE;

					    if (cube1[x2][y2][z2]==' ') {
							copy_cube(cube2,cube1);
							cube2[x2][y2][z2]=human_symbol;

							for (z3=0;z3<4 && !NoGood2;z3++)
							    for (y3=0;y3<4 && !NoGood2;y3++)
									for (x3=0;x3<4 && !NoGood2;x3++) {
								    	if (cube2[x3][y3][z3]==' '){
											copy_cube(cube3,cube2);
											cube3[x3][y3][z3]=comp_symbol;
							   	 			score=score_cube(cube3);
											if (s2<score) {
										    	s2=score;
										    	if (s2>s1) NoGood2=TRUE;
											}
								    	}
									}
					   		if (s1>s2) {
					   		   	s1=s2;
					   		   	if (s1<s0) NoGood=TRUE;
							}
					    }
			}

			if (s0<s1) {
			    s0=s1;
			    bestmovex=x1;
			    bestmovey=y1;
			    bestmovez=z1;
			}
		    }
		}

	cube0[bestmovex][bestmovey][bestmovez]=comp_symbol;

	myMatrix.clear();
	state = 3;					// blinking last move of computer
	while (getKey() == 0) ;		// wait until player has pressed a button, then display regular cube
	state = 0;
}

int score_cube(char cube[4][4][4]) {

	int scores=0, x, y, z, tally_comp=0, tally_human=0;
	int comp[5]={0,0,0,0,0}, human[5]={0,0,0,0,0};
	char board[4][4];

	for (z=0;z<4;z++) {	/* boards in Z direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][y][z];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* boards in Y direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[x][z][y];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* boards in X direction */
		for (y=0;y<4;y++)
			for (x=0;x<4;x++)
				board[x][y]=cube[z][y][x];
		scores+=score(board);
	}

	for (z=0;z<4;z++) {	/* 3D diagonal 1 */
		tally_comp+=(cube[z][z][z]==comp_symbol);
		tally_human+=(cube[z][z][z]==human_symbol);
	}

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 2 */
		tally_comp+=(cube[3-z][z][z]==comp_symbol);
		tally_human+=(cube[3-z][z][z]==human_symbol);
	}

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 3 */
		tally_comp+=(cube[z][3-z][z]==comp_symbol);
		tally_human+=(cube[z][3-z][z]==human_symbol);
	}

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (z=0;z<4;z++) {	/* 3D diagonal 4 */
		tally_comp+=(cube[z][z][3-z]==comp_symbol);
		tally_human+=(cube[z][z][3-z]==human_symbol);
	}	

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	scores+=comp[1]-3*human[1]+7*comp[2]-15*human[2]+31*comp[3]-63*human[3]+127*comp[4]-1000*human[4];
	return scores;

}

int score(char board[4][4]) {

	int x, y, tally_comp=0, tally_human=0, comp[5]={0,0,0,0,0}, human[5]={0,0,0,0,0};

	for (y=0;y<4;y++) {						/* Rows */
		for (x=0;x<4;x++) {
			tally_comp+=(board[x][y]==comp_symbol);
			tally_human+=(board[x][y]==human_symbol);
		}

		if (tally_comp>0 && tally_human>0) {
			tally_comp=0;
			tally_human=0;
		}

		comp[tally_comp]++;
		human[tally_human]++;

		tally_comp=0;
		tally_human=0;
	}

	for (x=0;x<4;x++) {						/* Columns */
		for (y=0;y<4;y++) {
			tally_comp+=(board[x][y]==comp_symbol);
			tally_human+=(board[x][y]==human_symbol);
		}

		if (tally_comp>0 && tally_human>0) {
			tally_comp=0;
			tally_human=0;
		}

		comp[tally_comp]++;
		human[tally_human]++;

		tally_comp=0;
		tally_human=0;
	}

	for (y=0;y<4;y++) {						/* Down diagonal */
		tally_comp+=(board[y][y]==comp_symbol);
		tally_human+=(board[y][y]==human_symbol);
	}

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	tally_comp=0;
	tally_human=0;

	for (y=0;y<4;y++) {						/* Up diagonal */
		tally_comp+=(board[3-y][y]==comp_symbol);
		tally_human+=(board[3-y][y]==human_symbol);
	}

	if (tally_comp>0 && tally_human>0) {
		tally_comp=0;
		tally_human=0;
	}

	comp[tally_comp]++;
	human[tally_human]++;

	y=comp[1]-3*human[1]+7*comp[2]-15*human[2]+31*comp[3]-63*human[3]+127*comp[4]-1000*human[4];
	/* Needs to be the same evaluation function as in 'score_cube' function */
	return y;

}

void init_cube (void) {

	int x,y,z;

	for(z=0;z<4;z++)
		for(y=0;y<4;y++)
			for(x=0;x<4;x++) cube0[x][y][z]=' ';
}

void get_player_move(void) {

	int x,y,z;

	while (getKey() == 0) ;

	state = 1;
	state1x = 5;
	state1y = 5;
	state1z = 5;

	do {
		while (getKey() == 0) ;
		if (key < '5')
			state1x = (key - '0') - 1;
	} while (key != '5' || state1x > 3 );
	x = state1x;

	do {
		while (getKey() == 0) ;
		if (key < '5')
			state1y = (key - '0') - 1;
	} while (key != '5' || state1y > 3 );
	y = state1y;

	do {
		while (getKey() == 0) ;
		if (key < '5')
			state1z = (key - '0') - 1;
	} while (key != '5' || state1z > 3 );
	z = state1z;

	if (cube0[x][y][z]!=' ') {			// Invalid move - redo entry
		get_player_move();
	}

	cube0[x][y][z]=human_symbol;
	state = 0;
}

void setup() {

	for (int row = 0; row < numRows; row++) {
		pinMode(rowPins[row], INPUT);
		digitalWrite(rowPins[row], HIGH);
	}
	for (int column = 0; column < numCols; column++) {
		pinMode(colPins[column], OUTPUT);
		digitalWrite(colPins[column], HIGH);
	}
}

void loop() {
	char done, Buf[12];
	int x,y,z;

	state = 1;	// Pre-game cube LED flashing
	done = ' ';

	myMatrix.clear();

	init_cube();
	MsTimer2::set(period, disp_LED_cube);
	MsTimer2::start();

	while (getKey() == 0) ;			// Press 1 to go first
	state = 0;		// Normal display of cube LED
	if (key != '1') {
		human_symbol='O';
		comp_symbol='X';
		get_computer_move();
	}

	do {
		state = 0;
		get_player_move();
		done=check_cube(cube0);
		if (done != ' ') break;
		get_computer_move();
		done=check_cube(cube0);
	} while (done==' ');

	if (done==human_symbol) ;			// Player has WON!
	else ;						// Compute has WON!

}

As always, if you have any questions, need further assistance or require additional pictures or diagrams, please let me know in the comments and I’ll do my best to address them.

Up Next: Figuring Out How To Select Player Moves (determining pin combinations for particular keys on an unknown keypad, and hard coding)