Detect winning game in nought and crosses

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 somethi开发者_运维技巧ng 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?

---

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.

---

Noughts and crosses is a neat programming challenge, because there's alot of mathematical tricks you can use to simplify the problem.

Noughts and crosses is typically a 3-by-3 grid. If you assign each position in your grid a number from one to nine (not in numerical order) you can arrange the numbers so that every horizontal, vertical, and diagonal row adds up to 15

+----+----+----+
| 4  | 3  | 8  |
|    |    |    |
+----+----+----+
| 9  | 5  | 1  |
|    |    |    |
+----+----+----+
| 2  | 7  | 6  |
|    |    |    |
+----+----+----+ 

Why's that useful? If you can pick any three squares belonging to either 'O' or 'X', and those three squares add up to a total sum of 15, you know that player has won the game.

---

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

---

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.