0
$\begingroup$

I'm creating a tic tac toe game, there will be two players: X and O. X will be a human, and O is an AI which will always choose the best move to play. My board is an 11x11 board and the winning condition is 5 in a row.

How do I know if a board is at end state (where one player has won)? For the 3x3 board, you can do it easily with just a few steps. But for the larger board (11x11) and the winning condition is smaller than the dimension, it's way more complex. The best solution I have found is to check for each n x n (n is the winning condition) square for a winner. But that seems slow.

So here is my question: if you know the last move of a player, can you use that position to check if that player wins without checking every n x n square in the board?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ An important improvement: You don't want to check moves in random order. You want to check the best moves first so the beta strategy can remove other moves quicker. So record the results after four moves for example, and try the ones first for five moves that look best after four moves. $\endgroup$
    – gnasher729
    Feb 20, 2017 at 14:58
  • 1
    $\begingroup$ Having only three outcomes (win, loss, draw) stops beta strategy from working well. Try giving 100 points to four in a row, 20 points to three in a row etc. $\endgroup$
    – gnasher729
    Feb 20, 2017 at 15:12
  • 1
    $\begingroup$ Your question doesn't seem to be about alpha-beta pruning. Including that information isn't relevant. I've deleted all that stuff about alpha-beta search and Moore neighborhood, as it seems to be just a distraction from what you are actually asking. If you have a question about alpha-beta search, I suggest asking that separately. $\endgroup$
    – D.W. ♦
    Feb 21, 2017 at 0:09
  • $\begingroup$ @gnasher729 I don't understand, how can we know if a move is the best move by record the results? I added more outcomes (4 in a row and 3 in a row) and the program runs a little bit faster, but still slow for some moves and still not very intelligent. For example when I have 4 in a row but two sides were blocked then it still returns 800 although I thought it should return 0. $\endgroup$
    – Huy Vo
    Feb 21, 2017 at 12:34
  • 1
    $\begingroup$ @HuyVo: Well, that means your evaluation function is daft. Four in a row, both ends open = win unless the opponent has a direct winning move. Four in a row, one end open = forced move by the opponent. Four in a row, no end open = no value at all. If you only value winning and losing, you don't value moves that build up rows and columns at all. $\endgroup$
    – gnasher729
    Feb 21, 2017 at 23:24

1 Answer 1

Reset to default
2
$\begingroup$

Yes, you can do this more efficiently. If you have a board position and the last move made to get to that position, you can check whether the board position is an end state using the following insight:

The previous board position wasn't an end state. Thus, if the board is an end state, that can only happen because there's a 5-in-a-row that includes the square where the last move occurred.

So, if the last move was in square $s$, check whether there's a 5-in-a-row that includes square $s$. There are only 4 directions to check (horizontal, vertical, and both diagonals), and you can check each direction efficiently.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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