Game tree for tic tac toe

Question

Firstly, I am a beginner in java and I'm trying to simulate a TicTacToe game. I wanted to use a game tree to create a possible tree for all the states. Each node in the tree will represent the state and use this tree to decide the next move to make. I have planned to approach as follows,

1. interface class includes the information necessary to represent a single move.

2. abstract/interface class include methods to:

   a. return a new state object that represents what the state of the game would be after
   applying that move.

   b. id of the winner of this game if the current state represents a victory by one of the players.

   c. return the current player and the next player ids.

3. in a class include methods to,

   a. state of the game represented at this node in the Game Tree

   b. given a Move, add a child node to this node.

   c. given a Move, return the appropriate child node.

4. In another class include methods to,

   a. Construct a Tree with an initial state.

   b. Return the current state of the game

   c. Given a Move, update the tree so that the root of the tree holds the new state of the game.

   d. Generate the child nodes for this tree to a given depth.

I know the concepts of the tree (binary or avl or red black) but I'm kind of confused where to begin and how to proceed. Any suggestions on this context would be highly helpful.

Thanks

Sinx

Answer 1

Trees are overkill for a 3x3 grid, just use a 2D array of player ids to model the scene. To check for wins, loop over each cell in each line (three rows, three columns, and the two diagonals). If all of the cells in any of these lines all belong to the same player, then that player has won.

For simplicity, the lines could just be a list of lists of coordinates, ie

[[[0, 0], [0, 1], [0, 2]],
...
[[0, 0], [1, 1], [2, 2]],
...

FWTW, I am making a 3D tictactoe game in Javascript / ThreeJS for a school project, and this method is working fine on a 4x4x4 grid.