11 ms·

Understanding the problem > any abstraction you pick without understanding the problem first. In this case chess was a terrible choice for an interview. In ches

• ZirconiumX 9y ago
  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.