3D Tic Tac Toe (3D Graphics pt. 2)
After getting my 3D graphics engine to a usable state, it was finally time to actually use it for what it was meant to do: 3D Tic Tac Toe.
3D Tic Tac Toe as a sold game can be traced back to the early 60s, where it was marketed at Qubic, although it’s possible that versions of the game had been played before then. The basic concept is fairly easy to understand: it’s simply the game of Tic Tac Toe expanded into a third dimension, inheriting and generalizing all the rules of the original. In 3D tic tac toe, any line that spans a cube is a valid winning solution. This may seem like a simple modification, but it increases the complexity of the game by an order of magnitude. The game of 2D tic tac toe has been solved (meaning that there is a way for a perfect player to always win or force a draw) since antiquity, long before computers even existed. However, 3D tic tac toe was only first solved in the 1980s with the help of a computer.
It would seem that I am not alone in my interest. 3D Tic Tac Toe has long held the interests of programmers, with the possible first digital version being developed in the late 1950s for the IBM 650. However, since then, it seems that nobody has ever developed a version of the game in true 3D. Every version of the game that I can find online seems to simply be a 2D representation of a 3D space, similar to the Atari version shown below:
The problem with reducing 3D Tic Tac Toe to a 2D representation like this is that it makes it hard to visualize some of the winning combinations, particularly diagonals that span across the height axis of the game “board”. In my mind the only way to truly play 3D Tic Tac Toe is… in 3D! Hence, I set out to program what is potentially the first ever true version of 3D Tic Tac Toe.
Before setting about programming the game, I needed to settle upon a dimension for the board. Simply expanding 3×3 Tic Tac Toe to 3x3x3 is not ideal as it results in a very steep first player win advantage if they occupy the center cell. To eliminate this, most versions of the game use a 4x4x4 board, which is what I elected to go with.
Now that our game dimensions had been settled upon, the next step was to generate the board. In theory, we could load each cube from an STL file like we did last time, but this is not necessary for an object as simple as a cube. Instead, we can procedurally generate every cube in the engine itself to save an unnecessary loading time. This brings us to another optimization. Currently, the only polygon class in our engine is the triangle class, meaning that every cube would have to be made up of 12 polygons total. As mentioned before, there is no GPU acceleration, meaning I can’t take any polygons for granted. If we implement another square class, we can cut our total polygon count in half. With no culling, this means that our entire game board can be reduced to just 384 polygons instead of 768. This square class is implemented as follows:
class square(polygon):
def __init__(self, normal, p1, p2, p3, p4, color):
super().__init__(normal, [p1, p2, p3, p4], color)On its own, this isn’t all that useful, but if we join 6 squares into a cube class, we can procedurally generate our entire board by simply defining the size of all our cubes and the space between them:
class cube(object):
def __init__(self, center, sidelength, color):
o = sidelength / 2
points = []
for x in range(2): #procedurally create all points in the cube
for y in range(2):
for z in range(2):
points.append(center + point(((-1) ** x) * o, ((-1) ** y) * o ,((-1) ** z) * o))
squares = []
squares.append(square(point(1, 0, 0), points[0], points[2], points[3], points[1], color)) #constant +x
squares.append(square(point(-1, 0, 0), points[4], points[6], points[7], points[5], color)) #constant -x
squares.append(square(point(0, 1, 0), points[0], points[4], points[5], points[1], color)) #constant +y
squares.append(square(point(0, -1, 0), points[2], points[6], points[7], points[3], color)) #constant -y
squares.append(square(point(0, 0, 1), points[0], points[4], points[6], points[2], color)) #constant +z
squares.append(square(point(0, 0, -1), points[1], points[5], points[7], points[3], color)) #constant -z
for s in squares:
s.parent = self
super().__init__(squares, color)
self.getcom()This generates a cube from three arguments defining its location, size, and color. All square creation is handed internally to ensure that points in each cube follow a consistent winding order and don’t produce a polygon that folds in on itself. To create the board, these cubes are then generated in three nested loops in the main file. Colors alternate between each cell, like in a chess board, in order to allow the players to distinguish between them more easily:
blist = []
colors = [(230,230,230),(200,200,200),(170,170,170),(140,140,140)]
space = 20
for cz in range(0, 4):
for cy in range(0, 4):
for cx in range(0, 4):
if (cy) % 2 == 0:
if (cy + cz + cx) % 2 == 0:
color = colors[0]
else:
color = colors[1]
else:
if (cy + cz + cx) % 2 == 0:
color = colors[2]
else:
color = colors[3]
blist.append(game.cell(pg3d.point(cx * space, cy * space, cz * space), 10, color, (cx + cy * 4 + cz * 16)))Launching the program for the first time gives us the following:
Because this difference in coloring is sufficient to distinguish each cell, we don’t need to apply any lighting to the scene, which also serves to drastically improve performance.
Now that the board is drawn, we need a means of selecting the cell that a player wants to occupy. A rudimentary approach would be to allow a user to type in a cell by coordinates or use some keys to change the selected cell, but this isn’t a very satisfying way to go about it. I wanted players to be able to click on a cell and have the game select it. In order to do this, we need to determine if the cursor lies within a given 2D projection of a polygon and mark that polygon’s cell as selected in the game backend. To to this, we must determine all the polygons that the cursor lines within, and then select the closest one to the camera. The key to this is the infamous point in polygon algorithm:
def insidePolygon2D(self, camera, xoffset, yoffset, point): #determine if a 2D point is in the projected polygon
points2D = []
lines2D = []
crossings = 0
for p in self.pointlist: #create list of projected points
points2D.append(point2D(p.project(camera, xoffset, yoffset)[0], p.project(camera, xoffset, yoffset)[1]))
for i in range(len(points2D)):
if i == 0:
j = len(points2D) - 1
else:
j = i - 1
lines2D.append(line2D(points2D[i], points2D[j])) #get all lines in polygon
ray = line2D(point2D(xoffset, yoffset), point2D(xoffset + 10000, yoffset)) #cast functionally infinite ray
for l in lines2D:
if ray.intersects(l):
crossings += 1
return (crossings % 2 != 0)What’s going on here is actually fairly simple. In 2D space, a point lies within a given polygon if an infinite line cast in any direction from said point intersects the polygon’s edges an odd number of times. Hence, this function casts a functionally infinite ray from the cursor and returns true if it crosses the polygon an odd number of times. Since all polygons here have only 4 edges, there is actually no case where a straight line will cross them more than twice, but is it good to generalize. This is illustrated below:
There are edge cases where the algorithm could detect a false positive, like if the ray passes through a vertex and registers as crossing an odd number of edges, but this is exceedingly rare and almost impossible to do accidentally with a simple polygon, so there is no need to implement a check for it here.
Now that we have a way to test all polygons that the user could be selecting, we will simply sort all those that return true by depth and select the nearest one to the camera. Once a cell is selected by the user, it is marked as occupied and can no longer be selected by another player:
if locked and winner == None:
plist = []
for p in s.polygons: #get closest polygon to mouse
if p.insidePolygon2D(s.camera, mxcenter, mycenter, (mxcenter,mycenter)):
plist.append(p)
plist.sort(key = lambda x: x.getDistance(s.camera))
if plist and ttt.currentPlayer.type == 0: #if it is a human's turn
#validmove = ttt.makeMove(usernum, plist[0].parent.numToBin())
validmove = ttt.currentPlayer.makeMove(plist[0].parent.numToBin())
if validmove:
plist[0].parent.changeColor(ttt.currentPlayer.color)
plist[0].parent.occupied = True
if ttt.testWin():
winner = ttt.currentPlayer
#print(ttt.currentPlayer.getWinningSequences(2))
ttt.gotoNextPlayer()We can now see click selection in action:
Now that we have a way to select cells, all we need to do is add some backend logic to determine win states and we’ll have a functional game. Since we have a fixed board size, we could assign each cell a number from 0-63 and just have a lookup table of all the possible winning sequences, but this is probably the worst way to go about it. Besides being an awful brute forced solution, it’s also very computationally wasteful. Instead, a better method takes advantage of the properties of binary numbers.
Instead of assigning each cell as 0-63, we can instead assign them the numbers \(2^{0 – 63}\). The reason for this is simple: each power of two can be represented by a single binary 1 followed by however many trailing zeros correspond to its power. If we use a bitwise OR operation to combine all the cells occupied by a player into a single integer, we can perform bitwise operations on said integer to determine win conditions. If the bitwise AND of a given win sequence and a player state outputs the same win sequence, we know that all the cells required for a win are occupied. Because of the way the cells are laid out, there are certain redundant bit patterns in winning combinations that we can isolate. This greatly reduces the amount of code we need to write and the amount of values we need to look up in order to check win conditions. The full code for this is shown below:
def testWin(self):
diags3D = [0x1000020000400008, 0x8000040000200001, 0x1002004008000, 0x8004002001000]
diagsHoriz = [0x1000200040008, 0x8000400020001]
diagsVert = [0x1248, 0x8421]
diagsDepth = [0x1001001001000, 0x1000010000100001]
for d in diags3D:
if self.testState(d):
return True
for n in range(4):
for d in diagsHoriz: #flat diagonals
if self.testState(d << (4 * n)):
return True
for d in diagsVert: #vertical diagonals
if self.testState(d << (16 * n)):
return True
for d in diagsDepth: #'z' diagonals
if self.testState(d << n):
return True
for m in range(4):
if self.testState((0x1111 << m) << (16 * n)): #verticals
return True
if self.testState((0x1000100010001 << m) << (4 * n)): #'z' horizontals
return True
for n in range(16):
if self.testState((0xf << (4 * n))): #horizontals
return True
return FalseNow that we can determine if a given player has won, it is now possible to play a full game of 3D Tic Tac Toe with however many players we wish, although I have decided to restrict it to 4 players for the sake of good gameplay. However, since I had no access to any friends at this time (darn you COVID-19!), I also needed a way to play the game by myself. Hence, it was also necessary to program a new bot player.
Most bots for board games like this with clear win states use something called a minimax algorithm for bot players. Minimax works by creating a tree of possible future moves and determining those that maximize the bot’s advantage and/or minimize the opponent’s advantage. However, this algorithm only works when there are two players, and it’s not strictly applicable when there are two or more opponent players. Therefore, we must create our own bot algorithm that can work with more than two players on the board.
My bot algorithm attempts to approach the game in the same way that human players typically do. I accomplish this by performing a search across all valid move sequences that each player can take starting with their next turn, with search depth as a parameter to change the difficulty of the bot player. After finding all valid moves, the algorithm then finds the move(s) that appear most commonly in all the potential winning sequences. If the depth of any winning sequence for the player is smaller or equal to the depth of any for its opponent(s), it will take that move first. Conversely, if any of its opponents have a winning sequence that is shorter than any of its own winning sequences, it will move to block their winning move. Because the largest possible winning move sequence is of size 4 on a 4x4x4 board, we can make the bot have 5 levels of difficulty, with 0 being totally random, and with 4 being able to map out a winning move sequence from an empty board.
The function inside the player class to get winning sequences up to depth n is as follows:
def getWinningSequences(self, depth): #get all sequences of n length that will result in a win
moves = []
winningMoves = []
validmoves = list(self.parentBoard.getValidMoves())
getAllCombinations(validmoves, len(validmoves), depth, 0, [0] * depth, 0, moves)
for sequence in moves:
movebits = 0
for move in sequence:
movebits |= move
newplayer = copy.deepcopy(self)
newplayer.boardstate |= movebits
if newplayer.testWin():
winningMoves.append(sequence)
return winningMovesThe bot class then applies this to its algorithm like so:
def doBlockingMove(self):
possibleDefMoves = []
possibleOffMoves = []
cell = -1
for p in self.parentBoard.playerlist: #defensive move
if p != self:
for d in range(1, self.difficulty + 1):
for m in p.getWinningSequences(d):
if m not in possibleDefMoves:
possibleDefMoves.append(m)
print(m)
if possibleDefMoves: #break so we address more pressing defensive moves first
break
for d in range(1, self.difficulty + 1):
for m in self.getWinningSequences(d):
if m not in possibleOffMoves:
possibleOffMoves.append(m)
if possibleOffMoves:
break
if possibleDefMoves and possibleOffMoves:
if (len(getShortest(possibleDefMoves)) < len(getShortest(possibleOffMoves))): #make defensive move if opponent is closer to winning
cell = randomInList(getMostCommon(getAllShortest(possibleDefMoves)))
else:
cell = randomInList(getMostCommon(getAllShortest(possibleOffMoves)))
elif possibleDefMoves:
cell = randomInList(getMostCommon(getAllShortest(possibleDefMoves)))
elif possibleOffMoves:
cell = randomInList(getMostCommon(getAllShortest(possibleOffMoves)))
else: #random move
validMoves = self.parentBoard.getValidMoves()
cell = validMoves[random.randint(0, len(validMoves) - 1)]
self.makeMove(cell)
return int(log(cell, 2))And now we have a bot player that can work with a theoretically infinite amount of opponents. The algorithm is far from perfect, and is far slower than I would like it to be, but it works. The last problem we need to overcome is the fact that, so far, all of our code has been single-threaded. This means that the 3D engine wouldn’t be able to draw to the screen while the bot is computing its next move. To fix this, we must split our bot code into its own thread. Luckily, Python’s threading module makes this fairly easy:
def doBotLogic():
nonlocal run
nonlocal winner
while run:
time.sleep(0.1)
if ttt.currentPlayer.type == 1 and winner == None: #if it is a bot's turn
cellNum = ttt.currentPlayer.doBlockingMove()
blist[cellNum].occupied = True
blist[cellNum].changeColor(ttt.currentPlayer.color)
if ttt.testWin():
winner = ttt.currentPlayer
ttt.gotoNextPlayer()
if ttt.boardstate == 0xffffffffffffffff and winner == None:
winner = False
logicThread = threading.Thread(target = doBotLogic)
logicThread.start()Finally, we may play a complete game of 3D Tic Tac Toe in real 3D against our AI opponent: