Implementing incremental hashing of a data type

Learn
#1

I’m writing a chess engine in Haskell (not my greatest idea) and have implemented Zobrist hashing, which is a form of incremental hashing. Before implementing hashing, this was my Game type:

data Pieces = Pieces
    { _pawns   :: !Bitboard
    , _knights :: !Bitboard
    , _bishops :: !Bitboard
    , _rooks   :: !Bitboard
    , _queens  :: !Bitboard
    , _kings   :: !Bitboard
    } deriving (Eq, Show)
mkLenses ''Pieces

data Game = Game
    { _gamePlaying   :: Pieces
    , _gameWaiting   :: Pieces
    , _gameCastling  :: !Int
    , _gameEnPassant :: !(Maybe Int)
    , _gameTurn      :: !Color
    } deriving (Eq, Show)
makeLenses ''Game

For incremental hashing I came up with two approaches: adding the hash to the Game type

data Game = Game
    { _gamePlaying   :: Pieces
    , _gameWaiting   :: Pieces
    , _gameCastling  :: !Int
    , _gameEnPassant :: !(Maybe Int)
    , _gameTurn      :: !Color
    , _gameHash      :: !Int
    } deriving (Eq, Show)
makeLenses ''Game

and creating a separate type that wraps Game

data HGame = HGame
    { _hgGame :: {-# UNPACK #-} !Game
    , _hgHash :: !Int
    } deriving (Eq, Show)
makeLenses ''HGame

None of these approaches are really satisfactory to me. The first approach isn’t great because ideally I’d like the board specific information (info required to generate moves) to stay separate from auxiliary info like the hash. The second approach is unwieldy because most of the time the code is accessing hgGame, not hgHash, which leaves lots of game ^. hgGame . whatever in the code. It also causes some extra unboxing/reboxing to happen when the Game is passed to a function from within a HGame; I tried removing the UNPACK, performance got worse. I’ve also tried benchmarking both of these; performance is better during perft for the first approach, performance during searching is better for the second.

Is there any approach I’m overlooking? Can any of these be improved?

#2

Not necessarily! If you use makeClassy to make your lenses, then you can just do game ^. whatever even with the nested structure. I like microlens’s documentation here, but lens and optics both have this too.

2 Likes
#3

Is the hash a fact about a game, or a fact about a board state? Would it make sense to carry around a state parameter and transform it at each game step? Has a certain CPS feel to it, too.

#4

makeClassy looks like a pretty good fit for HGame, thanks!

#5

The hash is created from all the fields of Game, which is closer to a board state than a game because it doesn’t store things like time control or history. What do you mean by a state parameter?

#6

E.g., something State BitVector Game-ish, so that every step of the game you don’t have to tie together the hash and the board logic, at all. So each step of your game then looks like

  1. Update the Game
  2. modify (flip xor $ hashGame newGameState) (or something close)
  3. Then each game is just initialized with flip runState hashOfStartingPosition

I don’t know how you’re currently handling updating the hash between game steps, so this might not actually be helpful.

#7

I don’t think that would work unfortunately, currently the hash updating needs to be tied with the game state updating