Saturday, 14 April 2018

Simultaneous Strategy 1: Cosmic Blocks

In the chess-like game Cosmic Blocks, by Narcissa Wright, and available through the Discord server at https://discordapp.com/invite/szpznUj , players each start with a 1-square base on an 11-by-21 grid. That base spreads influence, represented by coloured shading of squares, to the 3-by-3 area surrounding the base. The goal is to spread this influence into the opposing base.




In each round of Cosmic Blocks each player selects a block from their stockpile and a space on the grid to place the block. Most of the blocks contain an arrow or multi directional indicator both of which signify that any influence that spreads to this space of the block also spreads in the direction indicated by the block, at a distance of either one or two spaces.

In a round each player has 30 seconds to select a block and a space to place it on and then both blocks are placed at the same time. This means that each player has to guess what block and space their opponent will select and so no player has perfect information and therefore Cosmic Blocks is not a determined game in which an unbeatable strategy exists for one player.

If two blocks are placed on the same space in the same round a collision happens and the result is a dead space which does not spread influence anywhere. A space can, however, be under both players influence at once, as shown by a square that is shaded with both players' colours. If the influence from both bases reaches each other on the same round, the game is a draw.

At the moment, no computer player exists for Cosmic Blocks. That's not surprising given the challenges in developing such a program.

First the solution space is extremely large, it is comparable in size to Go and is much larger than the pollution space in chess. To get a sense of this, in Queen's chess each player typically has 40 choices for any given move. A player in Cosmic blocks typically has about 200 spaces to place one of 16 block types, implying about 3200 choices for a given move, as well as 3200 choices for the opponent who is placing a block at the same time. Without pruning, there are 10^24 possibilities after only 3 rounds.



Second, there is a rock-paper-scissors aspect of simultaneous play. A computer player cannot simply employ the minimax principle and assume an opponent will choose the best response to a given move. This is because the opponent is not responding to the move, they are playing at exactly the same time.

Instead a computer player needs to estimate the probability that an opponent will choose a given space as well. Because an opponent may also be estimating these probabilities using heuristics, and playing accordingly can order strategy should be employed to avoid being second-guessed.

The paths of influence from one base to another can be simplified into three classes above the middle direct and below the middle. Guessing the path that an opponent will develop is one thing nature of that development which also needs to be inferred. This combination of poker-style hidden information and a large set of choices like Go offers the kind of strategical depth that provides great difficulty for a computer player, as well as some exciting opportunities.