Gamescrafters: GamesmanClassic Introductory Guide

Table of Contents

Beginnings...

So, you want to add a game to Gamesman Classic! Well, you've come to the right place. This document provides an in-depth explanation of how a game, such as Abrobad, can be integrated into the system.

You can learn more about the game here.

This guide is divided into three main sections:

1. Solving Tic-Tac-Toe
2. New Game: Dissecting Abrobad
3. Solving Abrobad

Prerequisites

Before we begin, one should be familiar with Classic's hashing scheme, which can be read here. Furthermore, you should have fully implemented Homefun 1.

Needless to say, you should have GamesmanClassic downloaded to your device for the entire 'solver' portion, and need GamesmanUWAPI and GamesmanUni for the AutoGUI portion. You can find all the repos here.

Terminology

Piece and Stone may be used interchangeably.
Slot refers to one of the 12 places a piece can be placed or moved to.

Solving Tic-Tac-Toe

To start, we'll go over how Tic-Tac-Toe is implemented in GamesmanClassic. Afterwards, we'll look into a more complicated example that I ended up solving, Abrobad.

Tic-Tac-Toe (TTT) is a classic two-player, zero-sum game played on a 3×3 grid. Two players alternate marking the cells with their respective symbols (X and O). The game can end in either:

1. A win for one player if they manage to place three of their marks in a row (horizontal, vertical, or diagonal).
2. A tie if all cells are filled and no three-in-a-row exists.

Before implementing *Tic-Tac-Toe* in GamesmanClassic, it’s crucial to understand its mechanics and design efficient data structures and algorithms to solve it. Below, we detail the key components of its implementation as found in `mttt.c`.

Gameboard Representation and Designing Data Structures

Board as a Base-3 Integer

In `mttt.c`, each board position is represented as an integer in the range [0, 3⁹ - 1], where each of the 9 cells in the 3×3 grid can be in one of three states:

• Blank → 0
• o → 1
• x → 2

This base-3 encoding offers several significant advantages:

1. Memory Efficiency: A single 32-bit integer (range up to 2,147,483,647) can easily represent all possible Tic-Tac-Toe positions (3⁹ = 19,683 total positions), making it extremely space-efficient.
2. Fast Hashing: The integer itself serves as a perfect hash function, eliminating the need for complex hashing algorithms. Each position has a unique integer representation.
3. Cache Performance: Single integer comparisons are among the fastest operations a CPU can perform, and the compact representation improves cache locality when storing many positions.
4. Simplified State Management: The entire game state is contained in a single value, making it easy to copy, compare, and pass between functions.

The array `g3Array` contains the powers of 3, where each element represents 3^position for each cell in the grid. Since our board state is encoded as a base-3 integer, we can use this array to convert between the two representations. We'll precompute this array on the very top of the file.

int g3Array[] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561 };

Position Conversion Functions

Two functions handle conversions between the integer representation and an array of cell states:

• PositionToBlankOX(POSITION thePos, BlankOX *theBlankOX): Converts the integer `thePos` into a 9-element array `theBlankOX` by extracting base-3 digits, mapping them to `Blank`, `o`, or `x`.
• BlankOXToPosition(BlankOX *theBlankOX): Combines a 9-element `theBlankOX` array into a single base-3 integer using `g3Array`.

These conversions are critical for manipulating the board state efficiently.

Symmetry Handling

*Tic-Tac-Toe* exhibits symmetries (rotations and reflections), which `mttt.c` leverages to reduce the number of unique positions stored. This is optional and controlled by:

/**
 * If kSupportsSymmetries is TRUE, we reduce memory usage by canonicalizing.
 */
BOOLEAN kSupportsSymmetries = TRUE;

The function `GetCanonicalPosition(POSITION position)` computes the smallest integer representation among all symmetric equivalents by applying 8 symmetry operations (4 rotations and 4 flipped rotations), defined in `gSymmetryMatrix`.

Game-Specific Data Structures

Several data structures are used:

• BlankOX: An enum with values `Blank`, `o`, `x` to represent cell states.
• gPosition: A global struct containing:
  • BlankOX board[BOARDSIZE]: The current board state.
  • BlankOX nextPiece: The piece to be placed next (`x` or `o`).
  • int piecesPlaced: The number of pieces on the board.
• g3Array: An array of powers of 3 for position encoding.
• gSymmetryMatrix[NUMSYMMETRIES][BOARDSIZE]: A 2D array mapping each cell to its position under each symmetry operation.

Core Functions: GenerateMoves, DoMove, and Primitive

Similarly to HF1, we'll need to define three core functions: GenerateMoves(), DoMove(), and Primitive()

As a refresher, here's the high-level idea of how these functions work:

1. MOVELIST GenerateMove*(POSITION position)
   1. "Return the head of a list of the legal moves from the input position."
   2. Think of a LinkedList from CS61A. GenerateMove should return a *MOVELIST*, which essentially is a LinkedList. The head of a linked list of the legal moves from the input position.
2. POSITION DoMove(POSITION position, MOVE move)
   1. Return the child position reached when the input move is made from the input position.
3. VALUE Primitive(POSITION position)
   1. Return win, lose, or tie if the input position is primitive. Otherwise, return undecided.

Generating Moves

The GenerateMoves(POSITION position) function generates a linked list of all possible moves from a given position. In Tic-Tac-Toe, a move is placing a piece in an empty cell:

• It converts the position to a BlankOX array (if not using gPosition).
• It iterates over the 9 cells, adding the index of each Blank cell to the move list using CreateMovelistNode.

MOVELIST *GenerateMoves(POSITION position) {
    int index;
    MOVELIST *moves = NULL;
    if (!gUseGPS)
        PositionToBlankOX(position, gPosition.board);
    for (index = 0; index < BOARDSIZE; ++index)
        if (gPosition.board[index] == Blank)
            moves = CreateMovelistNode(index, moves);
    return moves;
}

Moves are represented as integers from 0 to 8, corresponding to the 9 cells.

Applying Moves

The DoMove(POSITION position, MOVE move) function applies a move to the current position and returns the new position. It supports two modes:

• With `gUseGPS` (Global Position State):
  • Updates gPosition.board[move] with gPosition.nextPiece.
  • Toggles gPosition.nextPiece between x and o.
  • Increments gPosition.piecesPlaced.
  • Converts the updated board back to a position integer.
• Without `gUseGPS`:
  • Converts the position to a BlankOX array.
  • Determines the current player with WhoseTurn.
  • Updates the position integer by adding the player’s value (1 for o, 2 for x) multiplied by the appropriate power of 3 from g3Array.

POSITION DoMove(POSITION position, MOVE move) {
    if (gUseGPS) {
        gPosition.board[move] = gPosition.nextPiece;
        gPosition.nextPiece = gPosition.nextPiece == x ? o : x;
        ++gPosition.piecesPlaced;
        return BlankOXToPosition(gPosition.board);
    } else {
        BlankOX board[BOARDSIZE];
        PositionToBlankOX(position, board);
        return position + g3Array[move] * (int) WhoseTurn(board);
    }
}

An UndoMove(MOVE move) function is also provided to revert moves when using gUseGPS.

Primitive Positions

The Primitive(POSITION position) function determines if a position is terminal:

• Checks for three-in-a-row using ThreeInARow across all rows, columns, and diagonals.
  • If found, returns lose (standard game) or win (misère game) for the player to move, as the previous player won.
• Checks if the board is full (no Blank cells) using AllFilledIn or gPosition.piecesPlaced.
  • If full and no win, returns tie.
• Otherwise, returns undecided.

VALUE Primitive(POSITION position) {
    if (!gUseGPS)
        PositionToBlankOX(position, gPosition.board);
    if (ThreeInARow(gPosition.board, 0, 1, 2) ||
        ThreeInARow(gPosition.board, 3, 4, 5) ||
        ThreeInARow(gPosition.board, 6, 7, 8) ||
        ThreeInARow(gPosition.board, 0, 3, 6) ||
        ThreeInARow(gPosition.board, 1, 4, 7) ||
        ThreeInARow(gPosition.board, 2, 5, 8) ||
        ThreeInARow(gPosition.board, 0, 4, 8) ||
        ThreeInARow(gPosition.board, 2, 4, 6))
        return gStandardGame ? lose : win;
    else if ((gUseGPS && (gPosition.piecesPlaced == BOARDSIZE)) ||
             ((!gUseGPS) && AllFilledIn(gPosition.board)))
        return tie;
    else
        return undecided;
}

The helper function ThreeInARow(BlankOX *theBlankOX, int a, int b, int c) checks if three cells contain the same non-Blank value.

Dissecting Abrobad

Similar to a design document before starting a large project, it is important to understand your game's ins and outs and begin thinking of data structures and algorithms that you can leverage to solve the game!

To start, Abrobad is a game involving the strategic placement and movement of pieces. The game concludes when the entire board is filled.

The rules are as follows:

1. Pieces can be placed in any open slot on the board where none of the adjacent slots contain a piece of your color.
2. If placement moves are unavailable, you may move a stone in any of the 6 main directions to the nearest open space in that direction (by jumping if necessary).
3. If placement moves are unavailable, you may opt to END GAME. Doing so fills all remaining open positions with the opponent's pieces. Additionally, if you place a piece in the last available open position, the game ends.

A primitive position is a position where the board is completely filled. To determine the winner, count the number of strongly connected components (SCCs) for each player's pieces. If it is the case that your count of SCCs is less than or equal to the number of your opponent's SCCs, you win. Otherwise, you lose. By construction of the game, it is impossible to tie the game.

Algorithmically, if you recall CS61Bs or CS70s graph theory, we can count each player's SCCs using Depth First Search (DFS).

Gameboard Representation and Designing Data Structures

An important question that you should start thinking about early is how you want to represent the board. Typically, this is done through some string, where the i-th position of the string corresponds to the i-th + 1 board position.

/**
 * Extracts the board state and current player from a position.
 * @param position The game position to decode
 */
void get_board_and_player_from_position(POSITION position) {
  char board[BOARDSIZE + 1];
  generic_hash_unhash(position, board);
  int player = generic_hash_turn(position);
}

However, with Abrobad, a string alone doesn't provide enough information necessary to implement the game functionality, as we need some manner of tracking adjacency in the board when we start generating moves. We note that Abrobad follows a unique board layout, we'll have to define a graph-like representation using an Adjacency Matrix. I would recommend constructing this for every game.

void print_entire_adj_list(int adj_matrix[BOARDSIZE][BOARDSIZE]) {
  for (int i = 0; i < BOARDSIZE; i++) {
    printf("Adjacency list for index %d: [", i);
    int first = 1;
    for (int j = 0; j < BOARDSIZE; j++) {
      if (adj_matrix[i][j]) {
        if (!first) {
          printf(", ");
        }
        printf("%d", j);
        first = 0;
      }
    }
    printf("]\n");
  }
}

/***************************************
* Example output:
* Adjacency list for index 0: [1, 2, 3]
* Adjacency list for index 1: [0, 3, 4]
* Adjacency list for index 2: [0, 3, 5, 6]
* Adjacency list for index 3: [0, 1, 2, 4, 6, 7]
{{ ... }}
* Adjacency list for index 2: [0, 3, 5, 6]
* Adjacency list for index 3: [0, 1, 2, 4, 6, 7]
.
.
.
***************************************/

Using this adjacency matrix, when we begin implementing GenerateMoves*(), we can quickly discern if placement moves are possible by iterating over each of the slots of the board and checking if the adjacent slots contain the current player's piece.

If you recall the rules of moving a piece, the piece can potentially jump over other pieces, so maintaining just an adjacency matrix won't be sufficient. To support jumps, we note that there is a fixed set of options for the piece from any slot on the board. Therefore, similarly to the adjacency matrix, we can define the list of slots that we can jump our piece to, and check if that specific position is open. However, it goes a step further, Schrodingersince we are only jumping to the nearest adjacent position. We'll define as int neighbors[BOARDSIZE][6][4].

To see these implementations, please see the Abrobad Implementation on GitHub.

Solving Abrobad

Now that we understand how Abrobad works, let's start implementing the game!

First, navigate to your project directory and copy the mtemplate.c file into a new file called mabrobad.c.

cp mtemplate.c mabrobad.c

In mabrobad.c, you'll find some configurable BOOLEAN values that determine game behavior. For Abrobad, we set the following:

/**
 * Game configuration settings
 */
kLoopy = TRUE;             // Abrobad can have loops in gameplay
kSupportsSymmetries = FALSE; // We are not implementing symmetries

Game Initialization

The first function you'll encounter in mabrobad.c is void InitializeGame(void). This function sets up the game by initializing the starting position of the game, constructing the number of positions the game has, and creating the hash data.

/**
 * Initializes the game state and configuration.
 * Sets up the board size, hash data, and initial position.
 */
void InitializeGame(void) {
  int BOARDSIZE = 12;
  
  // Set canonical position function pointer
  gCanonicalPosition = GetCanonicalPosition;
  
  // Define hash data for board representation
  // Format: [piece type, min count, max count, ...]
  int hash_data[] = {'-', 0, 12, 'X', 0, 12, 'O', 0, 12, -1};
  
  // Initialize hash and get total number of positions
  gNumberOfPositions = generic_hash_init(BOARDSIZE, hash_data, NULL, 0);
  
  // Create initial empty board and hash it
  char start[BOARDSIZE + 1] = "------------";
  gInitialPosition = generic_hash_hash(start, 1);
  
  // Set position to string conversion function
  gPositionToStringFunPtr = &PositionToString;
}

We designate empty spaces as -, P1 pieces as X and P2 pieces as O. You can designate the player pieces as whatever you want, but empty spaces should be -.

Since Abrobad has 12 total slots, we set our hash data to the following:

int hash_data[] = {'-', 0, 12, 'X', 0, 12, 'O', 0, 12, -1};

Given the hash_data[] array, we can set the total number of positions for the game by defining the value of gNumberOfPositions. Finally, we can construct the hash of the initial position of the game, gInitialPosition. I recommend reviewing the Hashing document if you are what we're doing here.

Completing Primitive()

To determine whether a position is primitive, we need to count the number of strongly connected components (SCCs) for the player's pieces. Say that we iterate through the game board starting from the top leftmost position. We use Depth First Search (DFS) from that slot to designate the entire "clump" of the player's pieces as a single SCC.

To avoid overcounting SCCs as we iterate through the board, we construct a copy of an empty board that gets filled with pieces visited during DFS. This copy allows us to efficiently check if a piece has already been accounted for as part of an SCC.

The approach is as follows:

• Start with an empty "visited" board to keep track of explored pieces.
• For each position on the game board:
  1. If the current position contains a player's piece and has not yet been visited in the "visited" board:
     • Perform DFS starting from this position.
     • Mark all visited positions in the "visited" board.
     • Increment the SCC count by 1.
  2. Otherwise, skip the position (it has already been accounted for in a previous SCC).

Counting Strongly Connected Components

The function CountPlayerGroups identifies and counts the strongly connected components (SCCs) of pieces belonging to the given player. It uses DFS to traverse and mark visited components.

/**
 * Counts the number of connected component groups for a player
 *
 * @param player  The player whose groups to count
 * @param board   The current board state
 * @return        The number of distinct groups
 */
CountPlayerGroups(player, board)
    groupCount ← 0
    visited ← Array of size BOARDSIZE initialized to FALSE
    piece ← Player's piece identifier (e.g., 'X' or 'O')
    
    FOR i ← 0 TO BOARDSIZE - 1
        IF board[i] = piece AND visited[i] = FALSE THEN
            DFS(i, piece, visited, board)
            groupCount ← groupCount + 1
        ENDIF
    ENDFOR
    
    RETURN groupCount

Pseudocode for Primitive Evaluation

/**
 * Determines if the current position is a primitive (terminal) position
 * and returns the appropriate game value
 *
 * @param position  The position to evaluate
 * @return          win, lose, tie, or undecided
 */
VALUE Primitive(POSITION position)
    board ← Board representation derived from position
    
    // If there are empty slots, the game is not over
    IF board contains '-' (empty slot) THEN
        RETURN undecided
    ENDIF
    
    // Determine current player and opponent
    player ← Player to move derived from position
    opponent ← 3 - player
    
    // Count connected component groups for each player
    playerGroups ← CountPlayerGroups(player, board)
    opponentGroups ← CountPlayerGroups(opponent, board)
    
    // Apply Abrobad winning condition
    IF playerGroups ≥ opponentGroups THEN
        RETURN lose
    ELSE
        RETURN win
    ENDIF

The code is essentially a pseudo-solution to the leetcode problem 'Number of Islands'.

Completing GenerateMove*()

Given a position, can we determine what moves are available? I like to tackle this problem case-by-case style. Firstly, there are placement moves and movement moves. If it were possible to have a placement move, then it wouldn't be possible to move any of our pieces, let alone declare to END GAME, so we'll start with placements.

Placement Moves

We can scan the board and determine the places where placements are possible. Recall that placement of one's piece is possible only when the adjacent tiles do not have the color of your piece. Reference the first half of GenerateMove*() if interested in how this is done, but should be pretty self-explanatory.

Movement Moves

Using the int neighbors[BOARDSIZE][6][4] data structure from the mabrobad.c file, we can implement the movement moves.

Firstly, if placement moves are possible, then we don't have to bother checking for movement moves. Otherwise, we can iterate through neighbors and determine if there is an open slot in that direction. We predefined the values such the values at the 0th-index are closest to the piece, and the following values expand one piece further in that direction. After selecting all the nearest possible jumps a piece can take, we do the same for every other one of the player's pieces. Finally, we add the END GAME move to the end of our return value.

Remarks

Because we were methodical while constructing neighbors, we didn't have to construct an overly complicated or computationally expensive GenerateMove*(). If it were the case where your game is large, I would consider err-ing towards the side of creating helper functions to create these data structures rather than resorting to a complicated GenerateMove*().

Completing DoMove()

At a high-level, DoMove() is simpler to implement than the other two functions. Given the current position and a move to be made, we make the move for that particular player's turn, and return the new updated position. However, while we have talked about Board representation throughout this guide, we haven't mentioned Move representation, which is important for implementing DoMove().

Move Representation

In GamesmanClassic, a move is stored as a single integer (MOVE), which serves as a compact way of encoding the necessary information for making a change to the board state. This integer encoding must capture:

1. What type of move is being made (e.g., a placement, a piece movement, or a special move like END_MOVE).
2. The move's parameters, such as which slot to place in or, for a movement, which slot is being moved from and to.

Why encode moves as integers?

• Solver Integration: Many of Gamesman's solvers store “child positions” as a result of applying integer-encoded moves to a parent position.
• Speed and Simplicity: Integers are fast to compare, hash, and pass around internally. This allows the solver code to remain lean and efficient.
• Generality: Even if your game’s logic involves complex movement (like multiple jumps), you can still encode that into a single integer according to your own scheme.

Example Scheme for Abrobad

In mabrobad.c, we use the following scheme to encode moves:

• #define END_MOVE 0
  • Sentinel to indicate an END GAME move.
• #define PLACE_PIECE(pos) (pos)
  • Board indices range from 1..12 (human-facing). Placing a piece on slot i is simply the integer i.
• #define MOVE_PIECE(start, end) (((start * 13) + end) + 12)
  • For movement, note that the maximum start slot is 12 and the maximum end slot is also 12.
  • We pack them into a single integer by multiplying start by 13, adding end, and then offsetting by 12.

For this, we'll leverage concepts of modular arithmetic! Breaking this down:

• Placing a piece on an empty slot pos is encoded directly by the integer pos. Since valid positions range from 1 to 12, any integer ≤ 12 corresponds to a placement move.
• Moving a piece from a slot start to a slot end is encoded by first multiplying start by 13, adding end, and then offsetting by 12. Thus, move = (13 × start) + end + 12. Because start and end each range from 1..12, this formula ensures an unambiguous integer result that’s always ≥ 13.
• Ending the game (a forced fill of the remaining slots) is a move encoded as END_MOVE = 0.

Decoding the Move

To apply a move, you must decode the integer to figure out which action to take. For Abrobad, we proceed as follows:

• void decode_move(MOVE move, int* start, int* end)
  • int tmp = move - 12;
  • *start = tmp / 13; // recover start
  • *end = tmp % 13; // recover end
• Pseudocode usage:
  • Case 1: if (move == END_MOVE)
    Fill all remaining open positions with the opponent's pieces.
  • Case 2: else if (move <= 12)
    Treat move as placing a piece on slot move.
  • Case 3: else
    Decode the movement via decode_move(move, &s, &e); and move the piece from slot s to e.

This scheme cleanly divides possible MOVE values into distinct categories (end-game, placement, or movement) and allows for swift encoding/decoding within the solver and user-interface logic.

Tips for Designing a Custom Move Encoding

• Reserve a sentinel value (like 0) for special moves such as “pass” or “end the game.” If your game doesn't have any such moves, then don't worry about this!
• Ensure no overlap between placement and movement. In Abrobad, by offsetting movement moves by +12, we avoid clashing with the 1..12 range for placements.
• Keep expansions in mind. If new move types arise (e.g., multiple jumps, reconfigured boards), design an encoding that can scale without collisions.

Depth First Search (DFS) for SCC Detection

The DFS function traverses all connected positions for a given piece, marking visited nodes as it goes. It recursively visits neighboring nodes.

/**
 * Depth-First Search algorithm to identify connected components
 * 
 * @param node      The current node being visited
 * @param piece     The piece type we're searching for ('X' or 'O')
 * @param visited   Boolean array tracking visited nodes
 * @param board     Current board state
 */
DFS(node, piece, visited, board)
    // Mark current node as visited
    visited[node] ← TRUE
    
    // Recursively visit all unvisited neighbors of the same piece type
    FOR each neighbor in adjacency list of node
        IF visited[neighbor] = FALSE AND board[neighbor] = piece THEN
            DFS(neighbor, piece, visited, board)
        ENDIF
    ENDFOR

AutoGUI

We'll be skipping the AutoGUI implementation (only going to give a quick primer) as the rest of the functions are relatively well documented and entirely up to you when it comes to designing (e.g., PrintPosition). Feel free to browse through other game implementations for inspiration.

The AutoGUI is how we'll bring our game to life! While we've been exclusively working on GamesmanClassic, the rest of the document will be worked on two additional repos, GamesmanUWAPI (middleware) and GamesmanUni (frontend).

This won't be a AutoGUI guide, as we already have a pre-existing guide (this other one is outdated but has some important information that is necessary), so instead we'll go into the specifics of Abrobad AutoGUI design and how you can complete AutoGUI for your own game!

Recall that we've been representing the board as a string. What we want to do is represent each one of the slots in the string as a designated position on some image. What image you may ask? Well, the image that you see when you're playing any game on GamesmanUni! Take an empty board of Abrobad for example:

Each one of the 12 slots in the position string should correspond to each one of the actual positions on the image. Depending on the dimensions of the image, we can define the tile centers to correspond to each of the 12 slots of the position string. When creating the actual image, I would just stick to using ChatGPT to come up with the .svg file. Alternate tools include Adobe Illustrator and Google Drawings.

The caveat with Abrobad is that we need to have a custom button, ENDGAME. We can include one additional slot to the AutoGUI position string for the new button and give it a custom value. We'll demark this value as E for ENDGAME and when the autogui position string has 'E' at the very end, that means the {ENDGAME} button should appear.

Conclusion

Congrats if you've made it this far in the document!

Gamescrafters was a very rewarding and fun experience during my time at Cal, and I hope that you (the reader) will also take pride in the group similarly to how I felt. Feel free to contact me if you are interested in talking more about Gamescrafters, Cal, or puzzles in general, I would love to talk!

In the meanwhile... check out Abrobad!