Minimax – Embedded-Friendly Alpha-Beta Library for Arduino & C++

A single-header, STL-free implementation of classic Minimax search with α–β pruning, crafted for 2 KB microcontrollers yet flexible enough for desktop use.

• Tiny footprint – ≈ 5 KB flash
• Zero dynamic allocation – no new, no STL containers
• Template-based – plug in your board & move types
• Five-function API – override, compile, play
• Playable examples – Checkers, Connect Four, Gomoku & Othello

Most hobby libraries assume megabytes of RAM and std::vector.
This header was born while squeezing an AI into an ATmega328 (2 KB RAM).

# Clone into your libraries folder
cd ~/Documents/Arduino/libraries
git clone https://github.com/ripred/Minimax.git

lib_deps =
    ripred/Minimax @ ^1.0.0   ; once published

#include "Minimax.h"

struct Board   { /* … */ };
struct Move    { uint8_t r, c; };

class TicTacToeLogic : public Minimax<Board, Move>::GameLogic {
public:
    int  evaluate(const Board& s) override { /* +10 / −10 / 0 */ }
    int  generateMoves(const Board& s, Move mv[], int max) override { /* … */ }
    void applyMove(Board& s, const Move& m) override { /* … */ }
    bool isTerminal(const Board& s) override { /* win / draw */ }
    bool isMaximizingPlayer(const Board& s) override { return s.turn == 0; }
};

TicTacToeLogic logic;
Minimax<Board, Move, 9, 9> ai(logic);

void loop() {
    Board state = /* current board */;
    Move best   = ai.findBestMove(state);
    Serial.printf("AI chose %d,%d (score %d, nodes %d)\n",
                  best.r, best.c, ai.getBestScore(), ai.getNodesSearched());
}

Compile with -std=gnu++17 (earlier standards also work if your toolchain lacks C++17).

Implement these in a subclass of Minimax<GameState, Move>::GameLogic:

1. evaluate() – heuristic for the current player
2. generateMoves() – fill an array of legal moves, return count
3. applyMove() – mutate GameState with a move
4. isTerminal() – true on win/loss/draw
5. isMaximizingPlayer() – whose turn?

Open File → Examples → Minimax → (game) after installing, or compile on desktop to profile deeper depths.

Disable Serial prints in examples to save ~2 KB flash.

• Iterative deepening + time cut-off
• Optional transposition table when RAM ≥ 32 KB
• Board-symmetry pruning helpers

1. Fork → create feature branch
2. Follow coding style (4-space indents, snake_case, right-side const)
3. Submit PR – CI (AVR & x86) must pass

Bug reports and new example ports are very welcome!

Released under the MIT License – see LICENSE.

^{© 2025 by Trent M. Wyatt}