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 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?
Answer
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.