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. On the other hand, the complex structures increase the implementation burden, with complex rules and intricate representations needed.

We study 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 Modeling Irregular Shape Placement Problems with Regular Constraints with: explicit rotation handling; optional placements; and new constraints for exact resource usage.

Crucial for implementing good game playing agents is to have great heuristics for guiding the search when faced with large branching factors. Placing tiles is done using a strategy. The strategy is divided 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 propapation 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 propapation guided regret is effective.

Kingdomino is introduced as an interesting game for studying game playing: the game is multiplayer (4 independent players per game); it has a limited game depth (13 moves per player); and it has limited but not insignificant interaction among players.

Several strategies based on locally greedy players, Monte Carlo Evaluation (MCE), and Monte Carlo Tree Search (MCTS) are presented with variants. We examine a variation of UCT called progressive win bias and a playout policy (Player-greedy) focused on selecting good moves for the player. A thorough evaluation is done showing how the strategies perform and how to choose parameters given specific time constraints. The evaluation shows that surprisingly MCE is stronger than MCTS for a game like Kingdomino.

All experiments use a cloud-native design, with a game server in a Docker container, and agents communicating using a REST-style JSON protocol. This enables a multi-language approach to separating the game state, the strategy implementations, and the coordination layer.