Going off on a bit of a tangent here (thought it might be interesting!) - I first came across this topic in one of Russ Cox's blog posts (https://research.swtch

Going off on a bit of a tangent here (thought it might be interesting!) - I first came across this topic in one of Russ Cox's blog posts (https://research.swtch.com/tictactoe https://research.swtch.com/tictactoe). In TAOCP Volume 4A, Knuth discusses how optimal tic-tac-toe moves can be represented using boolean logic. I just went over the section again, and I'll do my best to break down his algorithm: He starts by picturing 2 3x3 grids - one for the X’s and another for the O’s. This setup introduces 18 boolean variables - x1 to x9 for the X's, and o1 to o9 for the O's. I think this can be neatly represented as a bit array (see https://github.com/denkspuren/BitboardC4/blob/master/BitboardDesign.md https://github.com/denkspuren/BitboardC4/blob/master/Bitboar...). Now, creating a full-scale truth table for these 18 variables means we would be looking at 2^18, or 262,144 rows. However, it turns out only 4520 of those are legal inputs. So, the question becomes, how do we find patterns in this boolean chain to build our tic-tac-toe strategies. Knuth simplifies it by considering only the following strategies - (a.) winning - when putting an X in a cell wins the game - like when two cells in any line already have X's. (b.) blocking - when putting an X in a cell stops the other player from winning - like when two cells in any line have O's. (c.) forking - when putting an X in a cell opens up multiple winning moves - you store all the winning line possibilities (horizontal, vertical, and diagonal lines - all 9) in a set, and for each winning line (say {i, j, k}), you place an X on i, leave k empty, and see if a move on j creates two win chances. (d.) defending - similar, when putting an X in a cell stops the other player from creating multiple win chances. (e.) And just making any legal move - when a cell does not have an X or an O. The priority order of moves follows the order above. There's also a bit of priority within the legal moves - like the middle spot is best since it's part of more winning lines, while the edges are the last choice. As I am writing all this, I think it might not seem all that cool until you actually check out the boolean equations for yourself! Pretty neat stuff.