n*n*n tic-tac-toe

I wanted the algorithm to be applicable not only for n < 6 boards, so it would be board size agnostic. This resulted in a less optimal algorithm but fairly applicable for a good amount of sizes. It's decently playable up to n = ~20. (Except because, for the time being, the first move it's double the amount of a normal move).

Since the number of permutations is: 3^(n^3), 3 states for each point in the space and 3 dimensions, respectably, and the search space for miniMax algorithm is: O ( (Branching Factor) ^ depth ): with Branching Factor being n^3 initially, and for each move that is played on the board it's reduced by 1.

So a miniMax solution is not ideal. I tried to make an evaluation function based on the same principle of "value of a point convergence" and then reduce the whole board into a value. With no much success.

As you can see from the following table it doesn't perform as good, since for solved n, p1 should always win. As of my knowledge n = 3 and n = 4 are solved. Ties are not possible as per Hales–Jewett theorem.. The following games results is playing against itself:

To given an idea of the algorithm strength, the following table represents its performance against a completely dumb AI, playing random moves on each turn. In this case data is shown as raw numbers since it is very close to a 100% win ratio for the non-dumb player:

As an anecdotical strength reference: I have played against it a few times and winning as P1 or P2 is quite easy on n=3 and n=4, I suppose is the same on higher n

- If a winning move exist, play it
- If opponent have a winning move next turn, block it
- Else
    - Get a random point which is available to be played in
    - Check for all other points in the 3D space and compare which has the greatest amount of confluence abroad all lines which has this player markers
    - Ignore all lines which cannot lead to scoring
    - Count each marker and sum up all lines to give that point a final value
    - If a point as greater convergence than the currently selected point make that the new point
    - Play the point with the greatest value

• Up to further investigation I have found the following weaknesses:
  • In the early game, both players (should) try to occupy points which increase their potential for creating threats, without actually executing those threats. page 98, chapter 4.
  • It does't prevent falling into a forcing losing sequences of moves
  • It's always trying to execute it's threats, and therefore failing to get strong influence across the board, minimizing it's remaining attacking sequences.

• add a check for: if tentative move leads into opponent having a winning move (a move that we must block), skip that tentative move. maybe allowable in certain depth? maybe scan for the sequence forcing moves if it leads to opponent winning?

• run git checkout cli-game
• modify the game rules in the cli file by uncommenting or modifying the Game arguments
• run npm run play

• uncomment the desired test's
• run npm run tests

• Urges a code refactor:
  • GUI split into single responsability objects
  • Make Game and Players objects independant of each other
• I want to eventually re-take this project back and implement a second more optimal algorithm.
• project on stand-by until further notice

• On top of the 2D stacked planes I want to render a Three.js Cube representation of the board, for it to be really a 3D game.
• make a log control to display only the X amount of moves per page, and and let you see the past state