Spaces:
Running on Zero
Running on Zero
File size: 2,153 Bytes
2cf2375 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | ---
title: Bestemshe God Algorithm
emoji: 🎯
colorFrom: yellow
colorTo: red
sdk: gradio
sdk_version: 6.20.0
python_version: "3.12"
app_file: app.py
pinned: false
license: cc-by-4.0
---
# Bestemshe — Strongly Solved
Bestemshe is a Mancala variant (2×5 pits, 2 kazans, 50 stones). This repo contains
the HPC retrograde solver that strongly solved the game, the resulting ~8.3GB
zstd-compressed endgame tablebase, and a **Tablebase Explorer** web UI.
**Game-theoretic value of the starting position: the first player LOSES with perfect play.**
## Components
| File | Purpose |
|---|---|
| `main.cpp`, `Solver.{h,cpp}`, `Compressor.{h,cpp}`, `Inference.h` | HPC solver / verifier / compressor (`./bestemshe`) |
| `Oracle.h`, `query.cpp` | Explorer CLI: mmap + single-block zstd decode, ~20MB RSS per query (`./query`) |
| `app.py` | Gradio UI (calls `./query` via subprocess) |
| `layers/compressed/` | Tablebase: `layer_<K1>_<K2>_{win,draw}.bin` (not in the GitHub repo; LFS on the HF Space) |
## Build & run locally
```bash
brew install zstd libomp # macOS prerequisites (Linux: apt install libzstd-dev)
make # solver: ./bestemshe
make query # explorer CLI: ./query
./query 0 0 5 5 5 5 5 5 5 5 5 5 # JSON eval of the start position
pip install -r requirements.txt
python app.py # http://localhost:7860
```
Position format: 12 integers `K1 K2 p0..p9`, side-to-move perspective
(K1/p0–p4 = mover). Stones total 50; kazans are even. Evaluations are exact
Win/Draw/Loss (the tablebase stores no mate distances).
Set `BESTEMSHE_DATA_DIR` to point at the compressed layers (default `layers/compressed`).
## How the 10GB lookup stays OOM-safe
Each `.bin` stores a header `[u32 num_blocks][u32 offsets[]]` followed by
independently zstd-compressed 4MB blocks. `Oracle.h` mmaps the file (zero-copy,
pages faulted on demand), reads the offset table in place, and decompresses only
the one block containing the queried state's bit — peak RSS stays ~20MB
regardless of tablebase size, well inside the free HF Space's 16GB.
See [DEPLOY.md](DEPLOY.md) for pushing to GitHub (code-only) and the Hugging Face Space (with data).
|