zig-chess/docs/magic-bitboards-design.md

# Magic Bitboard Design Guide for a Zig Chess Engine

## Overview

This document describes the implementation strategy for sliding-piece move generation using Magic Bitboards in Zig.

The goal is:

- Extremely fast rook/bishop/queen move generation
- All move tables precomputed at startup or compile time
- Efficient runtime lookups using:
  - Bit masks
  - Bitwise operations
  - Multiplication by magic numbers
  - Table indexing

This document assumes:

- Board representation uses 64-bit bitboards (`u64`)
- One bitboard per piece type
- Separate white and black occupancy bitboards
- Additional metadata stored separately, such as castling and en passant

References for follow-up:

- Chess Programming Wiki, “Magic Bitboards”: https://www.chessprogramming.org/Magic_Bitboards
- Chess Programming Wiki, “Sliding Piece Attacks”: https://www.chessprogramming.org/Sliding_Piece_Attacks
- Chess Programming Wiki, “Bitboards”: https://www.chessprogramming.org/Bitboards

## 1. Board Representation

Use one `u64` per piece type.

Example:

```zig
const Board = struct {
    white_pawns:   u64,
    white_knights: u64,
    white_bishops: u64,
    white_rooks:   u64,
    white_queens:  u64,
    white_king:    u64,

    black_pawns:   u64,
    black_knights: u64,
    black_bishops: u64,
    black_rooks:   u64,
    black_queens:  u64,
    black_king:    u64,

    white_occ: u64,
    black_occ: u64,
    all_occ:   u64,
};
```

## 2. Square Numbering

Recommended:

```text
A1 = 0
B1 = 1
...
H1 = 7

A2 = 8
...
H8 = 63
```

This layout aligns naturally with white perspective, rank/file math, and bit shifting.

## 3. Sliding Piece Basics

Magic bitboards are only needed for:

- Rooks
- Bishops
- Queens

Knights, kings, and pawns can use precomputed attack masks or direct bit operations.

## 4. Relevant Occupancy Masks

Each rook/bishop square has a relevant occupancy mask.

This mask contains only squares that can block movement.

Board edges are excluded because edge blockers do not affect how far the slider can move; they create redundant occupancy states.

Example: rook on D4.

Relevant mask includes:

```text
D5 D6 D7
D3 D2
C4 B4
E4 F4 G4
```

Not included:

```text
D8
D1
A4
H4
```

## 5. Runtime Occupancy Extraction

At runtime:

```zig
const blockers = board.all_occ & rook_masks[square];
```

This isolates only blockers relevant to the rook.

## 6. Magic Bitboard Lookup Formula

Core formula:

```zig
index = (blockers * magic) >> shift;
```

Where:

- `blockers` = masked occupancy
- `magic` = precomputed magic number
- `shift` = reduces result to table index size

## 7. Why Multiplication Works

The multiplication mixes blocker bits into a pseudo-random pattern.

A good magic number guarantees that every possible blocker configuration maps to a usable table index. In practice, collisions are allowed only when the colliding occupancies produce the same attack bitboard.

## 8. Why Shifting Is Needed

Multiplication produces a 64-bit result. We only need enough bits to index the move table.

Example:

```text
4096 occupancy states -> need 12 bits
shift = 64 - 12
```

Formula:

```zig
index = (blockers *% magic) >> (64 - relevant_bits);
```

Use Zig wrapping multiplication (`*%`) for magic indexing.

## 9. Move Tables

Each square has attack entries:

```zig
rook_attacks[64][N]
bishop_attacks[64][N]
```

Where `N` depends on occupancy combinations.

Typical upper bounds:

- Rook: up to 4096 entries per square
- Bishop: up to 512 entries per square

Each entry stores a `u64` attack bitboard.

## 10. Runtime Move Generation

Rook:

```zig
const blockers = board.all_occ & rook_masks[square];
const index = (blockers *% rook_magics[square]) >> rook_shifts[square];
const moves = rook_attacks[square][index];
```

Bishop:

```zig
const blockers = board.all_occ & bishop_masks[square];
const index = (blockers *% bishop_magics[square]) >> bishop_shifts[square];
const moves = bishop_attacks[square][index];
```

Queen:

```zig
const queen_moves = rook_moves | bishop_moves;
```

Use OR (`|`), not AND (`&`).

## 11. Friendly Piece Removal

Sliding attacks include friendly occupied squares. Remove illegal destinations:

```zig
const legal_moves = attacks & ~friendly_occ;
```

## 12. Captures

Captures naturally remain in the move set because sliding stops on enemy blockers and includes the enemy blocker square.

To isolate captures:

```zig
const captures = legal_moves & enemy_occ;
```

## 13. Generating Relevant Occupancy Masks

Rook rays:

- North
- South
- East
- West

Bishop rays:

- North-east
- North-west
- South-east
- South-west

For magic relevant occupancy masks, exclude edge squares.

## 14. Generating All Occupancy Variations

If a mask has `n` relevant bits, then occupancy count is:

```text
2^n
```

Example:

```text
12 relevant bits -> 4096 occupancy states
```

Generate every occupancy subset.

## 15. Generating Attack Tables

For each occupancy subset:

1. Simulate sliding movement.
2. Stop when a blocker is encountered.
3. Include the blocker square.
4. Save resulting move bitboard.

## 16. Magic Number Generation

Magic generation is brute force.

Algorithm for a square:

1. Generate all occupancies.
2. Generate all attacks.
3. Pick random `u64` candidate magic.
4. Test `(blockers *% magic) >> shift`.
5. Ensure every occupancy maps without harmful collision.
6. If collision is harmful, reject magic and try another.

## 17. Zig-Specific Caveats

Use wrapping multiplication:

```zig
const index = (blockers *% magic) >> shift;
```

Normal multiplication may trap in safety-checked modes if overflow occurs.

## 18. Zig Integer Types

Use explicit types everywhere:

```zig
u64
u32
usize
```

Avoid implicit casts.

## 19. Compile-Time Generation

Zig can generate tables at compile time. Runtime generation is also useful while learning and debugging.

Potential workflow:

1. Runtime utility searches for magics and prints/generated tables.
2. Generated constants are reviewed.
3. Final engine uses embedded constants and precomputed attack tables.

## 20. Memory Usage

Approximate attack table RAM usage:

| Table | Size |
| --- | ---: |
| Rook attacks | ~800 KB |
| Bishop attacks | ~40 KB |
| Total | <1 MB |

## 21. Suggested Development Order

### Phase 1

Implement:

- square numbering
- bitboard helpers
- occupancy masks

### Phase 2

Implement:

- rook ray generation
- bishop ray generation

### Phase 3

Implement:

- occupancy subset generation
- attack generation

### Phase 4

Implement:

- brute-force magic finder

### Phase 5

Implement:

- runtime lookup system

### Phase 6

Validate against known positions/FENs.

## 22. Validation Tests

Verify:

- edge squares
- center squares
- empty board
- fully blocked board
- single blocker
- captures
- friendly blockers
- queen union correctness

## 23. Final Runtime Formula Summary

```zig
const blockers = board.all_occ & mask;
const index = (blockers *% magic) >> shift;
const attacks = attack_table[index];
const legal_moves = attacks & ~friendly_occ;
```

Queen:

```zig
const queen_moves = rook_moves | bishop_moves;
```