CSC242, AI: 3DTTT -- Win and threat detection

Disclaimer

The following is a very brief recounting of about 30 mins of thinking on these problems. I believe one 242 student may bave already improved on them, at least in terms of speed. Not only that, but it's only one guy's idea. There may be a much better static evaluator idea out there: please feel free to use your own!

State Representation

Two N-squared long column vectors, one for me and for him, with 1's where I have pieces and 0's elsewhere, same for him. Put together into 2-column matrix S.

Threat Space

Represented by an array with N-squared columns and as many rows as there are winning-positions (something like 8 for regular TTT, 74 or so for 3D TTT). This array is made in advance, with each row (like a special sort of (sub)state) representing a win (1's where the N pieces line up for the win, 0's elsewhere). So for instance in the 3x3, 2D game there'd be eight rows like
111000000
000111000
100010001
...

Call this big "threat space" matrix T. It sounds cooler than 'promise space'. I can use it to evaluate my opponent's threats to me, and vice versa. And it makes sense that these threats are the inverse of the "promise" of the position for the player.

Let's call a spot on the board into which a player can put a marker a "cell" -- so the 3x3 2D game has eight 2-D cells and a 4x4 3-D board has 64 3-D cells. A board position consists of a set of cells with "X"'s (put there by me) and another set of cells with "O"'s put there by my opponent. Let us represent a position, then, by two N-squared vectors, each representing the cells of the game. One has 1's where my "X's" are, and the other has 1's where his "O"'s are, and they both have 0's elsewhere. The rows of the threat space look just like this...in fact, if (and only if) my position has 1's in all the positions of one of those rows, I've won, and if his does, he's won.

Now one way to measure the similarity of two vectors is to subtract them and look for a small difference, and the other is to take their dot product and look for an answer near 1 (the cosine of their angle difference). Less generally, but more to the point, if I take the dot product of my position vector and a "won position" vector row from T, that gives the count of the number of X's I have IN THAT WINNING POSITION. If it's N, I've won. Likewise I can dot-product my opponent's vector (telling where his "O"'s are) by rows of T and see how many pieces he has lined up in a winning position.

[Optional Footnote: I call T the "threat space" because it provides a basis (in linear algebra terms: i.e. a set of vectors) with which to express any state: how well I match possible wins tells me how promising my position is and how well he matches possible wins tells me how threatening his position is). Each position vector b (written as a column vector) is "projected into threat space" by the matrix multiplication Tb, which does a bunch of dot products.]

We can compute an the promise of my position (threats to him) by computing the dot-product with all won positions. Similarly dot-producting with his positon give his promise (threats to me.) In fact we can construct the matrix B by pasting the two column position vectors for me and my opponent together and getting an N-squared row, 2-column matrix B which can be multiplied by T, with the resulting two-column 'assessment' matrix A giving all the promise and threats for each of us: A = TB. It has as many rows as there are won positions and in each row we see how much my and his positions 'resemble' that particular won position.

Win Detection

The matrix multiplication TB gives 2-column "promise and threats" matrix output. Its entries are dot products, so you can see (as we noted earlier) that any entry equal to N denotes a win: a matchup of N pieces from somebody's board state b and a known winning position with N pieces in a row. Thus an N in the B matrix means somebody's won: a 'winner' row will look like [N,0] or [0,N].

Blocking Detection

"Why that zero in winner rows?", you may ask. Well, you'll never see an N any other way, but here's why. Notice you should ignore promising positions that are blocked by the other player, and ignore threats from him that you've already blocked. In the "promise and threats" matrix B, these blocked-up no-win positions are those with no zero in them: there are positive counts both for him and for me. If both He and I have pieces in this particular won position, we're blocking the win for each other and it poses no threat to either side. Cute, eh?

Evaluation

Clearly in row of B, 3's represent that a player has 3 pieces in a row, etc. My simple-minded idea is to evaluate his and your threats by some function of the number or size of rows that look like [k,0]: you have k pieces participating in a won position and he has not blocked your hopes. Likewise of course you'll compute his promise (his threats to you) by some function of the rows that look like [0,j]. You are looking for one number that accurately measures goodness of the position for you.

Broader Issues

This is projecting the state onto threat space in true dot-product style, like other forms of correlation detection and basis-decomposition linear algebraic applications. Very elegant and classical, eh? Too bad the actual use of the output is presumably totally nonlinear (e.g. the 'excluded blocked threats' argument above).

---

This page is maintained by CB.

Last update: 2.3.10