[coldcode]

Understanding the problem > any abstraction you pick without understanding the problem first. In this case chess was a terrible choice for an interview. In chess the biggest issue is tree size. If you don't start there then no abstraction will ever save you.

[ZirconiumX]

I'm going to disagree with you here. In chess the problem is not about reducing the tree size: you can get a "tree" by picking random moves. The problem is about reducing the tree size intelligently.

My chess program - Dorpsgek - has an 800 byte board structure (though I recently reduced that to about 400). It uses techniques that the computer chess community considered to be impractical. But still it works, and it works because the space that I use per board contains very useful information, such as attacks to a given square.

The advantage that bitboards give are not space by any meaningful quantity - for an alpha-beta search of depth d with a branching factor of b you will allocate at most d boards - or even 1 board - at any given node, not b^d boards. The advantages that bitboards give are speed and information density.

And to anybody who thinks that a bitboard approach is not sufficiently generic for different board sizes, wrap the bitboard using an arbitrary size bit set and the problem is essentially solved.