I need to know the best way to detect a winning move in a game of noughts and crosses. Source code doesn't matter, I just need a example or something I can start with.
The only thing I can come up with is to use loops and test every direction for every move a player makes, to search for e.g five in a row. Is there a faster and more efficient way?
I'm not aware of a better method then looping, but the board is so small, it's quite trivial.
A little Python psuedo code:
def get_winner(board):
if board[0][0] != EMPTY and board[0][0] == board[1][1] == board[2][2]:
return board[0][0]
if board[2][0] != EMPTY and board[2][0] == board[1][1] == board[0][2]:
return board[2][0]
for i in xrange(3):
if board[i][0] != EMPTY and board[i][0] == board[i][1] == board[i][2]:
return board[i][0]
if board[0][i] != EMPTY and board[0][i] == board[1][i] == board[2][i]:
return board[0][i]
There are more efficient ways, but they really only matter when you extend this game for much, much larger board configurations. For example, if you stored groupings of noughts and crosses in directional objects (store a diagonal configuration, for example), you could sort by those with length winLength-1, and only test the new move against these groupings. You save some iterations, but you have to maintain a lot of extra information in memory.
It's a question of representation. How do you store the game board? Now think outside the box; how else could you store it? You might for example represent the board as a pair of bitmaps - one for noughts and one for crosses - then do a numerical pattern match to detect winning conditions.
The real easy solution is to just check from the last move made...obviously, no prior move could have won the game, or you wouldn't be here...so you just need to check to see if there are 5 (or however many) in a row/column/diagonal around the move that was just placed.
For example, if the board looks like this, and X marks the most recent move:
.............
.............
.............
.............
.....X.......
.............
.............
.............
.............
.............
You don't need to check anything outside the range of "C":
.C...C...C...
..C..C..C....
...C.C.C.....
....CCC......
.CCCCXCCCC...
....CCC......
...C.C.C.....
..C..C..C....
.C...C...C...
.............
Does that help? (It looked like you might be alluding to this in your original question, but I wasn't sure.)
Beyond this, simple loops are going to be your best friend. You could probably do some micro-optimization, but (depending on what your actual application is doing) it's probably not worth it.
One thing to keep track of is that you can't just jump out 5 in any direction from the most recent move looking for that many in a row, because this move might be in the middle of a streak. So I'd do something like
From the new move
left = how many in a row we have to the left of the lastest move
right = how many in a row we have to the right of the latest move
if (left + right + 1 >= 5) then you have a winner
up = how many in a row we have above the latest move
down = how many in a row we have below the latest move
if (up + down + 1 >= 5) then you have a winner
// repeat for both diagonal directions.
Consider the 3X3 board
Let X = 1 Let O = -1 and a space is represented by a zero.
So if the top row looks like this [X][X][X] the sum is 3, hence it is a win [O][O][O] the sum is -3, hence it is the other win.
[X][X][ ] is 2, hence if it is X turn, he can win by moving to the blank, or O must block.
[X][O][X] is 1, hence no win.
In a 3x3 board there are 8 positions to evaluate.
In NXN the number gets larger but the idea remains the same
if N=8 and a row or column sums to 7, then you know there is a winning move for X on that row/column
That method worked for me in high school.
Best Wishes
Evil