6
$\begingroup$

So I made up this game, but I'm not able to find a good strategy to always win.

It's very similar to the original 3×3 Tic-Tac-Toe; but with changes.

So you draw a 5×5 board. Then each player takes turns putting a cross and circle. We then count the "scores".

This is a completed game that I drew. The scores are made by counting every 3-in-a-row strike. So for example in the top row, cross player gets 1 point.

You then do the counting horizontally, vertically, and both ways diagonally; for each row, column and diagonal.

For a 4-in-a-row, you get two points, as you can look at it as 2 different 3-in-a-rows. Similarly, a 5-in-a-row would get 3 points.

In the example game, cross wins as it get 9 whereas circle gets only 7.

I play this a lot; but it's always hard to tell where to put your next move. I've noticed that starting first gives you a significant advantage. To compensate for this, I lower the points of the player who started first by one.

This can obviously be extended to further dimensions, but I would like an answer only for a 5×5 grid.

So what's the optimal strategy?

Thanks in advance!

Side note: I'm learning programming ATM, so if someone knows what they're doing, can they also simulate this game in a program? I'd be really grateful if someone does.

$\endgroup$
1
  • 1
    $\begingroup$ There are less than $3^{25}\approx 2^{40}\approx 10^{12}$ positions, so someone could solve the game by brute force. (For example, Connect Four has more positions and was solved by brute force in 1995. - see wikipedia article.) $\endgroup$ – Vepir May 24 at 17:27
6
$\begingroup$

TLDR - Assuming the "one point less to X" rule, the game is a draw.

For example, if X starts in the center and both players play optimal moves, then the following unique position (up to symmetry) can always be forced by X:

enter image description here

were no matter what X plays on the next two moves, X will end up with one point more than O. (This is a draw if you lower X's points.)

After every move by X (while forcing this position), O has only one correct response!

That is, every move by O can be forced by X. (If O makes just a single mistake, X will have multiple ways to get an advantage of more than just one point.)


Solution

I have solved the game computationally.

If first player X has penalty to start with 1 point less (equivalently, if second player O has compensation to start with 1 point more), then the game is a draw under optimal play. Otherwise, first player wins by 1 point (or more points if second player doesn't play optimally).

I have used alpha-beta pruning with transposition tables for search and bitboards to encode positions. After putting together some quick c++ code, it took me less than one hour to solve the game. (I've shared my initial code on codereview and an updated version on repl.it.)

Below are example games using optimal strategy. (To punish non-optimal moves, you can run my code and explore the variations. Note that it can take multiple minutes if you evaluate a position with only a few pieces on the board.)


Terminology

Given a 5 by 5 grid, call a square "adjacent" if it can be reached by one vertical or horizontal step, unless specified otherwise.

Let "advantage" be the number of raw points player X has more than player O. Raw meaning that we are ignoring the penalty aka compensation. To account for the penalty aka compensation, simply subtract one from the advantage.


First move

The optimal first move for X is to start in the center. This is the only first move after which X can still force a nonnegative advantage even if they make a mistake (plays a random move) on their second move!

The second best first move for X is to play in one of four adjacent squares to the center. Even if O follows up by playing in the center, X can still force positive advantage in this scenario.

The worst first move for X is to play in a corner or in a square adjacent to a corner. Then, O can force negative advantage after playing in the center.

That is, under optimal play, X can secure an advantage of $1$ by starting in any of the five central squares. But, the center itself is the best first move as it forces O to play more precisely.

After X plays the first move in the center, the only good move for O is to then play in one of the four adjacent squares. Otherwise, X can force an advantage greater than $1$, which is either $2$ or $3$.

enter image description here


Optimal game

WLOG (due to symmetry), the optimal game starts as follows: (X takes center and one of the four adjacent squares not opposite the one that O took, while O takes any adjacent square and then one opposite to the one that X took.)

enter image description here

The advantage that is forced under optimal play is shown on the left image. That is, X can continue to play into any of the squares marked with the advantage of $1$. The right image shows the number of different optimal responses by O if X plays there. (Lower number in the right image means O needs to be more precise).

Therefore, one can argue that squares containing $1$ on both images are the best optimal moves. It turns out that if X picks one of these two squares, then O must play in the other of the two. That is, we get one of the following two positions depending on what X picks.

  1. X continues up-adjacent to center.

enter image description here

  1. X continues left-down-adjacent to center.

enter image description here

Where again, in both cases, X can play in any of the $1$'s in the left image, where again $1$'s in the right image are arguably the best as they force O to play an exact move.

In both cases, X has two best optimal moves. But, in the first case, both best optimal moves are equivalent due to symmetry. This leads to three possible optimal games.

  1. X plays in 2nd square on the main diagonal, in the previous first case.

enter image description here

  1. X makes 3-in-a-row on main antidiagonal, in previous second case.

enter image description here

  1. X threatens to make double 3-in-a-row, in previous second case.

enter image description here

Notice that in the new third case, X now has a forced move and needs to play precisely from now on to keep the advantage of $1$! So maybe, picking a move that gives O least many options is not always the best optimal move.

In the new first case, whatever optimal move X picks, O will still have multiple optimal choices. I won't go into detail into these games as it starts branching a lot.

Only in the new second case, X has moves that give no choice to O. Expanding on these two choices from X, we have the following two "best" optimal games.

  1. X connects 3-in-a-row vertically, in new second case.

enter image description here

  1. X connects 3-in-a-row horizontally, in new second case.

enter image description here

Continuing to expand this newer second case, we have:

  1. X chooses to make 3-in-a-row.

enter image description here

  1. X chooses to block 3-in-a-row threatened by O.

enter image description here

The first option is better than the second, so expanding on it:

  1. X threatens two 3-in-a-row's.

enter image description here

  1. X threatens one 3-in-a-row.

enter image description here

The first option is again clearly better, and now it is not hard to also see that the first $1$ is the better continuation for the first option. This leads to one "best" optimal game:

enter image description here

Now again, it is not hard to see that $1$ in the bottom left corner is the best optimal move, which leads to the following position.

enter image description here

Once again, the $1$ in the last row is the best optimal move, leading to:

enter image description here

And now finally, X can force the best optimal position:

enter image description here

Finally, whatever X plays on next two moves, the advantage of $1$ is kept.

Notice that every move by O was forced so far.

That is, this unique position (up to symmetry), can always be forced by X!


You can verify all this and also explore various branches, alternatives and responses yourself, using my code that I linked. Btw, to increase the speed of solving early positions, you may want to start saving important optimal moves and responses.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.