EXPTIME Hardness of an <i>n</i> by <i>n</i> Custodian Capture Game

Abstract

Custodian capture occurs when a player has placed two of his pieces on the opposite sides of an orthogonal line of the opponent’s men. Each piece moves like the rook in Chess. Different cultures played it from pre-modern times in two-player strategy board games, Ludus Latrunculorum (Kowalski’s reconstruction), Hasami shogi in Japan, Mak-yek in Thailand and Myanmar, Ming Mang in Tibet, and so on. We prove that a custodian capture game on n×n square board is EXPTIME hard if the first player to capture five or more men in total wins.

Keywords

• computational complexity
• custodial capture
• EXPTIME hard
• generalized game
• repetition