Linear evaluations with tic-tac-toe, some data

[towforce]

Step 1: Chris's data converted to a usable format (for those of us who use data structures and hence write readable/maintainable code ) - link.

[jefk]

ttt n x n is probably a draw, although it hasn't been 'solved'.

Argument: 1) the first player has an advantage
2) the second player can use a 'sabotaging' strategy where
always a piece is placed on the row/column with the most pieces
thus always preventing the full completion of one line (row or column).
3) it works, as i noticed when doing some quick games for 4 x 4.
where it is -almost- certainly a draw.

For 5 x 5 etc drawing becomes usually even more easy, which is why
often -for human game play- the rules are changed, eg already
claiming a win when a 4 (n-1?) adjacent pieces are achieved.

Conclusion: for ttt 4x4 which surprisingly apparently not yet has been
'weakly solved' (imo could be done without excessive efforts) i claim an ultraweak
solution, namely, draw (no scientific paper yet but could do that easily with AI

For 5x5 etc nxn i could work on a similar conclusion but it takes
a bit (resp considerably) more work for proper confirmation.

[chesskobra]

Can you (Towforce) at least make your claim precise? For example, what is a pattern, what is a deep pattern, how should the solution of chess or Tic-Toc-Tow or any other game look like for it to be considered simple? You may do this in a simplified model, and the following is a suggestion, but you may propose another simplified model or framework in which the problem may be posed precisely (and hopefully also solved in a simple manner for a toy game). The model I suggest below does not require any data.

A game is played on a 3x3 board by 2 players O and X (or just 1x9 board for simplicity). They take turns to place a piece on an empty square. On their turns, O and X place a piece of type O or X, respectively. The game ends when the board is full, at which time one of the players wins the game according to some rules. The end position is evaluated 1 if O wins, and -1 if X wins. Given the values of the end positions, we can work backwards with min-max to find the value of any other position in which the board is partially occupied. Since O opens the game, the valid positions are the ones in which there is one more O than X on the board (X to move) or there are equal number of Os and Xs on the board (O to move). We can ignore symmetries, i.e., we may consider positions that can be obtained by rotation or reflection from each other to be distinct.

There are C(9,5) = 126 (the binomial coefficient) end positions (5 out of 9 pieces are O and remaining 4 are X), hence 2^126 functions possible from the set of end positions to the set of outcomes {-1,1}. Each one of these functions represents a Tic-Tac-Toe like game. (To be clear, each function is a different game - not as in the number of possible Tic-Tac-Toe games, but as in the number of possible Tic-Tac-Toe like games.) Given any of the functions, we can do min-max to evaluate all other legal positions.

Now we represent the i-th square by a variable x_i, which takes value 0 or 1 or 2 depending on whether it is empty or occupied by O or by X, respectively. Now given any one of the 2^126 TTT like games, we want a simple function f(x_1,...,x_8) that correctly gives the min-max outcome for any position in the game tree of that game.

Please tell us how simple f must be to be called simple? Should f be a polynomial with some restrictions on the degree or on the coefficients? Let us consider linear polynomials with 0 constant term: f(x_1,...,x_9) = a_1x_1 + ... + a_9x_9, with each a_i an integer in the range -k to k. Let us also assume that a_i cannot be 0 since that would make the outcome independent of the piece on a certain square. There are (2k)^9 such polynomials.

You want (2k)^9 >= 2^126, otherwise some different games would be indistinguishable by our polynomials, i.e., the prediction or evaluation of positions in some games will be wrong. That gives k^9 >= 2^117 or k >= 2^13. This is a necessary condition, not sufficient. So given a game (one of the 2^126 assignments of -1 or 1 to the end positions) we may or may not be able to find a linear polynomial with coefficients in the range -2^13 and 2^13 that solves any position in the game.

Now we have another difficulty to overcome if the above scheme is to work. Suppose that the polynomial looks like 100x_1 - 37x_2 + .... Now substituting either (x_1,x_2) = (1,2) or (x_1,x_2) = (2,1) both result in legal positions, but their evaluations would be 100x1-37x2+A and 100x2-37x1+A, for some A, i.e., their evaluations do not differ by 0 or 2. Therefore, any two coefficient a_i and a_j must be such that (a_1 + 2a_j) - (2a_i + a_j) is either 0 or 2 or -2.

Now this last difficulty seems serious. Looks like we don't have enough simple polynomials. Even if you say that all these 2^126 games are irrelevant; we are just dealing with Tic-Tac-Tow, which is much simpler than an arbitrary assignments of -1 and 1 to the end positions, your simple polynomial will still suffer from the above difficulty. Considering real coefficients does not solve the problem, because if ultimately the inputs and outputs are integers, different polynomials with real coefficients would be equivalent.

[abulmo2]

Btw, a "linear polynomial" is a polynomial of degree 1. At degree 2 or above, it becomes non linear.

Not sure it makes a difference here , according to wikipedia on polynomial regression:
"The polynomial regression model [...] can be expressed in matrix form in terms of a design matrix X a response vector y a parameter vector β and a vector ε of random errors. The i-th row of X and y will contain the x and y value for the i-th data sample. Then the model can be written as a system of linear equations"