确定 Tic Tac Toe 游戏结束的算法
我用 Java 编写了一个 tic-tac-toe 游戏，我当前确定游戏结束的方法考虑了游戏结束的以下可能情况：
- 棋盘已满，尚未宣布获胜者: 比赛是平局。
- 克罗斯赢了。
- 圆赢了。
不幸的是，为此，它从表中读取一组预定义的场景。 考虑到棋盘上只有 9 个空格，因此桌子有点小，这不一定是坏事，但是是否有更好的算法方法来确定游戏是否结束？ 确定某人是否获胜是问题的核心，因为检查 9 个空格是否已满是微不足道的。
表方法可能是解决方案，但如果不是，那么什么是？ 另外，如果电路板的尺寸不是 n=9 怎么办？ 如果它是一个更大的棋盘，例如 n=16、n=25 等，导致获胜的连续放置项目数为 x=4、x=5 等？ 适用于所有 n = { 9, 16, 25, 36 ... } 的通用算法？
I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:
- The board is full, and no winner has yet been declared: Game is a draw.
- Cross has won.
- Circle has won.
Unfortunately, to do so, it reads through a predefined set of these scenarios from a table. This isn't necessarily bad considering that there are only 9 spaces on a board, and thus the table is somewhat small, but is there a better algorithmic way of determining if the game is over? The determination of whether someone has won or not is the meat of the problem, since checking if 9 spaces are full is trivial.
The table method might be the solution, but if not, what is? Also, what if the board were not size n=9? What if it were a much larger board, say n=16, n=25, and so on, causing the number of consecutively placed items to win to be x=4, x=5, etc? A general algorithm to use for all n = { 9, 16, 25, 36 ... }?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（26）
您知道获胜的举动只能在 X 或 O 做出最近的举动之后发生，因此您只能使用该举动中包含的可选诊断来搜索行/列，以在尝试确定获胜棋盘时限制您的搜索空间。 此外，由于平局井字棋游戏的步数是固定的，因此一旦完成最后一步，如果不是获胜步，则默认为平局游戏。
此代码适用于 n × n 棋盘，其中 n 连续才能获胜（3x3 棋盘需要连续 3 个棋盘，等等）
You know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.
This code is for an n by n board with n in a row to win (3x3 board requires 3 in a row, etc)
您可以使用幻方http://mathworld.wolfram.com/MagicSquare.html（如果有）行、列或对角线加起来为 15，则玩家获胜。
you can use a magic square http://mathworld.wolfram.com/MagicSquare.html if any row, column, or diag adds up to 15 then a player has won.
这个伪代码怎么样：
当玩家在位置 (x,y) 放下一个棋子后：
我将使用一个 char [n,n] 数组，其中 O,X 和空格为空。
How about this pseudocode:
After a player puts down a piece at position (x,y):
I'd use an array of char [n,n], with O,X and space for empty.
这类似于Osama ALASSIRY的答案，但它用恒定空间和线性时间来交换线性空间和恒定时间。 也就是说，初始化后没有循环。
为每行、每列和两条对角线（对角线和反对角线）初始化一对
(0,0)。 这些对表示相应行、列或对角线上棋子的累积(sum,sum)，其中当玩家放置棋子时，更新相应的行对、列对和对角线对（如果在对角线上）。 如果任何新更新的行、列或对角线对等于
(n,0)或(0,n)，则 A 或 B 分别获胜。渐近分析：
对于内存使用，您使用 4*(n+1) 整数。
练习：你能明白如何在每次移动的 O(1) 时间内测试平局吗？ 如果是这样，您可以以平局提前结束游戏。
This is similar to Osama ALASSIRY's answer, but it trades constant-space and linear-time for linear-space and constant-time. That is, there's no looping after initialization.
Initialize a pair
(0,0)for each row, each column, and the two diagonals (diagonal & anti-diagonal). These pairs represent the accumulated(sum,sum)of the pieces in the corresponding row, column, or diagonal, whereWhen a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either
(n,0)or(0,n)then either A or B won, respectively.Asymptotic analysis:
For the memory use, you use
4*(n+1)integers.Exercise: Can you see how to test for a draw in O(1) time per-move? If so, you can end the game early on a draw.
超高效位板
让我们将游戏存储在二进制整数中，并只需一步即可评估所有内容！
xxx xxx xxxooo ooo ooo因此，棋盘位置只需 18 位即可表示:
xoxoxo xoxoxo xoxoxo但是，虽然这看起来很有效，但它并不能帮助我们确定胜利。 我们需要一种更有用的位模式……它不仅可以对动作进行编码，还可以以合理的方式对行、列和对角线进行编码。
我会通过为每个棋盘位置使用一个巧妙的整数值来做到这一点。
选择更有用的表示
首先，我们需要一个董事会符号，以便我们可以讨论这个问题。 因此，与国际象棋类似，让我们用字母对行进行编号，用数字对列进行编号 - 这样我们就知道我们正在谈论哪个方格
让我们给每个值一个二进制值。
...其中，二进制值对位置出现的行、列和对角线进行编码。（稍后我们将了解其工作原理）
我们将使用这些值构建两个表示游戏，一个用于 X，一个用于 O
000 000 000 000 000 000 000 000000 000 000 000 000 000 000 000< /code>让我们跟随 X 的动作 （O 也是同样的原理）
这对 X 的棋盘值有什么影响：
a1 = 100 000 000 100 000 000 100 000... ORed与a2 = 010 000 000 000 100 000 000 000... 与a3 = 001 000 000 000 000 100 000 100进行或运算 ... 等于：XB =
111 000 000 100 100 100 100 100从左到右读取，我们看到 X
111（所有位置）(\o/ 获胜，耶！ )000（无位置）000（无位置） 第 3 行中的100（一个位置） 仅第一个第 1 列的位置100（一个位置） 仅第 1 列的第一个位置100（一个位置） 仅第 1 列的第一个位置100（一个位置）仅对角 1 的第一个位置100（一个位置）仅对角 2 的第一个位置你会注意到，每当 X（或 O）有获胜线时，也会有是他的棋盘值中的三个连续位。 准确地说，这三个位的位置决定了他在哪一行/哪一列/哪一条对角线上获胜。
因此，现在的技巧是找到一种方法来在单个操作中检查此（三个连续位设置）条件。
修改值以使检测更容易
为了帮助实现这一点，让我们更改位表示形式，以便三组之间始终存在零（因为
001 110也是三个连续的位 - 但它们不是有效的胜利...因此，固定的零间隔符会打破这些：0 001 0 110）因此，在添加一些间隔零之后，我们可以确信任何三个X 或 O 棋盘值中的连续设置位表示获胜！
因此，我们的新二进制值（带零填充）如下所示：
a1 = 100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0； 0x80080080（十六进制）a2 = 010 0 000 0 000 0 000 0 100 0 000 0 000 0 000 0; 0x40008000您会注意到主板的每个“winline”现在需要 4 位。
8 个 winlines x 每条 4 位 = 32 位！ 这不是很方便吗 : )))))
解析
我们可以遍历所有位来查找三个连续的位，但这将需要 32 次移位 x 2 个玩家...以及一个计数器来跟踪。 很慢！
我们可以与 0xF 进行 AND 运算，查找值 8+4+2=14。 这将允许我们一次检查 4 位。 将轮班数量减少四分之一。 但同样，这很慢！
因此，让我们立即检查所有可能性...
超高效获胜检测
假设我们想要评估 A3+A1+B2+C3 情况（对角线上的胜利）
现在，让我们通过有效地将三位合并为一位来检查是否获胜...
只需使用：
XB AND (XB << 1) AND (XB >> 1)换句话说： XB 与（XB 向左移动）AND（XB 向右移动）进行 AND
运算让我们尝试一个示例...
看到了吗？ 任何非零结果都意味着胜利！
但是，他们赢在哪里
想知道他们赢在哪里吗？ 好吧，您可以只使用第二个表：
但是，我们可以比这更聪明，因为模式非常规则！
例如，在汇编中，您可以使用BSF（向前位扫描）来查找前导零的数量。 然后减去 2，然后减去 /4（右移 2） - 得到 0 到 8 之间的数字...您可以将其用作索引来查找 win 字符串数组：
{"wins the top row ”，“占据中间行！”，...“抢对角线！” 这使得整个游戏逻辑......从移动检查到棋盘更新，一直到赢/输检测和适当的成功消息，都适合少数 ASM 指令。
...它小巧、高效且超快！
检查某步棋是否可玩
显然，将“X 棋盘”与“O 棋盘”进行 OR 运算 = 所有位置
因此，您可以轻松检查棋步是否有效。 如果用户选择UpperLeft，则该位置具有整数值。 只需用 (XB OR OB) 检查该值的“AND”...
...如果结果非零，则该位置已被使用。
结论
如果您正在寻找处理板的有效方法，请不要从板对象开始。 尝试发现一些有用的抽象。
查看状态是否适合整数，并考虑要处理的“简单”位掩码是什么样的。 通过巧妙地选择整数来表示动作、位置或棋盘……您可能会发现整个游戏可以非常有效地进行、评估和评分 - 使用简单的按位逻辑。
最后致歉
顺便说一句，我不是 StackOverflow 的常客，所以我希望这篇文章不会太混乱而难以理解。 另外，请友善...“人类”是我的第二语言，我还不太流利；）
无论如何，我希望这对某人有帮助。
Ultra-efficient Bit-boarding
Let's store the game in a binary integer, and evaluate everything using just one step!
xxx xxx xxxooo ooo oooSo, a board position could be represented in just 18 bits:
xoxoxo xoxoxo xoxoxoBut, whilst this might look efficient, it doesn't help us with determining a win. We need a more useful bit pattern... one that not only encodes the moves, but also encodes the rows, columns and diagonals in a reasonable way.
I would do this by using a clever integer value for each board position.
Choosing a more useful representation
First, we need a board notation, just so that we can discuss this. So, similar to Chess, lets number the rows with letters and the columns with numbers - so we know which square we're talking about
And let's give each a binary value.
... where, the binary values encode which rows, columns and diagonals the position appears in. (we'll look at how this works this later)
We will use these values to build two representations of the game, one for X and one for O
000 000 000 000 000 000 000 000000 000 000 000 000 000 000 000Let's follow X's moves (O would be the same principle)
What does that do to X's board value :
a1 = 100 000 000 100 000 000 100 000... ORed witha2 = 010 000 000 000 100 000 000 000... ORed witha3 = 001 000 000 000 000 100 000 100... equals :XB =
111 000 000 100 100 100 100 100Reading from left to right we see that X has :
111(All positions) in Row 1 (\o/ A win, Yay!)000(No positions) in Row 2000(No positions) in Row 3100(One position) Only the first position of Column 1100(One position) Only the first position of Column 1100(One position) Only the first position of Column 1100(One position) Only the first position of Diagonal 1100(One position) Only the first position of Diagonal 2You'll notice that whenever X (or O) has a winning line, then there will also be three consecutive bits in his board value. Precisely Where those three bits are, dictates which row/column/diagonal he won on.
So, the trick now is to find a way to check for this (three consecutive bits set) condition in a single operation.
Modifying the values to make detection easier
To assist with this, let's change our bit representation so that there are always ZEROs between the groups of three (Because
001 110is also three consecutive bits - but they are NOT a valid win ... so, a fixed zero spacer would break these up:0 001 0 110)So, after adding some spacing ZEROes, we can be confident that ANY three consecutive set bits in X's or O's board value indicates a win!
So, our new binary values (with zero-padding) look like this :
a1 = 100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0; 0x80080080 (hex)a2 = 010 0 000 0 000 0 000 0 100 0 000 0 000 0 000 0; 0x40008000a3 = 001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0; 0x20000808b1 = 000 0 100 0 000 0 010 0 000 0 000 0 000 0 000 0; 0x08040000b2 = 000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0; 0x04004044b3 = 000 0 001 0 000 0 000 0 000 0 010 0 000 0 000 0; 0x02000400c1 = 000 0 000 0 100 0 001 0 000 0 000 0 000 0 001 0; 0x00820002c2 = 000 0 000 0 010 0 000 0 001 0 000 0 000 0 000 0; 0x00402000c3 = 000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0; 0x00200220You'll notice that each "winline" of the board now requires 4 bits.
8 winlines x 4 bits each = 32 bits! Isn't that convenient : )))))
Parsing
We could shift through all the bits looking for three consecutive bits, but that will take 32 shifts x 2 players... and a counter to keep track. It's slow!
We could AND with 0xF, looking for the value 8+4+2=14. And this would allow us to check 4 bits at a time. Cutting the number of shifts by a quarter. But again, this is slow!
So, instead, let's check ALL of the possibilities at once...
Ultra-efficient win detection
Imagine we wanted to evaluate the A3+A1+B2+C3 case (a win on the diagonal)
Now, let's check it for a win, by efficiently merging three bits into one...
Simply use :
XB AND (XB << 1) AND (XB >> 1)in other words: XB ANDed with (XB shifted left) AND (XB shiftted right)
Let's try an example...
See that? Any non-zero result means a win!
But, where did they win
Want to know where they won? Well, you could just use a second table :
However, we can be smarter than that, as the pattern is VERY regular!
For example, in assembly you can use
BSF (Bit Scan Forward)to find the number of leading zeros. Then subtract 2 and then /4 (Shift Right 2) - to get a number between 0 and 8... which you can use as an index to look up into an array of win strings :{"wins the top row", "takes the middle row!", ... "steals the diagonal!" }This makes the whole game logic... from move checking, to board updating and right through to win/loss detection and an appropriate success message, all fit in a handful of ASM instructions.
... it's tiny, efficient and ultrafast!
Checking whether a move is playable
Obviously, ORing "X's board" with "O's board" = ALL POSITIONS
So, you can check if a move is valid quite easily. If user chooses UpperLeft, this position has an integer value. Just check the 'AND' of this Value with (XB OR OB)...
... if the result is nonzero, then the position is already in use.
Conclusion
If you're looking for efficient ways to process a board, don't start with a board object. Try to discover some useful abstraction.
See if the states fit within an integer, and think about what an 'easy' bitmask to process would look like. With some clever choice of integers to represent moves, positions or boards... you might find that the entire game can be played, evaluated and scored VERY efficiently - using simply bitwise logic.
Closing apologies
BTW I'm not a regular here on StackOverflow, so I hope this post wasn't too chaotic to follow. Also, please be kind... "Human" is my second language and I'm not quite fluent yet ;)
Anyway, I hope this helps someone.
这是我为我正在使用 javascript 开发的项目编写的解决方案。 如果您不介意几个数组的内存成本，那么它可能是您能找到的最快、最简单的解决方案。 它假设您知道最后一步的位置。
Heres my solution that I wrote for a project I'm working on in javascript. If you don't mind the memory cost of a few arrays it's probably the fastest and simplest solution you'll find. It assumes you know the position of the last move.
恒定时间解决方案，运行时间为 O(8)。
将板的状态存储为二进制数。 最小的位 (2^0) 是棋盘的左上行。 然后它向右移动，然后向下移动。
IE
每个玩家都有自己的二进制数来表示状态（因为井字游戏）有 3 个状态（X、O 和空白），因此单个二进制数无法代表多个玩家的棋盘状态。
例如，如下棋盘：
请注意，玩家 X 的位与玩家 O 的位不相交，这是显而易见的，因为 X 不能将棋子放在 O 有棋子的地方，反之亦然。
为了检查玩家是否获胜，我们需要将该玩家覆盖的所有位置与我们知道的获胜位置进行比较。 在这种情况下，最简单的方法是对玩家位置和获胜位置进行“与”门控，然后查看两者是否相等。
例如。
注意：
X & W = W，所以X处于获胜状态。这是一个恒定时间解决方案，它仅取决于获胜位置的数量，因为应用与门是恒定时间操作并且获胜位置的数量是有限的。
它还简化了枚举所有有效板状态的任务，它们只是由 9 位表示的所有数字。 但是当然你需要一个额外的条件来保证一个数字是有效的棋盘状态（例如，
0b111111111是一个有效的9位数字，但它不是一个有效的棋盘状态，因为X刚刚采取了所有回合）。可能的获胜位置的数量可以即时生成，但无论如何它们都在这里。
要枚举所有板位置，您可以运行以下循环。 尽管我将把确定一个数字是否是有效的棋盘状态留给其他人。
注意：(2**9 - 1) = (2**8) + (2**7) + (2**6) + ... (2**1) + (2**0)
Constant time solution, runs in O(8).
Store the state of the board as a binary number. The smallest bit (2^0) is the top left row of the board. Then it goes rightwards, then downwards.
I.E.
Each player has their own binary number to represent the state (because tic-tac-toe) has 3 states (X, O & blank) so a single binary number won't work to represent the state of the board for multiple players.
For example, a board like:
Notice that the bits for player X are disjoint from the bits for player O, this is obvious because X can't put a piece where O has a piece and vice versa.
To check whether a player has won, we need to compare all the positions covered by that player to a position we know is a win-position. In this case, the easiest way to do that would be by AND-gating the player-position and the win-position and seeing if the two are equal.
eg.
Note:
X & W = W, so X is in a win state.This is a constant time solution, it depends only on the number of win-positions, because applying AND-gate is a constant time operation and the number of win-positions is finite.
It also simplifies the task of enumerating all valid board states, their just all the numbers representable by 9 bits. But of course you need an extra condition to guarantee a number is a valid board state (eg.
0b111111111is a valid 9-bit number, but it isn't a valid board state because X has just taken all the turns).The number of possible win positions can be generated on the fly, but here they are anyways.
To enumerate all board positions, you can run the following loop. Although I'll leave determining whether a number is a valid board state upto someone else.
NOTE: (2**9 - 1) = (2**8) + (2**7) + (2**6) + ... (2**1) + (2**0)
我刚刚为我的 C 编程课写了这个。
我发布它是因为这里的其他示例都不适用于任何大小的矩形网格，以及任何数量的N连续标记来获胜。
您将在
checkWinner()函数中找到我的算法。 它不使用幻数或任何奇特的东西来检查获胜者，它只使用四个 for 循环 - 代码注释得很好，所以我想我会让它自己说话。I just wrote this for my C programming class.
I am posting it because none of the other examples here will work with any size rectangular grid, and any number N-in-a-row consecutive marks to win.
You'll find my algorithm, such as it is, in the
checkWinner()function. It doesn't use magic numbers or anything fancy to check for a winner, it simply uses four for loops - The code is well commented so I'll let it speak for itself I guess.如果棋盘为 n × n，则有 n 行、n 列和 2 条对角线。 检查每个选项的全 X 或全 O，找出获胜者。
如果只需要x x x x x x n个连续方格获胜，那么情况就有点复杂了。 最明显的解决方案是检查每个 x × x 方格是否获胜。 下面是一些代码来演示这一点。
（我实际上并没有测试这个*咳嗽*，但它确实在第一次尝试时编译了，耶我！）
If the board is n × n then there are n rows, n columns, and 2 diagonals. Check each of those for all-X's or all-O's to find a winner.
If it only takes x < n consecutive squares to win, then it's a little more complicated. The most obvious solution is to check each x × x square for a winner. Here's some code that demonstrates that.
(I didn't actually test this *cough*, but it did compile on the first try, yay me!)
我不太了解Java，但我了解C，所以我尝试了adk 的魔方思想（以及Hardwareguy 的搜索限制）。
它编译和测试得很好。
% gcc -o tic-tac-toe tic-tac-toe.c % ./tic-tac-toe | | ---+---+--- | | ---+---+--- | | Enter moves as " " (no quotes, zero indexed) X's move: 1 2 | | ---+---+--- | | X ---+---+--- | | O's move: 1 2 illegal move (already taken), try again O's move: 3 3 illegal move (off the board), try again O's move: 2 2 | | ---+---+--- | | X ---+---+--- | | O X's move: 1 0 | | ---+---+--- X | | X ---+---+--- | | O O's move: 1 1 | | ---+---+--- X | O | X ---+---+--- | | O X's move: 0 0 X | | ---+---+--- X | O | X ---+---+--- | | O O's move: 2 0 X | | ---+---+--- X | O | X ---+---+--- O | | O X's move: 2 1 X | | ---+---+--- X | O | X ---+---+--- O | X | O O's move: 0 2 X | | O ---+---+--- X | O | X ---+---+--- O | X | O tic-tac-toe! O wins! % ./tic-tac-toe | | ---+---+--- | | ---+---+--- | | Enter moves as " " (no quotes, zero indexed) X's move: 0 0 X | | ---+---+--- | | ---+---+--- | | O's move: 0 1 X | O | ---+---+--- | | ---+---+--- | | X's move: 0 2 X | O | X ---+---+--- | | ---+---+--- | | O's move: 1 0 X | O | X ---+---+--- O | | ---+---+--- | | X's move: 1 1 X | O | X ---+---+--- O | X | ---+---+--- | | O's move: 2 0 X | O | X ---+---+--- O | X | ---+---+--- O | | X's move: 2 1 X | O | X ---+---+--- O | X | ---+---+--- O | X | O's move: 2 2 X | O | X ---+---+--- O | X | ---+---+--- O | X | O X's move: 1 2 X | O | X ---+---+--- O | X | X ---+---+--- O | X | O stalemate... nobody wins :( %很有趣，谢谢！
实际上，想一想，你不需要幻方，只需要每行/列/对角线的计数。 这比将幻方推广为
n×n矩阵要容易一些，因为您只需要计数到n即可。I don't know Java that well, but I do know C, so I tried adk's magic square idea (along with Hardwareguy's search restriction).
It compiles and tests well.
% gcc -o tic-tac-toe tic-tac-toe.c % ./tic-tac-toe | | ---+---+--- | | ---+---+--- | | Enter moves as " " (no quotes, zero indexed) X's move: 1 2 | | ---+---+--- | | X ---+---+--- | | O's move: 1 2 illegal move (already taken), try again O's move: 3 3 illegal move (off the board), try again O's move: 2 2 | | ---+---+--- | | X ---+---+--- | | O X's move: 1 0 | | ---+---+--- X | | X ---+---+--- | | O O's move: 1 1 | | ---+---+--- X | O | X ---+---+--- | | O X's move: 0 0 X | | ---+---+--- X | O | X ---+---+--- | | O O's move: 2 0 X | | ---+---+--- X | O | X ---+---+--- O | | O X's move: 2 1 X | | ---+---+--- X | O | X ---+---+--- O | X | O O's move: 0 2 X | | O ---+---+--- X | O | X ---+---+--- O | X | O tic-tac-toe! O wins! % ./tic-tac-toe | | ---+---+--- | | ---+---+--- | | Enter moves as " " (no quotes, zero indexed) X's move: 0 0 X | | ---+---+--- | | ---+---+--- | | O's move: 0 1 X | O | ---+---+--- | | ---+---+--- | | X's move: 0 2 X | O | X ---+---+--- | | ---+---+--- | | O's move: 1 0 X | O | X ---+---+--- O | | ---+---+--- | | X's move: 1 1 X | O | X ---+---+--- O | X | ---+---+--- | | O's move: 2 0 X | O | X ---+---+--- O | X | ---+---+--- O | | X's move: 2 1 X | O | X ---+---+--- O | X | ---+---+--- O | X | O's move: 2 2 X | O | X ---+---+--- O | X | ---+---+--- O | X | O X's move: 1 2 X | O | X ---+---+--- O | X | X ---+---+--- O | X | O stalemate... nobody wins :( %That was fun, thanks!
Actually, thinking about it, you don't need a magic square, just a count for each row/column/diagonal. This is a little easier than generalizing a magic square to
n×nmatrices, since you just need to count ton.在一次采访中我也被问到了同样的问题。
我的想法：
用 0 初始化矩阵。
保留3个数组
1）sum_row（大小n）
2）sum_column（大小n）
3) 对角线（大小 2）
每移动一次 (X)，框值就减 1；每移动一次 (0)，框值就增加 1。
在任何时候，如果当前移动中修改的行/列/对角线的总和为 -3 或 +3，则意味着有人赢得了游戏。
对于平局，我们可以使用上述方法来保留 moveCount 变量。
你认为我错过了什么吗？
编辑：同样可用于 nxn 矩阵。 总和应为偶数 +3 或 -3。
I was asked the same question in one of my interviews.
My thoughts:
Initialize the matrix with 0.
Keep 3 arrays
1)sum_row (size n)
2) sum_column (size n)
3) diagonal (size 2)
For each move by (X) decrement the box value by 1 and for each move by (0) increment it by 1.
At any point if the row/column/diagonal which has been modified in current move has sum either -3 or +3 means somebody has won the game.
For a draw we can use above approach to keep the moveCount variable.
Do you think I am missing something ?
Edit: Same can be used for nxn matrix. Sum should be even +3 or -3.
我喜欢这个算法，因为它使用 1x9 与 3x3 的棋盘表示。
I like this algorithm as it uses a 1x9 vs 3x3 representation of the board.
确定该点是否位于反诊断上的非循环方法：
a non-loop way to determine if the point was on the anti diag:
我迟到了，但我想指出我发现使用魔方，即它可以用来获取导致下一回合输赢的方格的参考，而不仅仅是用来计算游戏何时结束。
以这个幻方为例：
首先，设置一个
scores数组，每次移动时该数组都会递增。 有关详细信息，请参阅此答案。 现在，如果我们在 [0,0] 和 [0,1] 处连续两次非法玩 X 两次，那么scores数组将如下所示：并且棋盘将如下所示：
然后，我们所拥有的一切为了获得获胜/阻止哪个方格的参考，要做的事情是：
实际上，实现需要一些额外的技巧，例如处理编号键（在 JavaScript 中），但我发现它非常简单并且喜欢娱乐数学。
I am late the party, but I wanted to point out one benefit that I found to using a magic square, namely that it can be used to get a reference to the square that would cause the win or loss on the next turn, rather than just being used to calculate when a game is over.
Take this magic square:
First, set up an
scoresarray that is incremented every time a move is made. See this answer for details. Now if we illegally play X twice in a row at [0,0] and [0,1], then thescoresarray looks like this:And the board looks like this:
Then, all we have to do in order to get a reference to which square to win/block on is:
In reality, the implementation requires a few additional tricks, like handling numbered keys (in JavaScript), but I found it pretty straightforward and enjoyed the recreational math.
以下是 React 中的示例实现：CodeSandbox 演示。
该算法非常简单：
为“O”输入分配
0，为“X”输入分配1。 检查函数的结果可以是0、1或2（绘制）。这是实现：
然后剩下的就是拥有一个在每个用户输入时触发的函数：
现在就完成了！
GitHub 存储库链接：https://github.com/mkotsollaris/tic-井字形
Here's an example implementation in React: CodeSandbox Demo.
The algorithm is quite straightforward:
Assigning
0for an "O" input and1for an "X" input. The result of the check functions can be either0, or1, or2(draw).Here's the implementation:
Then all is left, is to have a function that will trigger on every single user input:
And there you have it!
GitHub repo link: https://github.com/mkotsollaris/tic-tac-toe
我在行、列、对角线检查中做了一些优化。 主要是在第一个嵌套循环中决定我们是否需要检查特定的列或对角线。 因此，我们避免检查列或对角线，从而节省时间。 当电路板尺寸较大且大量单元未填充时，这会产生很大影响。
这是它的 java 代码。
I made some optimization in the row, col, diagonal checks. Its mainly decided in the first nested loop if we need to check a particular column or diagonal. So, we avoid checking of columns or diagonals saving time. This makes big impact when the board size is more and a significant number of the cells are not filled.
Here is the java code for that.
这是一个非常简单的检查方法。
}
This is a really simple way to check.
}
另一种选择：使用代码生成表。 直到对称为止，获胜的方式只有三种：边排、中排、对角线。 采取这三个并以各种可能的方式旋转它们：
这些对称性可以在您的游戏代码中有更多用途：如果您到达一个已经看到旋转版本的棋盘，您可以只采用缓存的值或缓存的最佳值从那个移动（并将其取消旋转）。 这通常比评估游戏子树要快得多。
（左右翻转也可以以同样的方式提供帮助；这里不需要它，因为获胜图案的旋转集是镜像对称的。）
Another option: generate your table with code. Up to symmetry, there are only three ways to win: edge row, middle row, or diagonal. Take those three and spin them around every way possible:
These symmetries can have more uses in your game-playing code: if you get to a board you've already seen a rotated version of, you can just take the cached value or cached best move from that one (and unrotate it back). This is usually much faster than evaluating the game subtree.
(Flipping left and right can help the same way; it wasn't needed here because the set of rotations of the winning patterns is mirror-symmetric.)
这是我想出的一个解决方案，它将符号存储为字符，并使用字符的 int 值来确定 X 或 O 是否获胜（查看裁判的代码）
另外，这里是我的单元测试，以验证它是否确实有效 完整
的解决方案： https://github.com/nashjain/tictactoe/tree/master/java
Here is a solution I came up with, this stores the symbols as chars and uses the char's int value to figure out if X or O has won (look at the Referee's code)
Also here are my unit tests to validate it actually works
Full solution: https://github.com/nashjain/tictactoe/tree/master/java
对于 9 个插槽，采用以下方法怎么样？ 为 3x3 矩阵 (a1,a2...a9) 声明 9 个整数变量，其中 a1,a2,a3 表示第 1 行，a1,a4,a7 将形成第 1 列（您明白了）。 使用“1”表示玩家 1，使用“2”表示玩家 2。
有 8 种可能的获胜组合：
Win-1：a1+a2+a3（答案可能是 3 或 6，具体取决于哪位玩家获胜）
赢2：a4+a5+a6
Win-3：a7+a8+a9
Win-4：a1+a4+a7
....
Win-7：a1+a5+a9
Win-8：a3+a5+a7
现在我们知道，如果玩家 1 穿过 a1，那么我们需要重新评估 3 个变量的总和：Win-1、Win-4 和 Win-7。 无论哪个“赢-？” 变量达到 3 或 6 最先获胜。 如果 Win-1 变量首先达到 6，则 Player-2 获胜。
我确实知道这个解决方案不容易扩展。
How about a following approach for 9 slots? Declare 9 integer variables for a 3x3 matrix (a1,a2....a9) where a1,a2,a3 represent row-1 and a1,a4,a7 would form column-1 (you get the idea). Use '1' to indicate Player-1 and '2' to indicate Player-2.
There are 8 possible win combinations:
Win-1: a1+a2+a3 (answer could be 3 or 6 based on which player won)
Win-2: a4+a5+a6
Win-3: a7+a8+a9
Win-4: a1+a4+a7
....
Win-7: a1+a5+a9
Win-8: a3+a5+a7
Now we know that if player one crosses a1 then we need to reevaluate sum of 3 variables: Win-1, Win-4 and Win-7. Whichever 'Win-?' variables reaches 3 or 6 first wins the game. If Win-1 variable reaches 6 first then Player-2 wins.
I do understand that this solution is not scalable easily.
例如，如果您有 5*5 的边界字段，我使用了下一种检查方法：
我认为，它更清晰，但可能不是最好的方法。
If you have boarder field 5*5 for examle, I used next method of checking:
I think, it's more clear, but probably is not the most optimal way.
这是我使用二维数组的解决方案：
Here is my solution using an 2-dimensional array:
不确定此方法是否已发布。 这应该适用于任何 m*n 棋盘，并且玩家应该填补“winnerPos”连续位置。 这个想法是基于运行窗口的。
Not sure if this approach is published yet. This should work for any m*n board and a player is supposed to fill "winnerPos" consecutive position. The idea is based on running window.
我只是想分享我在 Javascript 中所做的事情。 我的想法是有搜索方向； 在网格中，它可以是 8 个方向，但搜索应该是双向的，因此 8 / 2 = 4 个方向。 当玩家移动时，搜索从该位置开始。 它会搜索 4 个不同的双向，直到其值与玩家的棋子（O 或 X）不同。
每次双向搜索，可以添加两个值，但需要减去一个，因为起点重复。
该
函数可以与两个参数（x，y）一起使用，它们是最后一次移动的坐标。 在初始执行中，它使用 4 个参数递归调用 4 次双向搜索。 所有结果均以长度形式返回，函数最终在 4 个双向搜索中选择最大长度。
I just want to share what I did in Javascript. My idea is to have search directions; in grid it could be 8 directions, but search should be bi-directional so 8 / 2 = 4 directions. When a player does its move, the search starts from the location. It searches 4 different bi-directions until its value is different from the player's stone(O or X).
Per a bi-direction search, two values can be added but need to subtract one because starting point was duplicated.
}
This function can be used with two parameters (x,y), which are coordinates of the last move. In initial execution, it calls four bi-direction searches recursively with 4 parameters. All results are returned as lengths and the function finally picks the maximum length among 4 search bi-directions.
在另一个线程上有一个井字游戏问题，我现在找不到，但我找到了这个，所以这是我在阅读问题后创建的井字游戏模拟器：
There was a tic-tac-toe question on another thread that I can't find now, but I found this, so here was my tic-tac-toe simulator I whipped up after reading the question:
我曾为此开发过一种算法，作为科学项目的一部分。
您基本上将棋盘递归地划分为一堆重叠的 2x2 矩形，测试在 2x2 正方形上获胜的不同可能组合。
它很慢，但它的优点是可以在任何尺寸的板上工作，并且具有相当线性的内存要求。
我希望我能找到我的实现
I developed an algorithm for this as part of a science project once.
You basically recursively divide the board into a bunch of overlapping 2x2 rects, testing the different possible combinations for winning on a 2x2 square.
It is slow, but it has the advantage of working on any sized board, with fairly linear memory requirements.
I wish I could find my implementation