Zero knowledge fog of war chess implemented using Aztec's zk circuit language Noir.
If you're after [THE RULES, CLICK HERE]
Major components are the JavaScript workspace for developer utilities and the test harness as well as the circuits themselves.
.
├── circuit/ # Noir FoW Chess implementation.
├── frontend/ # FoW Chess web frontend (TODO).
├── util/ # Dev utilities.
│ ├── bb_term/ # View bitboards in a terminal.
│ ├── bb_web/ # View bitboards in a web browser.
│ └── dev/ # JS workspace package for shared dependencies.
TODO: Circuit folder structure etc. Any simple sequence diagrams of how the main circuit logic is structured?
Noir is under active development if you want to build this project yourself please ensure you're using exactly the version numbers of Noir as specified in the relevant files otherwise your build may not work.
Currently (and as a goal) the entire project uses the same version of Noir for all circuits involved.
Noir 0.22.0 (0.22.0+420a5c74a14dcfeede04337a42282093a7b5e63e)
acvm-backend-barretenberg 0.15.1
Rather than keeping track of wanted tests within test files and having to open say 6 different files to check all have the same we can trust ourselves to keep this file up to date (famous last words) with the tests we want and whether or not we've implemented them. Ideally in the future this is automated.
Focus is piece move patterns, legal and illegal versions of those, and special game mechanics like en-passant capture.
| Knight | Bishop / Rook / Queen | King | Pawn | ||||||
|---|---|---|---|---|---|---|---|---|---|
| L | I | Legal | Illegal | L | I | L | I | ||
| General | Capture | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| Nothing move | -- | ✅ | -- | ✅ | -- | ✅ | -- | ✅ | |
| Pattern | Empty board | ✅ | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| Dense board | ✅ | ✅ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | |
| Blocked | Faux-empty board** | -- | ✅ | -- | ❌ | -- | ❌ | -- | ❌ |
| Dense board | -- | ✅ | -- | ❌ | -- | ❌ | -- | ❌ | |
| Special | King's side castle | -- | -- | -- | -- | ❌ | ❌ | -- | -- |
| Queen's side castle | -- | -- | -- | -- | ❌ | ❌ | -- | -- | |
| Promotion | -- | -- | -- | -- | -- | -- | ✅ | ✅ | |
| En-passant capture | -- | -- | -- | -- | -- | -- | ✅ | ✅ | |
| En-passant target | -- | -- | -- | -- | -- | -- | ✅ | -- | |
| Fog | Movement | ✅ | ✅ | ✅ | ✅ | -- | -- | -- | -- |
| Lights toggle | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ | |
- Faux-empty board
**isn't strictly empty, rather it contains the minimum required pieces for the test scenario. It is still named 'empty' in tests for easier running of tests by name-pattern. - Cells containing
--are not applicable.
Purely 'normal' piece captures.
| Pawn | Knight | Bishop | Rook | Queen | King | |
|---|---|---|---|---|---|---|
| Pawn | ✅ | ❌ | ❌ | ❌ | ✅ | ❌ |
| Knight | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| Bishop | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| Rook | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| Queen | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
| King | ❌ | ❌ | ❌ | ❌ | ❌ | ❌ |
- LS1B happy path.
- LS1B sad path.
- MS1B happy path.
- LS1B sad path.
Diag masking is the basis for all diag (diagonal and anti-diagonal) sliding piece movement (bishop, queen, king), so these masks must be correct without weird wrapping or edge-artifacting.
- Diagonal masks for every starting edge square.
- Anti-diagonal masks for every starting edge square.
Whether two given square indices are on the same diag forms the basis of computing the required diag mask.
- Same diagonal and NOT same anti-diagonal.
- Same anti-diagonal and NOT same diagonal.
Fog of War Chess has a standard definition but also numerous variations; Tikan is a variation.
In this version there is fog which is removed when pieces are nearby; or thought another way pieces have an illuminating area akin to a lighthouse and both players can only see in this illuminated area regardless of which player is illuminating it.
The presence of this fog means:
- You can see all illuminated squares (even those illuminated by your opponent).
- You can only see which piece your opponent has if your own piece illuminates the square their piece is on. (TODO: Diagram for this so it's clear for others).
- When moving a piece it must only move along illuminated squares, except for knights which can jump over the fog.
Penultimately there is also the ability for a player to toggle their pieces lighthouse:
- A piece with its lights off does not clear fog around it.
- A piece with its lights off is not revealed even if in the direct illumination of the opponent. (TODO: Diagram for this so it's clear for others).
- A piece with its lights off can still move subject to the normal rules.
- Toggling lights counts as a turn.
The rest of the game is like normal chess, except:
- There is no such thing as check or checkmate, the win condition is capturing the opponents king.
- [] Repo structure.
- [] test.sh script.
- [] Javascript test harness.
- [] Project structure (bitboards etc).
- [] bb_term project
- [] break_to_seed.ts
- [] gimme_that_enum.ts
- Bitboard state representation.
- [] (maybe) Recursive proof validation (persistence-layer agnostic).
- [] Svelte or SolidJS interface with circuit using
noir-js.
- [] For common dependencies like Typescript some kind of workspace management with Bun instead of manually keeping the various
package.jsons in-sync. - [] Where appropriate a workspace-based
tsconfig.jsonfor the various ones in sub-projects.
- [] For some reason Helix likes to make it REALLY hard to clean up whitespace in files and has likes to litter them maximally. Annoying stuff, the entire codebase could do with a good auto-formatting later on.
- [] Tidy up etymology.
- Basic build system for WASM frontend.
- Basics of Rust and Bevy.
- Compile current stuff and confirm it works via WASM in a browser.
- [] Create a Hello World WASM module and instantiate it alongside (1) showing multiple modules can be used.
- [] WASM backend instantiated with data passed in from frontend.
- [] Optimise WASM build for size.
- [] Profile game memory usage and Noir WASM backend usage (ceiling is 4GiB).
- [] WASM multithreading with SharedArrayBuffer? Rayon (a dependency of Bevy) can apparently do this already; alternative are WebWorkers which would require copying memory per call.
- [] Using (2) try and do this in a WebWorker so that the game and the second WASM module run on seperate threads (because...)
- [] Replace the Hello World WASM module with the Noir WASM backend. - Computing a proof will block so having another thread is key (hence 3).
- [] "Proper" build system for WASM (not just simple shell script currently).
짙다 = (adj.) thick, heavy, dense, deep, dark 안개 = (n.) fog or mist
짙은 안개 = dense fog
Romanised for intuitive spelling -> tikun ange Abbreviated -> TIKun ANge -> tikan
Checkmark and cross copy-pasta: ✅ ❌