Algorithm for a strategy game

Question

This is a question I have been toying with for a week or so, proposed by a colleague:

Imagine a game played on a 36x36 grid. The goal of the game is to create four corners of a square of any size (eg., 2x2, 3x3, 4x4, and so on). The first player places a game-piece anywhere except the center four grid spaces. After the first move, players can place their game-piece anywhere on the grid. Game-pieces cannot be moved after they are placed. And that's it; The game is simple and fun.

I have been trying to come up with an algorithm to win, or at least do well at this game. Any suggestions?

Answer 1

This is a game of perfect information where players take turns, like chess, so the same approach used in chess engines applies here. Use a minimax (with alpha-beta pruning probably) algorithm to search the tree of valid moves. You can use some evaluation function to guide your search, favoring positions that have the most almost-completed squares.

Answer 2

ok I'm reading junk into the game.. as its ambiguous.. I'm assuming that this game is similar to "dots and lines" where the move space is to connect 2 adjacent dots with a line. so the 2x2 grid would have 9 verticies, 4 1x1 win positions and 1 2x2 win position. With the game ending with a win for the person who completes a square, and a tie once both players have exhausted winable solutions.

since your working squares some of the logic is nice. you can calculate membership of any line to all possible boxes. so in the 2x2 example a radial would have membership in 2 1x1 boxes and a side would have a membership in one 1x1 and one 2x2. This membership becomes important.

at the begining of the game you generate all memberships for all line segments. make 2 copies.. (like playing battleship) the ENEMY COPY will be initilized to the number of turns he has left to finish every box.. so on the 36x36 there will be a 144 moves left to finish the large box 4 sets of 140moves to finish the 4 35x35 boxes

During his moves you decrement all of the affected boxes on the ENEMY COPY During your move any move you make invalidates ALL boxes containing your move. you set these to negative 1,, or infinite or 2 billion... just something to know that these squares are impossible.

You now create a ANTI-ENEMY COPY which is the reverse of the enemy copy.. this contains how many moves to complete a given square.

For a given move.. first check for a win situation. if you can move and win. (antienemy with a square at one) Then check if a block is needed. (enemy board with any square at one)

now add a minimax type function if your so inclined..

or use search to find the positions that destroy as many low finish squares as possible, or create a line that reduces multiple low squares on the anti-enemy board. This should work reasonably as it isnt trying to finish any specific square but a minimax where your both shooting for the low score is going to be a better scenario.

Answer 3

Like FogleBird wrote a Minimax Algorithm would work best. The problem is how to evaluate the score of the current board. The game is pretty complex there are over a thousand fields to begin with. In a small game like tic tac toe you can compute all possible moves till the end of the search tree in minimax then you give 1 point to the winning player and a -1 to the losing and backtrack the tree to find your best move. In this game you need some kind of heuristic to calculate a score for the board after descending the three 10 moves.

I don't have much information about the game so I can only guess good heuristics:

• Points because of completed squares (if you can get more then one square) this would be the easiest way because your heuristic is directly related to the game points
• minus points because of completed squares of your enemy
• number of possible squares
• number of owned fields at the sides of the board
• number of owned fields in small neighbourhoods

There are plenty of heuristics possible and most of the time you would need a mix of some of them.

Answer 4

Do you need to fill the square or just place it in corners?

For instance, is the following a win?

.......................
.X..X..................
.......................
.......................
.X..X..................
.......................

or the following?

.......................
.XXXX..................
.X..X..................
.X..X..................
.XXXX..................
.......................

or the following?

.......................
.XXXX..................
.XXXX..................
.XXXX..................
.XXXX..................
.......................