Essays, Posts & Presentations

Visualizing Game Trees in "Trax" the Board Game

Eric Parfitt

Author

Eric Parfitt

Title

Visualizing Game Trees in "Trax" the Board Game

Description

Visualizing Game Trees in "Trax" the Board Game

Visualizing Game Trees in “Trax” the Board Game

Eric Parfitt

Introduction

Trax is possibly my favorite board game. I like the somewhat simple rules, the fact that it’s played on an infinite board, and also I just have a general feeling that the branching of the game tree is just right. To that last end, I decided to write some code to actually analyze that game tree. Below are some of my preliminary results.

Just to mention, this project doubles as a project to demonstrate my general coding abilities. Because of that, I have also added many comments to my code to show how it all fits together. If you’re mostly interested in seeing a Trax game tree, and not somebody interested in learning details about my coding style and how my code works, you can feel free to just read the short “Game Tree Analysis” section and possibly the final “Future Plans” section and skip the rest.

Also though, here is a link to the rules for the game which can help with understanding how the game itself works.

Code


Game Tree Analysis

This shows expanding the game tree for one step. The top layer has the two starting tiles, and the bottom layer shows all possible moves after one step. Boards that are the same when reflected, rotated, or translated are considered to be the same, and also if swapping black for white would make the board the same, then states are also merged (and one representative example is shown in the graph).

In[]:=

traxMultiway[Automatic,1,ImageSize->Large]

Out[]=

The game tree after two steps:

traxMultiway[Automatic,2,GraphLayout->"LayeredDigraphEmbedding",ImageSize->Full]

Out[]=

You can notice from these examples that the game tree not only branches, but sometimes merges.

Below is the game tree after three steps. In this example, I have pruned the game tree by removing win states, and to prune the tree further, this is additionally a modified version of the game where a line of only length three (instead of the standard 8) wins. Hover over a vertex to see the board at that vertex (hovering only works on desktop, not on cloud).

traxMultiway[Automatic,3,"winStateBehavior"->"remove",GraphLayout->"LayeredDigraphEmbedding",VertexShapeFunction->Automatic,VertexLabels->Placed["Name",Tooltip],AspectRatio->1/2,ImageSize->Large]

Out[]=

Code Overview Description

Here is a descriptive outline of how some of the program works:

To generate the game tree:

◼

Use a modified version of NestGraph to generate a game tree

◼

Input a function that generates all possible new states for a given state

◼

Generate all possible potential moves and return any that lead to boards that are valid and not wins

◼

Merge states that are equivalent when ignoring reflections / rotations / translations / color inversions (using the modifications in the modified version of NestGraph)

To perform a move:

◼

Check if move is valid

◼

Add any forced moves (return “mismatch” if mismatched “forced move” encountered)

◼

Check if either player has won

To add forced moves:

◼

Recursively attempt to add tiles around the neighbors of the starting tile or any other forced tiles

◼

Attempt to add them by checking if there are two of the same color entering a position, and if so, find the one possible tile that should fit there

◼

If a position is found where a forced move would cause three or more possible tiles to enter a position, then the whole forced moves attempt just returns “mismatch”.

To check for a win:

◼

Follow all paths from all tiles

◼

Paths either

◼

return to their original tile, which means there’s a loop win, or

◼

end up on different edges of the board

◼

If two ends of a path end up on different edges of the board, check if the player won, which happens when three three things are all checked and found to be true:

◼

are the edges pointing in opposite directions

◼

are the edges at least 8 tiles apart (in the direction that they are oriented)

◼

are the edges on the far sides of the board (in the direction that they are oriented)

Code Snippets

Here are some snippets of code from above, (helper functions) along with the comments on them, that are ones I find to be somewhat interesting parts of the code:

MoveForced

Attempts to add a tile to the board, and also finds any “forced moves” in the neighborhood of the tile (a forced move being defined as an adjacent space to the added tile into which same coloured track enters from two edge), and adds those to the queue, which is recursively ran through until the queue is empty. If at any time one of the potential forced tiles forms an adjacent space into which same coloured track enters from more than two edges, the whole thing returns the string “mismatch” (which takes care of the prohibition rule against three or more edges of the same color entering the same space).

moveForced[board_Association,queue:{myMove:(position:{_Integer,_Integer}tile_?tileQ),moves___?moveQ}]:=With[{newBoard=Append[board,myMove]},{myForcedMoves=forcedMoves[newBoard,position]},Replace[myForcedMoves,myMoves:Except["mismatch"]moveForced[newBoard,{moves}~Join~myForcedMoves]]]

EdgeWinState

This function takes a position, and an edge around that position, and follows a path that comes out of that edge until either there is no path to follow any longer, in which case it outputs that “dangling” position, or the path returns to the position it started from, which, due to the nature of the tiles, would imply a loop has been formed (and then the string “loopWin” is returned).

It repeatedly steps along a path, while keeping the last two tiles in memory. If the last tile is missing, then the second to last is tile returned, whereas if the last tile is the same as the first tile, that one is compared with the first tile and if they are the same then “loopWin” is returned.

In[]:=

edgeWinState[board_?AssociationQ,position:{_Integer,_Integer},edge_?edgePosQ]:=Replace[ResourceFunction["SafeTake"][Prepend[{position,edge}]@nestWhileKeeping[stepPath[board],stepPath[board][{position,edge}],Not@*MatchQ[{position,_}|{_,_Missing}],2],-2],{{extreme_,{_,_Missing}}:>extreme,_List->"loopWin"}]

CanonicalizeBoard

Canonicalizes a board such that boards that differ just by reflections, rotations, translations, and color-inversions give the same output board.

This does so by finding all rotations / reflections of the board, and both color-inversions of those, then translates them all so that their minimum x and y coordinates are exactly 0, sorts all of them, and then picks the first out of of all those possibilities.

In[]:=

canonicalizeBoard[board_?AssociationQ]:=First@Sort[KeySort@*boardNormalize/@Catenate[colorSwaps/@flipRotates[board]]]

Further use of the Code

Below are some more examples showing some details of how the code works.

Short Sample Game

Here is a very quick example “game” where white plays quite badly and so black gets a loop win.

First we’re just going to set up this tile as the final move for the game:

In[]:=

myMove={2,0}->{1,0,0,1};

display[<|myMove|>,ImageSize->Tiny]

Out[]=

The A game in progress. Step 3 involves a forced move. Step 4 is where the final move from above is played, and outputs “1 -> {“loopWin”}” meaning that 1, the black player, had a loop win.

GraphicsRow[FoldList[moveAndCheck[First[#1],#2,<|0->1,1->0|>[Last[#1]]]&,{<|{0,0}->{1,1,0,0}|>,0},{{1,0}->{0,1,0,1},{1,1}->{0,1,0,1},myMove}]/.{board_?AssociationQ,_}:>display[board,100],Frame->All]

Out[]=

Exemplifying Forced Tile Moves

Here is certain board state:

In[]:=

board=<|{0,0}->{0,1,1,0},{1,0}->{0,1,0,1},{2,0}->{1,0,0,1},{0,1}->{0,1,0,1},{0,2}->{1,0,0,1},{0,3}->{1,0,1,0},{1,3}->{0,1,1,0},{2,3}->{1,0,0,1}|>;

display@board

Out[]=

Here, one added tile:

In[]:=

move2={2,1}->{1,0,1,0};

display[<|move2|>,ImageSize->Tiny]

Out[]=

...causes three additional forced moves :

display@First@moveAndCheck[board,move2,0]

Out[]=

Here, one of the forced moves:

In[]:=

move3={2,1}->{0,1,1,0};

display[<|move3|>,ImageSize->Tiny]

Out[]=

...would have caused three colors to enter the same position, so the whole state is illegal and returns “mismatch”.

moveAndCheck[board,move3,0]

Out[]=

mismatch

It would have forced this, where the the gray “hole” has three white edges leading into it, so no tile would fit, making the whole forced sequence illegal.

display[Append[board,{{2,1}->{0,1,1,0},{1,1}->{1,0,0,1},{1,2}->{1,0,1,0}}],Background->GrayLevel[.75],PlotRangePadding->None]

Out[]=

Branching from a Specific State

Here is showing how one can find all moves that follow from a specific state, (the same state from above). The mismatched game state from above is avoided.

traxMultiway[{{board,0}},1,8,GraphLayout->"RadialEmbedding",ImageSize->Large]

Out[]=

Future Plans

In the future, I plan to write some code to further prune the game tree, by allowing the user to remove “mate in two” moves, or “mate in n” moves up to infinity, at which point the graph should show only a single “perfect game” from some given starting position.

Cite this as: Eric Parfitt, "Visualizing Game Trees in "Trax" the Board Game" from the Notebook Archive (2025), https://notebookarchive.org/2025-03-bjmj60g

Visualizing Game Trees in “Trax” the Board Game

Introduction

Code

Game Tree Analysis

Code Overview Description

To generate the game tree:

To perform a move:

To add forced moves:

To check for a win:

Code Snippets

MoveForced

EdgeWinState

CanonicalizeBoard

Further use of the Code

Short Sample Game

Exemplifying Forced Tile Moves

Branching from a Specific State

Future Plans

Code
