MAGPIE

Macondo Accordant Game Program and Inference Engine

MAGPIE is a crossword game playing and analysis program that supports the following features:

• Static move generation
• Montecarlo simulation
• Exhaustive inferences
• Autoplay
• Superleave generation
• Exhaustive endgame

MAGPIE started as a C rewrite of Macondo but has since incorporated a variety of new features, algorithms, and data structures. It uses several concepts originally developed in wolges, including shadow playing and the KWG and KLV data structures.

Getting Started

From this page, download and unzip the MAGPIE repo or use git clone:

git clone https://github.com/jvc56/MAGPIE.git

then navigate into the MAGPIE directory

cd MAGPIE

and run the setup command

./setup.sh

You should now be able to run the compiled MAGPIE executable:

./bin/magpie

This will start MAGPIE in async interactive mode by default. For more details on different ways to run MAGPIE, see Execution Modes.

Usage

Commands and Settings

MAGPIE accepts two different kinds of arguments: commands and settings.

Commands perform a specific action and settings affect how the actions are performed. Some commands can take positional arguments that could be required or optional. Command arguments only apply to the given command. Settings persist between commands and only change when overwritten by a new specified value. Settings are always denoted by a - character. Any number of settings can be specified for any command.

For example, in the following command:

magpie> autoplay games 100 -lex CSW21 -threads 4 -hr true

The autoplay text is the command and the games and 100 text are the positional arguments. Everything else is a setting which will apply to the next command, so running the subsequent command:

magpie> autoplay games 50 -lex CSW21 -threads 4 -hr true

will play 50 games in the CSW21 lexicon with 4 threads and print the results in a human readable format.

Autoplay can use PlayChooser for either or both players. -pc1 and -pc2 set each player's total per-game clock in milliseconds; -1 disables it (the default), and 0 enables it without a clock. For example, this gives both players a 30-second clock:

magpie> autoplay games 100 -pc1 30000 -pc2 30000 -hr true

PlayChooser selects its evaluation mode from the position, using simulation, pre-endgame, or endgame analysis as appropriate. Timed games deduct 10 points per started minute of overtime by default. The penalty and period are configurable independently, so blitz runs can deduct one point per started second:

magpie> autoplay games 100 -pc1 5000 -pc2 5000 -otpenalty 1 -otperiod 1000 -hr true

When at least one player uses PlayChooser, the final report includes clock usage, overtime, and deducted penalty points for each active player.

Games with a clocked player are not reproducible from the seed. How much search fits in the budget varies with machine load, thread count, and build, so the same -seed will not replay the same moves, and the overtime penalty itself varies between runs. This is inherent to timed play rather than a defect, but it is worth knowing because the rest of autoplay is seed-deterministic. The intended output is the aggregate: win percentage, spread, and penalty points over enough games. Individual games are not meant to be replayed.

For the same reason, game pairs (-gp) lose their variance-reduction property when combined with a clock. Pairs work by having both games see identical draws so that only the players' decisions differ; with timing on, the two games can diverge for reasons unrelated to strategy.

How much search a clock buys also depends on the threading mode, so the same -pc1 value is not comparable across -mtmode settings:

• Per-game parallelism (-mtmode pgp, the default) runs -threads games at once and gives each game's PlayChooser a single thread. Raising -threads finishes the run sooner but does not give any player more search per second of clock — until the thread count exceeds the machine's available cores, at which point games contend for CPU and the same budget buys measurably less.
• Intra-game parallelism (-mtmode igp) plays one game at a time and gives that game's PlayChooser every thread, so the same clock buys roughly -threads times as much search per move.

Compare timed runs only against other runs with the same -mtmode and -threads.

All commands and settings can be specified by the shortest unambiguous string. For example, the generate command can be specified by any of the following strings:

magpie> generat
magpie> genera
magpie> gen

Some commands have one character shortcuts such as the generate and shgame commands:

magpie> g
magpie> s

To print more details about commands and settings, run the help command:

magpie> help

To see details for a specific command or setting, provide the command or setting when invoking the help command:

magpie> help autoplay
magpie> help lex

Load and Save Settings

On startup, MAGPIE will check for a settings.txt file in the current directory and will load the settings saved in that file if it exists. By default, after every successful command that is not invoked in script mode, MAGPIE will save the current settings to settings.txt so they do not have to be reentered on the next startup. To disable this feature, set the "savesettings" setting to false.

Execution Modes

MAGPIE can operate in multiple modes, which are described below:

Script Mode

Script mode executes a single command and then exits immediately. To run in script mode, the following conditions must be met:

• A command which is not set or cgp is given
• No execution mode is specified with the mode setting.

If the conditions above are not met, MAGPIE will run in interactive mode and wait for user input.

Interactive Modes (REPL)

The interactive modes of MAGPIE implement a Read-Evaluate-Print-Loop which continuously listens for and executes user input.

Asynchronous Interactive Mode

Asynchronous mode allows the user to either stop or query the status of the currently running command, with the stop and status asynchronous commands respectively. This mode is enabled by default and can be set with the -mode async setting.

In async mode a long running sim and be checked for progress and stopped at anytime during execution:

magpie> new
(... game output ...)
magpie> r AEEINNR
magpie> gs
sta
(... current sim results ...)

sto
(... final sim results ...)

magpie>

The asynchronous commands can also be specified by their shortest unambiguous strings.

Synchronous Interactive Mode

Synchronous mode blocks while a command is running and will not accept new commands until the previous command has completed. This mode can be set with the -mode sync setting. It is not recommended for human users to run in sync mode.

For running many commands programatically from another process, it is recommended to use sync mode instead of script mode to avoid the overhead startup costs.

API Library

Programs can embed MAGPIE through a string -> string C API. Build the shared library with

make libmagpie

which produces bin/libmagpie.so (bin/libmagpie.dylib on macOS) exporting only the magpie_* functions declared in src/impl/cmd_api.h — that header plus the shared library is the entire embedding surface.

The API is command-oriented: callers create an opaque Magpie handle, pass it the same command strings the console accepts, and read the resulting output back as a string. Output is machine readable by default; the *_human_readable function variants format it for display instead. Commands can run synchronously (magpie_run_sync) or on a background thread (magpie_run_async), with magpie_get_last_command_status_message for mid-run progress, magpie_stop_current_command to interrupt, and magpie_await to collect the result. All returned strings are owned by the caller and freed with magpie_free_string.

See examples/generate_moves.c for a minimal C client (build it with make examples) and examples/magpie.py for a Python ctypes wrapper with an interactive REPL.

Data

The setup.sh command will download the necessary lexical data for several common lexica into the ./data directory organized into 4 subdirectories. All lexical, board layout, and strategy data must be saved in their respective directories for MAGPIE to find them. When specifying input data in MAGPIE, always use the basename without the file extension.

layouts

This directory contains the layout files which specify the start square and bonus squares for the board. The start square is denoted by the row, column integers on the first row, followed by the board layout bonus square. Only the following bonus squares are valid:

• (no bonus)
• ' (double letter)
• - (double word)
• " (triple letter)
• = (triple word)
• ^ (quadruple letter)
• ~ (quadruple word)
• # (brick, an unplayable square)

The height and width of the board are denoted by the compile time constant BOARD_DIM which can be overwritten during compilation. For example, compiling with:

make magpie BUILD=release BOARD_DIM=21

will compile a MAGPIE executable that only accepts layouts of 21x21.

letterdistributions

This directory contains the letter distribution CSV files which specify the frequency, score, and display of each tile. The format is:

<uppercase_letter>,<lowercase_letter>,<frequency>,<score>,<is_vowel>,[<fullwidth_uppercase_letter>,<full_width_lowercase_letter>]

The full width display characters can be optionally specified at the end of the row. Setting a new lexicon with the lexicon setting will set a default letter distribution if the lexicon name has a known prefix. Below is a list of lexicon prefixes and their default letter distributions:

• CSW, NWL, OSPD, OSW, America, CEL -> english
• RD -> german
• NSF -> norwegian
• DISC -> catalan
• FRA -> french
• OSPS -> polish
• DSW -> dutch

lexica

This directory contains the following file types:

• .txt (plain text lexica files)
• .kwg (Kurnia Word Graph (KWG), courtesy of wolges)
• .klv (KWG that stores leave values, courtesy of wolges)
• .wmp (Word Maps)

strategy

This directory contains win percentage lookup tables used in Monte Carlo simulations.

Examples

Annotating a game

The following example demonstrates some of the more common game annotation commands. To see all of the available commands, invoke the help command.

First, set the lexicon:

magpie> set -lex CSW24

then start a new game:

magpie> new

player names can be specified with the p1 and p2 commands:

magpie> p1 Adam Logan
magpie> p2 Nigel Richards

at any point in the game, player names can be switched with the switchnames command:

magpie> sw

specify the rack for the player on turn:

magpie> r EEIJNP?

generate moves with the given rack:

magpie> g

sim the generated moves:

magpie> sim

to generate moves and sim in a single command, use the gsim command:

magpie> gsim

to set the rack, generate moves, and then sim in a single command, use the rgsimulate command:

magpie> rgs RETINAS

to commit a play, use the commit command:

magpie> c 1

alternatively, the current best move can be commited with the tcommit command:

magpie> t

which commits the top simming move if there are sim results available, otherwise it will commit the top static move. To challenge the previous play, use the challenge command:

magpie> chal

this will either remove the previous play if it formed a phony word or add a challenge bonus if not. Challenge bonuses for any play can be removed at any point in the game without affecting the subsequent move with the unchallenge command:

magpie> unchal

To save the game as a GCG file, use the export command:

magpie> e

The export command will give the file a default name if no name is provided.

Analyzing a game from xtables or woogles.io

First, set the lexicon:

magpie> set -lex CSW24

then import the game

magpie> load 54515

the load command can take several different types of input which are explained in further detail in the help command.

To navigate through the game, use goto

magpie> goto end
magpie> gsim
magpie> goto start
magpie> gsim
magpie> goto 10
magpie> gsim
magpie> goto 3
magpie> infer

Solving a pre-endgame

The peg command solves a pre-endgame (1 to 4 tiles in the bag): for each candidate move it enumerates the possible bag/opponent-rack orderings, solves the resulting endgames, and reports each move's win percentage and spread.

Load a position with cgp and run peg:

magpie> cgp 15/3Q7U3/3U2TAURINE2/1CHANSONS2W3/2AI6JO3/DIRL1PO3IN3/E1D2EF3V4/F1I2p1TRAIK3/O1L2T4E4/ABy1PIT2BRIG2/ME1MOZELLE5/1GRADE1O1NOH3/WE3R1V7/AT5E7/G6D7 ENOSTXY/ACEISUY 356/378 0 -lex NWL20
magpie> peg

By default the solver generates all root moves and assumes a rational opponent (it replies with its best-equity move). An optional positional argument restricts the search to a fixed set of root candidates instead of generating all moves. Moves are comma-separated UCGI with no spaces — coordinate and tiles joined by a period, pass as pass (exchanges are not valid PEG moves):

magpie> peg 13L.ONYX,13L.OXY

The case-insensitive word empty restricts the search to every generated move that would empty the bag (plays at least as many tiles as remain in the bag):

magpie> peg empty

Several settings tune the search further; see help peg, help pnoprune, etc. for full descriptions:

• -pegpess true switches to the pessimistic opponent model (the opponent plays the worst-for-you reply) — i.e. guaranteed-win analysis.
• -pnoprune <moves> protects moves from being cut by the halving cascade so they are evaluated at full fidelity even if their win% rank falls below the cut.
• -pegtopk <count1>,<count2>,... overrides the per-stage halving counts (default 32,16,8,4,2). Stage 0 always greedy-evaluates every candidate play; each count is how many top plays are then kept and re-ranked at the next ply of fidelity (so the default keeps the top 32 after stage 0, then narrows 16/8/4/2 across the halving stages). A single all (or 0) is the exhaustive setting: it keeps every candidate and solves each at full endgame depth in one deep stage, with full scenario enumeration (it ignores -pegstride).
• -pegstride <n> samples ~1/n of the scenarios for bag >= 3 (faster, approximate).

Use - to clear pnoprune.

Speed vs. accuracy

The same peg command spans a spectrum from a fast in-game estimate to an exhaustive analysis, controlled by a few knobs:

• Scenario coverage — -pegstride. Stride 1 (the default) enumerates every bag/opponent-rack ordering. -pegstride <n> instead samples ~1/n of them (reweighted to preserve the expected aggregate), trading accuracy for speed; it applies only at bag ≥ 3 (bag ≤ 2 is always fully enumerated). A larger stride is the single biggest speedup.
• Search depth — -pegtopk. A longer/wider schedule carries more candidates into the deeper, higher-fidelity stages (where bag-emptying leaves are solved further), so it is more accurate but slower; a shorter/narrower schedule is faster and coarser. Stage 0 always greedy-scores every move, so even an interrupted run returns a ranked answer.
• Time — -tlim <seconds>. The solver returns the best answer it has when the limit hits (stage 0 finishes first, then each halving stage refines). With no limit it runs the full schedule to completion.
• Cores — -threads <n>. Pure speedup at the same accuracy.

So a quick in-game read might sample scenarios under a time cap, while an exhaustive study enumerates everything and solves to game end. The most thorough setting is -pegtopk all: after the greedy stage 0 it runs a single deep stage that keeps every candidate, enumerates every scenario (no stride), and solves each bag-emptying leaf at full endgame depth — no narrowing, no truncation:

magpie> peg -pegstride 7 -tlim 5    # fast: sampled, 5s cap
magpie> peg                         # default: full enumeration, halving cascade, uncapped time
magpie> peg -pegtopk all            # exhaustive: every play, full-depth endgame, no caps

(-pegtopk all — or 0 — forces full enumeration regardless of -pegstride; with no -tlim it is uncapped in time.) How far this extreme is practical depends on the bag: at 1-in-bag, exhaustively solving every candidate is realistic for most positions given enough time; at 4-in-bag it can take effectively forever — but you can still configure and run it.

The leaf evaluation is an exact endgame_solve for bag-emptying scenarios but a greedy playout (averaged over the leftover-bag orderings) for the rest, so even the exhaustive end is a very strong estimate rather than a literal proof.

Comparing lexica

To play two lexica against each other to see which is stronger, you can create the required lexical data from text files and run the autoplay command. First, set the letter distribution:

magpie> set -ld english

then convert the text files to the KWG and WMP. The following example assumes a text file called CSW50.txt is saved to ./data/lexica:

magpie> convert text2kwg CSW50
magpie> convert text2wordmap CSW50
magpie> convert text2kwg CSW60
magpie> convert text2wordmap CSW60

both text file must contain one word per line in all uppercase. Once converted, you can run the autoplay command

magpie> autoplay games 10000 -l1 CSW50 -l2 CSW60 -leaves CSW21 -gp true -hr true -pfreq 10000

It is highly recommended to run with game pairs to reduce statistical noise. To see more details about game pairs, use help gp.