# How SAN Kit represents the board

SAN Kit (Steven J. Edwards, 1993–1994) does not use a single, obvious
"chessboard" data structure. It uses one primary representation, one
shadow representation built specifically to make move generation
cheap, and one compact representation built specifically to make
storing many positions cheap. This note describes all three, and how
they relate to each other, based directly on the type definitions in
`sandef.h` and their use in `sanint.c`/`sangen.c`.

## The color-piece code: what one square holds

Every square's content is a single small integer, `cpT` (a plain
`int` typedef). There are sixteen possible values, only thirteen of
which mean something on a real board:

```c
#define cp_wp  0   /* white pawn */
#define cp_wn  1   /* white knight */
...
#define cp_bk 11   /* black king */
#define cp_v0 12   /* empty square */
#define cp_x0 13   /* off-board sentinel (see "The extended board") */
#define cp_x1 14   /* reserved */
#define cp_x2 15   /* reserved */
```

Two lookup tables split a `cpT` back into a color and a piece when
needed (`cv_c_cpv[cp]`, `cv_p_cpv[cp]`), rather than encoding color
and piece as separate bit-fields packed into the same integer. This
is a deliberate simplicity/speed trade-off typical of the period: a
whole `int` per square, and a table lookup instead of bit-masking,
in exchange for code that never has to think about encoding.

## The board itself: a union of two views over the same 64 squares

```c
typedef union bU
  {
    cpT bm[rankL][fileL];   /* 8x8, indexed [rank][file] */
    cpT bv[sqL];             /* 64 squares, indexed 0..63 */
  }
bT, *bptrT;

extern bT gb;                /* the one live board */
```

`bT` is a **union**, not a struct: `bm` and `bv` are two different
views of exactly the same 64 `cpT` values in memory. Code that
naturally thinks in ranks and files (`gb.bm[rank][file]`) and code
that just wants "the next square" in a flat scan (`gb.bv[sq]`, `sq`
from 0 to 63) both work directly against the same storage, with no
conversion step and no risk of the two getting out of sync — they
are not "kept in sync", they are the same bytes.

The single global `gb` (`sanvar.h`) is the position the rest of the
library reads and writes; `SANGetSq()`/`SANPutSq()` (`sanval.h`) are
the accessor functions built on top of it that the examples in this
project's `examples/` and `examples-pascal/` directories use rather
than touching `gb` directly (though `examples-pascal/custom_board.pas`
and its C counterpart, `custom_board.c`, do exactly that indirection
themselves, one call at a time, to draw the board in their own
style).

Square numbers are not arbitrary: `sq = (rank << 3) | file` (the
`map_sq_rank_file` macro), i.e. simply `rank * 8 + file`, so `sq_a1`
is 0 and `sq_h8` is 63 in one straight, gap-free numbering — no
padding, no offset, no invalid values in that range at all.

## The extended board: a padded shadow copy for move generation

Alongside `gb`, the library keeps a second, larger board purely to
make sliding-piece move generation cheap:

```c
#define xbdrL 4                          /* border width, each side */
typedef union xbU
  {
    cpT xbm[xrankL][xfileL];             /* 16x16 */
    cpT xbv[xsqL];
  }
xbT, *xbptrT;
```

The real 8x8 board sits in the middle of a 16x16 grid, surrounded by
a 4-square-wide border on every side. The border squares are filled
once, at start-up, with the sentinel value `cp_x0`:

```c
gxb.xbv[xsq] = cp_x0;
```

A rook, bishop, or queen can then be "walked" outward from its
square, one step at a time, in any of the eight directions, without
a single explicit boundary comparison anywhere in that loop: the
walk simply stops as soon as it reads `cp_x0` off a border square.
This is the classic *sentinel border* technique for move generation
(the same idea behind the well-known "0x88" board, just realized
here as a full explicit 256-square array rather than a single-bit
validity trick) — trading a larger, mostly-empty array for
completely branch-free-of-bounds-checks sliding move loops.

`map_xsq_sq`/`map_sq_xsq` (`sandef.h`) convert a square number
between the two coordinate systems; nothing about `gb` itself ever
needs to know the extended board exists.

## The piece lists: a reverse index, for the other direction

The board answers "what's on this square?" in O(1). The reverse
question — "where are this color's pieces?" — is answered by a
second, independent structure kept up to date alongside it:

```c
extern sqT plv[rcL][pmaxL];    /* plv[color][slot] = square, or none */
extern siT biv[sqL];           /* biv[square] = which slot, if any */
```

`plv[c_w]`/`plv[c_b]` are short, fixed-size lists of squares (slot 0,
`kingslot`, is always that color's king), and `biv` is the mapping
back the other way, from a square to its slot in the relevant color's
list, so a piece can be removed from or relocated within its list in
O(1) when it's captured or moved, without scanning the list to find
it first. Code that needs "every white piece" (evaluation, mate
scanning, `08_material_count.c`'s material sum, and others) walks
`plv[c_w]` directly instead of scanning all 64 squares of `gb` and
sorting the occupied ones from the empty ones every time.

## The compressed board: four bits per square, for history

Every move played is recorded on a history stack, and storing a full
copy of `gb` — 64 squares, 4 bytes each — in every history entry
would be needlessly wasteful, since a `cpT` value never exceeds 15
and so always fits in a nibble:

```c
#define zL (sqL / 2)     /* 32 */
typedef byteT zT[zL];    /* 32 bytes = 64 squares, 4 bits each */
```

`SANHistPush()` (`sanhst.c`) packs two squares into each byte of a
`zT` when saving a position to the stack:

```c
if ((sq % 2) == 0)
  hcurr->h_z[sq / 2] = gb.bv[sq];
else
  hcurr->h_z[sq / 2] |= (gb.bv[sq] << 4);
```

— an eightfold saving (32 bytes instead of 256) over storing `bT`
values directly, for a structure whose only job is to sit in memory,
unread, for as long as the move it belongs to might need to be
retracted.

## Summary

| Structure | Shape | Purpose |
|---|---|---|
| `bT gb` | union: `cpT[8][8]` / `cpT[64]` | the position itself |
| `xbT gxb` | union: `cpT[16][16]` / `cpT[256]` | branch-free sliding move generation |
| `plv[color][slot]` / `biv[sq]` | two small arrays | O(1) "which squares does this color occupy" |
| `zT` | `byte[32]` | a whole position, packed 4 bits/square, for the history stack |

One logical chessboard, four physical representations, each earning
its keep in a different part of the library — a small, concrete
illustration of a broader pattern in this 1994 codebase: favor a
second, purpose-built copy of the data over a single "clever enough
for everything" structure, whenever the access pattern actually
differs.
