How can you most effectively find on the playing field the coordinates of all the cells, the filling of which will lead to winning?

Accordingly, the following options are possible: XXX_ , XX_X , X_XX , _XXX horizontally, similar vertically and along both diagonals. ( X is a busy cell, _ is empty)

At first, I looked for a simple pass through the entire array: I put X on an empty cell, then O, and every time I checked some checkWin (), is there a winner.

However, since the field is conditionally "unlimited", this option works too slowly, something more effective is needed.

How can I do that? Is the only option to fence a bunch of ifs and check each of the sixteen possible situations?

(Java language)

  • If they are faster than the cycle from 1 to 16 will not work ... And they will not save from the unlimited field - theoretically, if you put a cross / zero away from the main constructions, in the future the game can go far, and it will play its role. Those. The number of possible moves is not limited. If your question is how to quickly check whether a line of 4 crosses / zeros appeared after installing another one, check only the neighborhood of the changed cell, then it can really get clearer and faster than 4 similar cycles (the first is left-right, the second is - diagonally from the left from top to bottom, ...) - Mikhail M
  • In general, it seems, there is a fairly simple winning strategy for the first player, look for - Michael M
  • No, that is not the question. What is required is to find all the cells, the filling of which will lead to the victory of one of the players. (check them one step further, as it were). - fastZtx
  • Store the coordinates of the already filled cells in the list and check the neighborhood of each of these cells. - avp 2:51 pm
  • one
    @VladD, so here built 4 is already a win? Inattentively I read the question. We have always played 5-ku on a piece of paper from a notebook ... In my opinion, there is no obvious strategy for winning there. - avp

1 answer 1

I would not go from the whole sheet with the moves and through all possible combinations, but from the current moves.

  1. Put a cross.
  2. Check winnings in eight directions, i.e. whether he added winning combinations (on the next move).
  3. We memorize the list of cells, the move on which will be a dagger. Plus for each such cell, the coordinates of the winning combination itself (n cells).
  4. Put a zero.
  5. Pass through all winning moves with a cross, and cross out the blocked moves.

similarly for zeroes.

Thus, after each next move, we will have a list of cells for both players, having gone to which, they can win.