Discover a winning game with nothing or crosses

Question

I need to know the best way to find a winning move in a game with notes and crosses. The source code doesn't matter, I just need an example or something that I can start with.

The only thing I can think of is to use cycles and check each direction for each movement the player makes, for example, to search five times in a row. Is there a faster and more efficient way?

Answer 1

The real easy solution is to simply check from the last move made ... it is obvious that no previous move could win the game, or you would not be here ... so you just need to check if there are 5 (or as many ) in the row / column / diagonal around the moved object.

For example, if the panel looks like this, and X marks the most recent move:

............. ............. ............. ............. .....X....... ............. ............. ............. ............. ............. 

You do not need to check anything outside the "C" range:

 .C...C...C... ..C..C..C.... ...CCC.... ....CCC...... .CCCCXCCCC... ....CCC...... ...CCC.... ..C..C..C.... .C...C...C... ............. 

Does it help? (It looks like you could refer to this in your original question, but I was not sure.)

In addition, simple loops will become your best friend. You might be able to do some micro-optimization, but (depending on what your actual application is doing) this is probably not worth it.

One thing to keep in mind is that you cannot simply jump 5 in any direction from the very last move, looking for it a lot in a row, because this movement may be in the middle of the lane. So I would 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. 

Answer 2

Noughts and crosses is not an easy programming task, because you can use math tricks to simplify the problem.

Notes and crosses are usually a 3 by 3 grid. If you assign each position in your grid a number from one to nine (not digitally), you can arrange the numbers so that each horizontal, vertical and diagonal lines add up to 15

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

Why is this useful? If you can select any three squares belonging to either “O” or “X”, and these three squares add up to a total of 15, you know that the player won the game.

Answer 3

Consider a 3X3 board

Let X = 1. Let O = -1 and the space is represented by zero.

So, if the top line looks like this [X] [X] [X], the sum is 3, therefore, this is a win [O] [O] [O] the sum is -3, therefore, this is another win.

[X] [X] [] is 2, so if he is an X-turn, he can win by going to the space or O should be blocked.

[X] [O] [X] is 1, therefore there is no gain.

The 3x3 board has 8 positions for evaluation.

At NXN, the number is increasing, but the idea remains the same

if N = 8, and the sum of rows or columns is 7, then you know that there is a winning move for X in this row / column

This method worked for me in high school.

Best regards

Evil

Answer 4

I don’t know a better method and then cycle, but the board is so small that it is pretty trivial.

A small puedon 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] 

Answer 5

There are more efficient methods, but they are really important only when you expand this game for much larger board configurations. For example, if you saved noughts and crosses groups in directional objects (for example, save the diagonal configuration), you can sort them with winLength-1 length and only check the new move against these groups. You save several iterations, but you need to save a lot of additional information in memory.

Answer 6

This is a matter of submission. How do you keep the playing field? Now think outside the box; how else could you save it? You could, for example, represent a board, like a pair of raster images - one for crosses and one for crosses - then do a numerical comparison with a sample to detect victory conditions.