State Representation and Polyomino Placement for the Game Patchwork
  Modern board games are a rich source of entertainment for many people, but
also contain interesting and challenging structures for game playing research
and implementing game playing agents. This paper studies the game Patchwork, a
two player strategy game using polyomino tile drafting and placement. The core
polyomino placement mechanic is implemented in a constraint model using regular
constraints, extending and improving the model in (Lagerkvist, Pesant, 2008)
with: explicit rotation handling; optional placements; and new constraints for
resource usage. Crucial for implementing good game playing agents is to have
great heuristics for guiding the search when faced with large branching
factors. This paper divides placing tiles into two parts: a policy used for
placing parts and an evaluation used to select among different placements.
Policies are designed based on classical packing literature as well as common
standard constraint programming heuristics. For evaluation, global propagation
guided regret is introduced, choosing placements based on not ruling out later
placements. Extensive evaluations are performed, showing the importance of
using a good evaluation and that the proposed global propagation guided regret
is a very effective guide.
