Category: Memoirs of James Pate Williams Jr
Blog Entry © Sunday, November 30, 2025, by James Pate Williams, Jr. and the Microsoft Artificially Intelligent Agent, the Copilot
Blog Entry © Saturday, November 28, 2025, by James Pate Williams, Jr. Fair Coin and Fair Dice Probabilities
Blog Entry © Tuesday 25, 2025, by James Pate Williams, Jr. Enumeration of the Tic-Tac-Toe Game Tree
/*
* Board.h
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Modified on Monday 11/24/2025
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#ifndef _Board_
#define _Board_
#include <fstream>
#include <vector>
class Board {
private:
char state[9];
std::vector<std::vector<char>> board;
public:
Board(void);
Board(const Board &board);
Board(const char b[3][3]);
Board(const std::vector<char> &v);
char GetState(int n) const;
void PrintBoard(int n) const;
void WriteBoard(std::ofstream &out) const;
friend bool operator == (const Board &b1, const Board &b2);
friend bool operator != (const Board &b1, const Board &b2);
friend bool Found(const Board &initial, const Board &board);
friend bool Win(const Board b, char winner[8]);
friend bool LegalBoard(
bool& legal, bool& won, char& whoWon, const Board b);
friend void PrintBoard(char board[3][3], int number);
static const char CharX, CharO, CharS;
};
#endif
/*
* Board.cpp
* Permutation
*
* Created by James Pate Williams, Jr. on 7/21/08.
* Copyright 2008 James Pate Williams, Jr. All rights reserved.
*
*/
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <vector>
#include "Board.h"
const char Board::CharO = 'o';
const char Board::CharX = 'x';
const char Board::CharS = '_';
Board::Board(void) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 9; i++)
state[i] = '\0';
}
Board::Board(const Board &b) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b.state[3 * i + j];
}
Board::Board(const char b[3][3]) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = b[i][j];
}
Board::Board(const std::vector<char> &v) {
board.resize(3, std::vector<char>(3));
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
state[3 * i + j] = board[i][j] = v[3LL * i + j];
}
char Board::GetState(int n) const {
return state[n];
}
void Board::PrintBoard(int n) const {
std::cout << n << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << state[3 * i + j];
std::cout << std::endl;
}
std::cout << std::endl;
std::cout << std::endl;
}
void Board::WriteBoard(std::ofstream &out) const {
for (int i = 0; i < 9; i++)
out << state[i];
out << std::endl;
}
bool operator == (const Board &b1, const Board &b2) {
int i, equal = 0;
for (i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
equal++;
return equal == 9;
}
bool operator != (const Board &b1, const Board &b2) {
for (int i = 0; i < 9; i++)
if (b1.state[i] == b2.state[i])
return false;
return true;
}
bool Found(const Board &initial, const Board &board) {
// reflections
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[3] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[5] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[1] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[7] &&
initial.state[8] == board.state[6])
return true;
if (initial.state[0] == board.state[0] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[8])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[2] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[6] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[0])
return true;
// rotations
if (initial.state[0] == board.state[6] && initial.state[1] == board.state[3] &&
initial.state[2] == board.state[0] && initial.state[3] == board.state[7] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[1] &&
initial.state[6] == board.state[8] && initial.state[7] == board.state[5] &&
initial.state[8] == board.state[2])
return true;
if (initial.state[0] == board.state[8] && initial.state[1] == board.state[7] &&
initial.state[2] == board.state[6] && initial.state[3] == board.state[5] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[3] &&
initial.state[6] == board.state[2] && initial.state[7] == board.state[1] &&
initial.state[8] == board.state[0])
return true;
if (initial.state[0] == board.state[2] && initial.state[1] == board.state[5] &&
initial.state[2] == board.state[8] && initial.state[3] == board.state[1] &&
initial.state[4] == board.state[4] && initial.state[5] == board.state[7] &&
initial.state[6] == board.state[0] && initial.state[7] == board.state[3] &&
initial.state[8] == board.state[6])
return true;
// equal
return initial == board;
}
bool Win(const Board b, char winner[8]) {
bool win = false;
for (int i = 0; i < 8; i++)
winner[i] = Board::CharS;
if (b.board[0][0] == b.board[0][1] && b.board[0][0] ==
b.board[0][2] && b.board[0][0] != Board::CharS) {
winner[0] = b.board[0][0];
win = true;
}
if (b.board[1][0] == b.board[1][1] && b.board[1][0] ==
b.board[1][2] && b.board[1][0] != Board::CharS) {
winner[1] = b.board[1][0];
win = true;
}
if (b.board[2][0] == b.board[2][1] && b.board[2][0] ==
b.board[2][2] && b.board[2][0] != Board::CharS) {
winner[2] = b.board[2][0];
win = true;
}
if (b.board[0][0] == b.board[1][0] && b.board[0][0] ==
b.board[2][0] && b.board[0][0] != Board::CharS) {
winner[3] = b.board[0][0];
win = true;
}
if (b.board[0][1] == b.board[1][1] && b.board[0][1] ==
b.board[2][1] && b.board[0][1] != Board::CharS) {
winner[4] = b.board[0][1];
win = true;
}
if (b.board[0][2] == b.board[1][2] && b.board[0][2] ==
b.board[2][2] && b.board[0][2] != Board::CharS) {
winner[5] = b.board[0][2];
win = true;
}
if (b.board[0][0] == b.board[1][1] && b.board[0][0] ==
b.board[2][2] && b.board[0][0] != Board::CharS) {
winner[6] = b.board[0][0];
win = true;
}
if (b.board[0][2] == b.board[1][1] && b.board[0][2] ==
b.board[2][0] && b.board[0][2] != Board::CharS) {
winner[7] = b.board[0][2];
win = true;
}
return win;
}
void PrintBoard(char board[3][3], int number) {
std::cout << "number = " << number << std::endl;
std::cout << std::endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
std::cout << board[i][j];
std:: cout << std::endl;
}
std::cout << std::endl;
}
bool LegalBoard(
bool &legal, bool &won, char &whoWon, const Board b) {
bool winO, winX;
char winner[8];
int countO = 0, countS = 0, countX = 0;
int i, j, oWins = 0, xWins = 0;
legal = won = false;
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (b.board[i][j] == Board::CharO)
countO++;
else if (b.board[i][j] == Board::CharX)
countX++;
else if (b.board[i][j] == Board::CharS)
countS++;
}
}
if ((countX >= 3 || countO >= 3) && Win(b, winner)) {
for (i = 0; i < 8; i++) {
if (winner[i] == Board::CharX)
xWins++;
else if (winner[i] == Board::CharO)
oWins++;
}
winX = (xWins >= 1 && oWins == 0) &&
(countX <= 5 && countO <= 4 && countX == countO + 1);
winO = (xWins == 0 && oWins >= 1) &&
(countO <= 5 && countX <= 4 && countO == countX + 1);
legal = won = winX || winO;
if (won && winX)
whoWon = Board::CharX;
else if (won && winO)
whoWon = Board::CharO;
}
else
legal = (countX <= 5 && countO <= 4 && countX == countO + 1) ||
(countO <= 5 && countX <= 4 && countO == countX + 1);
return legal;
}
#define _WriteBV_
#include <algorithm>
#ifdef _WriteBV_
#include <fstream>
#endif
#include <iomanip>
#include <iostream>
#include <vector>
#include "Board.h"
static int Compare(const void *vPtr1, const void *vPtr2) {
char *cPtr1 = (char *) vPtr1;
char *cPtr2 = (char *) vPtr2;
return strcmp(cPtr1, cPtr2);
}
static void EnumerateTicTacToe(void) {
bool legal, won;
char b[3][3], whoWon;
char tree[3][3][3][3][3][3][3][3][3];
int i0, i1, i2, i3, i4, i5, i6, i7, i8;
int legals = 0, number = 0, wCount = 0;
int xCount = 0, oCount = 0;
int bvSize, i, j;
std::vector<Board> boardVector;
for (i0 = 0; i0 < 3; i0++) {
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
for (i3 = 0; i3 < 3; i3++) {
for (i4 = 0; i4 < 3; i4++) {
for (i5 = 0; i5 < 3; i5++) {
for (i6 = 0; i6 < 3; i6++) {
for (i7 = 0; i7 < 3; i7++) {
for (i8 = 0; i8 < 3; i8++) {
if (i0 == 0)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i0 == 1)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i0 == 2)
b[0][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i1 == 0)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i1 == 1)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i1 == 2)
b[0][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i2 == 0)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i2 == 1)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i2 == 2)
b[0][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i3 == 0)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i3 == 1)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i3 == 2)
b[1][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i4 == 0)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i4 == 1)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i4 == 2)
b[1][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i5 == 0)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i5 == 1)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i5 == 2)
b[1][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i6 == 0)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i6 == 1)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i6 == 2)
b[2][0] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i7 == 0)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i7 == 1)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i7 == 2)
b[2][1] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
if (i8 == 0)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharX;
else if (i8 == 1)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharO;
else if (i8 == 2)
b[2][2] = tree[i0][i1][i2][i3][i4][i5][i6][i7][i8] = Board::CharS;
Board bb(b);
if (LegalBoard(legal, won, whoWon, bb)) {
Board board(b);
legals++;
if (won) {
wCount++;
if (whoWon == Board::CharX)
xCount++;
else if (whoWon == Board::CharO)
oCount++;
}
boardVector.push_back(board);
}
number++;
}}}}}}}}}
for (i = 0; i < boardVector.size() - 1; i++)
for (j = i; j < boardVector.size(); j++)
if (Found(boardVector[i], boardVector[j]))
boardVector.erase(boardVector.begin() + j);
bvSize = (int)boardVector.size();
std::cout << std::setw(4) << "legal total = " << legals << std::endl;
std::cout << std::setw(4) << "xWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oWins total = " << xCount << std::endl;
std::cout << std::setw(4) << "oxWin total = " << xCount + oCount << std::endl;
std::cout << std::setw(4) << "unique size = " << boardVector.size();
std::cout << std::endl;
#ifdef _WriteBV_
std::cout << std::endl;
std::ofstream outFile("Tic TacToe Game Tree Enumeration.txt");
std::cout << std::endl;
for (i = 0; i < bvSize; i++) {
boardVector[i].PrintBoard(i + 1);
boardVector[i].WriteBoard(outFile);
}
#endif
}
int main (int argc, char * const argv[]) {
EnumerateTicTacToe();
return 0;
}
Blog Entry © Monday, November 24, 2025, by James Pate Williams, Jr., A* Informed Search Application to Solve the 15-Tile Puzzle
Blog Entry © Sunday, November 23, 2025, by James Pate Williams, Jr. Modification of My A* Informed Search Solver for the 8-Tile Puzzle
Blog Entry © Friday, November 21, 2025, by James Pate Williams, Jr., Win32 C/C++ Desktop GUI Solution of the 15-Tile Puzzle Using Iterative Deepening A* Informed Seach Algorithm
Blog Entry © Tuesday, November 18, 2025, by James Pate Williams, Jr. A New MP3 Entitled “Blunder-Full”
The MP3 was created using the digital audio workstation (DAW), SONAR Platinum, and the Universal Audio (UA) plugin UADx PolyMAX synthesizer. The number of beats per minute is 180. The synthesizer emulator patch is 2 Saws which utilizes two oscillators with sawtooth waves.
Numerical Explorations 