# Infinite sums, integer sequences

Yesterday my son told me “You know Dad, when you add 1/10 + 4/100 + 9/1000 + 16/10000 forever you end up with **110/729**.”

This was part of a discussion we started a year ago when I was teaching him about repeating decimals. We started easy with 1/10 + 1/100 + 1/1000 forever is 1/9, moved on to stuff like 1/9 + 1/81 + 1/729 etc is 1/8. He particularly likes 1/49, which has a 42 digit repeat and is 0.0204081633..etc or the sum of **(2^n)/(100^n)** where n is 1..infinity.

He also likes how 1/4 is related to 1/49 and 1/499. 1/4 is sum(**(2^n)/(10^n)**) (n <- 1..infinity), 1/49 is sum(**(2^n)/(100^n)**), and 1/499 is sum(**(2^n)/(1000^n)**).

Anyway, since 1/4 is sum((**2^n**)/(10^n)), we briefly wondered what sum((**n^2**)/(10^n)) was. I didn’t know, and I forgot about it.

But my son remembered and somehow calculated it to be **110/729**. Then he told me sum(**(n^2)/(100^n)**) is **10100/(99^3)**. So I suggested maybe sum(**(n^2)/(X^n)**) (n <- 1..infinity) is **(X*(X+1))/((X-1)^3)**.

That’s kind of cool. It’s related to the fact that 1/2 + 1/4 + 1/8 + ..etc.. is 1, and 1/3 + 1/9 + 1/27 + ..etc.. is 1/2, and in general sum(**1/(B^n)**) is **1/(B-1)** (summing over n <- 1..infinity). And also 1/2 + 2/4 + 3/8 + ..etc.. is 2, and 1/3 + 2/9 + 3/27 + ..etc.. is 3/4, and in general sum(**n/(B^n)**) is **B/((B-1)^2)**. So if my guess above is right maybe we’ve caught a pattern. Take a look:

Summing over n <- 1..infinity: sum((n^0)/(B^n)) is (1 /((B-1)^1)) sum((n^1)/(B^n)) is (B /((B-1)^2)) sum((n^2)/(B^n)) is (B(B+1))/((B-1)^3)

That’s interesting. And the denominator follows the obvious pattern as we go forward. For sum(**(n^3)/(B^n)**) it’s **(B-1)^4**, for sum(**(n^4)/(B^n)**) it’s **(B-1)^5**, etc. As for the numerator, you’d think **B(B+1)(B+2)** might be next.

But it’s not. The numerator is a lot weirder than that.

Let’s look at this again:

Summing over n <- 1..infinity: sum((n^0)/(B^n)) is v0/((B-1)^1) where v0 is 1 sum((n^1)/(B^n)) is v1/((B-1)^2) where v1 is B sum((n^2)/(B^n)) is v2/((B-1)^3) where v2 is B(B+1) sum((n^3)/(B^n)) is v3/((B-1)^4) where v3 is ? ... sum((n^A)/(B^n)) is vA/((B-1)^(A+1))

Is there an easy way to describe the numerators v3, v4, v5, etc? To find out I wrote some code. You can see it here (in **series.erl**). Here’s what the function **sum_na_over_bn_numerator** (and **list_close_sum_na_over_bn_numerator_for_b**) told me:

For A | Numerator when B is 2 | Numerator when B is 3 | Numerator when B is 4 | Numerator when B is 5 |
---|---|---|---|---|

0 | 1 | 1 | 1 | 1 |

1 | 2 | 3 | 4 | 5 |

2 | 6 | 12 | 20 | 30 |

3 | 26 | 66 | 132 | 230 |

4 | 150 | 480 | 1140 | 2280 |

5 | 1082 | 4368 | 12324 | 28280 |

6 | 9366 | 47712 | 160020 | 421680 |

7 | 94586 | 608016 | 2424132 | 7336880 |

8 | 1091670 | 8855040 | 41967540 | 145879680 |

9 | 14174522 | 145083648 | 817374564 | 3263031680 |

The first three rows are **1**, **B**, and **B(B+1)** as I stated above. But the rows after that are harder to figure. If the next numerator were **B(B+1)(B+2)**, the 4th row (where A is 3) would be **24, 60, 120, 210** instead of **26, 66, 132, 230**. I don’t know of a simple expression to generate this sequence.

The column where B is 2 is the sequence [1, 2, 6, 26, 150, 1082, 9366, 94586, 1091670, 14174522, 204495126, etc]. This series is described as the Number of necklaces of sets of labeled beads (A000629) in the Encyclopedia of Integer Sequences (att.com). It is also mentioned in Stirling Number of the Second Kind (wolfram.com).

The column where B is 3 is the sequence [1, 3, 12, 66, 480, 4368, 47712, 608016, 8855040, 145083648, 2641216512, etc]. This series is also (sort of) described in the Encyclopedia of Integer Sequences (att.com) where it is called the Expansion of ln(1+sinh(x)/exp(x)) (A009362). But A009362 is not exactly the same sequence since it starts with 0 and has alternating positive and negative integers, like this: [0, 1, -3, 12, -66, 480, -4368, 47712, -608016, etc].

We can turn this table on its side with the function **list_close_sum_na_over_bn_numerator_for_a** and look at other integer sequences.

For B | Numerator when A is 0 | Numerator when A is 1 | Numerator when A is 2 | Numerator when A is 3 | Numerator when A is 4 |
---|---|---|---|---|---|

2 | 1 | 2 | 6 | 26 | 150 |

3 | 1 | 3 | 12 | 66 | 480 |

4 | 1 | 4 | 20 | 132 | 1140 |

5 | 1 | 5 | 30 | 230 | 2280 |

6 | 1 | 6 | 42 | 366 | 4074 |

7 | 1 | 7 | 56 | 546 | 6720 |

8 | 1 | 8 | 72 | 776 | 10440 |

9 | 1 | 9 | 90 | 1062 | 15480 |

10 | 1 | 10 | 110 | 1410 | 22110 |

11 | 1 | 11 | 132 | 1826 | 30624 |

And of course the 2nd column (where A=0) is always 1, the 3rd column is the same as B, and the fourth column is B(B+1).

The fourth column values (*B(B+1)*) are also known as the Pronic Numbers. In the Encyclopedia they are called the Oblong (or pronic, or heteromecic) numbers: n(n+1) (A002378).

I don’t have names for any of the other integer sequences in the tables above. I’ll list a few of them here in case someone ever googles them. (I don’t think google is very good at recognizing number sequences in table columns.)

**The following lists are just google bait. Read above to find out where they came from.**

Sequences from list_close_sum_na_over_bn_numerator_for_a( N ):

- 26, 66, 132, 230, 366, 546, 776, 1062, 1410, 1826
- 150, 480, 1140, 2280, 4074, 6720, 10440, 15480, 22110, 30624
- 1082, 4368, 12324, 28280, 56670, 103152, 174728, 279864, 428610, 632720
- 9366, 47712, 160020, 421680, 948570, 1907136, 3525192, 6103440, 10027710, 15781920

Sequences from list_close_sum_na_over_bn_numerator_for_b( N ):

- 3, 12, 66, 480, 4368, 47712, 608016, 8855040, 145083648, 2641216512
- 4, 20, 132, 1140, 12324, 160020, 2424132, 41967540, 817374564, 17688328020
- 5, 30, 230, 2280, 28280, 421680, 7336880, 145879680, 3263031680, 81097294080
- 6, 42, 366, 4074, 56670, 948570, 18532590, 413749770, 10391253630, 289972117050

# Tic-tac-toe in Erlang — alternative rules (Y pattern)

This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called **tic.erl** and available here.

There are also smaller Erlang modules for analyzing game-spaces called **tic_count.erl** and **tic_game_space.erl**.

There are also alternative versions of **tic.erl** and **tic_game_space.erl** called **tic2.erl** and **tic_game_space2.erl**. With these alternatives you can experiment with different rules for playing. For example, you can set the rules so 3-in-a-row does NOT win, but a Y-shaped arrangment does. There are a lot of alternative combinations of rules to choose from.

The tutorial is organized as follows:

- Introduction
- Top-level loop
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction
- Utilities to introduce randomness
- Macros for testing and debugging

### Alternative rules

In my last post I mentioned that, according to Wikipedia, some people treat a Y-shaped arrangment of marks as a tic-tac-toe win.

That started me wondering how special rules affect the tic-tac-toe game-space. So I hacked **tic.erl** (alternative-rules version: **tic2.erl**) and **tic_game_space.erl** (alternative rules version: **tic_game_space2.erl**) to find out.

The alternative-rule code has the following functions to check for winning games:

% -------------------------------------------------------------- % is_board_won_all_rows( Board, Mark ) % is_board_won_all_columns( Board, Mark ) % is_board_won_rising_diagonal( Board, Mark ) % is_board_won_falling_diagonal( Board, Mark ) % is_board_won_upright_Y( Board, Mark ) % is_board_won_tilt_right_Y( Board, Mark ) % is_board_won_upside_down_Y( Board, Mark ) % is_board_won_tilt_left_Y( Board, Mark ) % is_board_won_four_corners( Board, Mark ) % is_board_won_four_sides( Board, Mark ) % is_board_won_nw_bend( Board, Mark ) % is_board_won_ne_bend( Board, Mark ) % is_board_won_sw_bend( Board, Mark ) % is_board_won_se_bend( Board, Mark ) % % All possible winning board patterns, including % experimental ones controlled by preprocessor macros. % --------------------------- % Check for 3-in-a-row: is_board_won_all_rows( {X,X,X, _,_,_, _,_,_}, X ) -> true; is_board_won_all_rows( {_,_,_, X,X,X, _,_,_}, X ) -> true; is_board_won_all_rows( {_,_,_, _,_,_, X,X,X}, X ) -> true; is_board_won_all_rows( _ , _ ) -> false. % --------------------------- % Check for 3-in-a-column: is_board_won_all_columns( {X,_,_, X,_,_, X,_,_}, X ) -> true; is_board_won_all_columns( {_,X,_, _,X,_, _,X,_}, X ) -> true; is_board_won_all_columns( {_,_,X, _,_,X, _,_,X}, X ) -> true; is_board_won_all_columns( _ , _ ) -> false. % --------------------------- % Check the diagonals. is_board_won_rising_diagonal( {_,_,X, _,X,_, X,_,_}, X ) -> true; is_board_won_rising_diagonal( _ , _ ) -> false. is_board_won_falling_diagonal( {X,_,_, _,X,_, _,_,X}, X ) -> true; is_board_won_falling_diagonal( _ , _ ) -> false. % --------------------------- % Check the Y's is_board_won_upright_Y( {X,_,X, _,_,_, _,X,_}, X ) -> true; is_board_won_upright_Y( _ , _ ) -> false. is_board_won_tilt_right_Y( {_,_,X, X,_,_, _,_,X}, X ) -> true; is_board_won_tilt_right_Y( _ , _ ) -> false. is_board_won_upside_down_Y( {_,X,_, _,_,_, X,_,X}, X ) -> true; is_board_won_upside_down_Y( _ , _ ) -> false. is_board_won_tilt_left_Y( {X,_,_, _,_,X, X,_,_}, X ) -> true; is_board_won_tilt_left_Y( _ , _ ) -> false. % --------------------------- % Check corners - 4-mark pattern is_board_won_four_corners( {X,_,X, _,_,_, X,_,X}, X ) -> true; is_board_won_four_corners( _ , _ ) -> false. % --------------------------- % Check sides - 4-mark pattern is_board_won_four_sides( {_,X,_, X,_,X, _,X,_}, X ) -> true; is_board_won_four_sides( _ , _ ) -> false. % --------------------------- % Check the corner bends is_board_won_nw_bend( {X,X,_, X,_,_, _,_,_}, X ) -> true; is_board_won_nw_bend( _ , _ ) -> false. is_board_won_ne_bend( {_,X,X, _,_,X, _,_,_}, X ) -> true; is_board_won_ne_bend( _ , _ ) -> false. is_board_won_sw_bend( {_,_,_, X,_,_, X,X,_}, X ) -> true; is_board_won_sw_bend( _ , _ ) -> false. is_board_won_se_bend( {_,_,_, _,_,X, _,X,X}, X ) -> true; is_board_won_se_bend( _ , _ ) -> false.

You control which of these rules is in force with the following preprocessor macros, which expand to either **true** or **false**.

== Normal Rules - default true == c_win_pattern_all_rows c_win_pattern_all_columns c_win_pattern_rising_diagonal c_win_pattern_falling_diagonal == Rules for Y-shaped patterns - default false == c_win_pattern_upright_Y c_win_pattern_tilt_right_Y c_win_pattern_upside_down_Y c_win_pattern_tilt_left_Y == 4-mark rules - default false == c_win_pattern_four_corners c_win_pattern_four_sides == Rules for corner-bend patterns - default false == c_win_pattern_nw_bend c_win_pattern_ne_bend c_win_pattern_sw_bend c_win_pattern_se_bend

You can set these preprocessor macros when you compile/load the module. For example, to get **?c_win_pattern_all_rows** to expand to **false** and **?c_win_pattern_upright_Y** to expand to **true**, do the following. It’s flexible, but a little difficult to type.

1> c( '/erlang/tic_game_space2', 1> [ {d, c_symmetry_collapse, false}, 1> {d, c_win_pattern_upright_Y, true} ]). {ok,tic_game_space2}

An alternative would be to add function params or UI to specify these options. But I used preprocessor flags because it’s a quick (albeit dirty) solution. Good enough when you’re just experimenting.

### Normal rules

First of all, remember the game-space for normal-rules tic-tac-toe looks something like this. I’ve covered this before in earlier posts.

1> c( '/erlang/tic_game_space2', 1> {d, c_symmetry_collapse, false}). {ok,tic_game_space2} 2> tic_game_space2:report0( ). Full tic-tac-toe game space: Player 1: all moves Player 2: all moves Large game space -- no symmetry collapse Total number of game paths: 255168 Total number of boards: 5478 Player 1 winning boards : 626 Player 2 winning boards : 316 Player 1 must respond to: 2423 Player 2 must respond to: 2097 Tie boards : 16 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 2739 Boards produced by player 2: 2738 ok

When you reduce the game space by collapsing symmetries (treating all rotated and reflected tic-tac-toe boards as equal) you end up with this.

1> c( '/erlang/tic_game_space2', 1> {d, c_symmetry_collapse, true}). {ok,tic_game_space2} 2> tic_game_space2:report0( ). Full tic-tac-toe game space: Player 1: all moves Player 2: all moves Reduced game space -- 8-fold symmetry collapse Total number of game paths: 26830 Total number of boards: 765 Player 1 winning boards : 91 Player 2 winning boards : 44 Player 1 must respond to: 338 Player 2 must respond to: 289 Tie boards : 3 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 383 Boards produced by player 2: 381 ok

If you just analyze “smart” moves (moves that do not worsen your position), the game space shrinks even further. This gets rid of all winning games because either player can force a draw.

1> c( '/erlang/tic_game_space2', 1> {d, c_symmetry_collapse, false}). {ok,tic_game_space2} 2> tic_game_space2:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Large game space -- no symmetry collapse Total number of game paths: 3584 Total number of boards: 884 Player 1 winning boards : 0 Player 2 winning boards : 0 Player 1 must respond to: 417 Player 2 must respond to: 451 Tie boards : 16 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 467 Boards produced by player 2: 416 ok

And when you collapse symmetries in the smart game space you have an even smaller game-space. You end up with only distinct 336 tie games and 125 boards.

1> c( '/erlang/tic_game_space2', 1> {d, c_symmetry_collapse, true}). {ok,tic_game_space2} 2> tic_game_space2:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Reduced game space -- 8-fold symmetry collapse Total number of game paths: 336 Total number of boards: 125 Player 1 winning boards : 0 Player 2 winning boards : 0 Player 1 must respond to: 58 Player 2 must respond to: 64 Tie boards : 3 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 67 Boards produced by player 2: 57 ok

### What if Y-shaped patterns also win?

So what if we expand the rules of tic-tac-toe so that you can also win by playing a Y-shaped pattern (or a rotated Y-shape). You get this:

1> c( '/erlang/tic_game_space2', 1> [ {d, c_symmetry_collapse, false}, 1> {d, c_win_pattern_upright_Y, true}, 1> {d, c_win_pattern_tilt_right_Y, true}, 1> {d, c_win_pattern_upside_down_Y, true}, 1> {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic_game_space2} 2> tic_game_space2:report0( ). Full tic-tac-toe game space: Player 1: all moves Player 2: all moves Large game space -- no symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Total number of game paths: 209520 Total number of boards: 5214 Player 1 winning boards : 846 Player 2 winning boards : 428 Player 1 must respond to: 2131 Player 2 must respond to: 1809 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 2655 Boards produced by player 2: 2558 ok

The game space is somewhat smaller with the new rules, but not much (255168 vs 209520 games and 5478 vs 5214 boards). This is because more games end early with one player winning. In fact you can see tie games are not possible — all games end in a win.

You can still collapse out symmetries because all winning patterns, including the Ys, are still rotation/reflection symmetric.

1> c( '/erlang/tic_game_space2', 1> [ {d, c_symmetry_collapse, true}, 1> {d, c_win_pattern_upright_Y, true}, 1> {d, c_win_pattern_tilt_right_Y, true}, 1> {d, c_win_pattern_upside_down_Y, true}, 1> {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic_game_space2} 2> tic_game_space2:report0( ). Full tic-tac-toe game space: Player 1: all moves Player 2: all moves Reduced game space -- 8-fold symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Total number of game paths: 22100 Total number of boards: 727 Player 1 winning boards : 120 Player 2 winning boards : 59 Player 1 must respond to: 298 Player 2 must respond to: 250 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 370 Boards produced by player 2: 356 ok

Again we see a small reduction in the number of possible games in the game space (26830 vs 22100) and the number of boards (765 vs 727).

The smart game-space looks like this, in full and with collapsed symmetries.

1> c( '/erlang/tic_game_space2', 1> [ {d, c_symmetry_collapse, false}, 1> {d, c_win_pattern_upright_Y, true}, 1> {d, c_win_pattern_tilt_right_Y, true}, 1> {d, c_win_pattern_upside_down_Y, true}, 1> {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic_game_space2} Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Large game space -- no symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Total number of game paths: 33424 Total number of boards: 2985 Player 1 winning boards : 788 Player 2 winning boards : 0 Player 1 must respond to: 1619 Player 2 must respond to: 578 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 1366 Boards produced by player 2: 1618 ok 3> c( '/erlang/tic_game_space2', 3> [ {d, c_symmetry_collapse, true}, 3> {d, c_win_pattern_upright_Y, true}, 3> {d, c_win_pattern_tilt_right_Y, true}, 3> {d, c_win_pattern_upside_down_Y, true}, 3> {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic_game_space2} 4> tic_game_space2:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Reduced game space -- 8-fold symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Total number of game paths: 3495 Total number of boards: 412 Player 1 winning boards : 109 Player 2 winning boards : 0 Player 1 must respond to: 220 Player 2 must respond to: 83 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 192 Boards produced by player 2: 219 ok 5> tic_game_space2:report1( ply_overview). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Reduced game space -- 8-fold symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Player 1 moves, leading to ply 1 2 boards (all continue) 2 boards lead to a win by player 1 Player 2 moves, leading to ply 2 10 boards (all continue) 10 boards lead to a win by player 1 Player 1 moves, leading to ply 3 22 boards (all continue) 22 boards lead to a win by player 1 Player 2 moves, leading to ply 4 81 boards (all continue) 81 boards lead to a win by player 1 Player 1 moves, leading to ply 5 80 boards (53 continuing) 27 boards won by player 1 53 boards lead to a win by player 1 Player 2 moves, leading to ply 6 121 boards (all continue) 121 boards lead to a win by player 1 Player 1 moves, leading to ply 7 81 boards (6 continuing) 75 boards won by player 1 6 boards lead to a win by player 1 Player 2 moves, leading to ply 8 7 boards (all continue) 7 boards lead to a win by player 1 Player 1 moves (last move) 7 boards won by player 1 ok

Oddly enough, although the *total* game space shrinks with the new rules, the *smart* game space expands. The number of smart games goes from 3584 with normal rules to 33424 with these new rules. The board count goes from 884 to 2985.

The reason for this expansion is that with the new rules, the second player cannot avoid losing no matter how smart he is. So the smart game space with the normal rules always leads to tie games, while with the alternative game space there are no ties and all smart games end with the first player winning. The tie game space necks down to just a few boards at the end, but the first-player-wins game space stays wide, especially with the alternative rules.

Here’s a view of the blank board with predicted outcomes for each starting move.

1> c( '/erlang/tic2', 1> [ {d, c_init_board_predictions, true}, 1> {d, c_win_pattern_upright_Y, true}, 1> {d, c_win_pattern_tilt_right_Y, true}, 1> {d, c_win_pattern_upside_down_Y, true}, 1> {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic2} 2> tic2:play( ). Playing with special rules: V (Y) wins < wins ^ wins > wins Welcome to tic-tac-toe, the game that predicts the outcomes of every move and lets you erase X's and O's and skip turns. Starting a new game. [] [] 1 Wins in [] 2 Wins in [] 3 Wins in three turns [] four turns [] three turns after this [] after this [] after this [] [] ===============##===============##=============== [] [] 4 Wins in [] 5 Loses in [] 6 Wins in four turns [] four turns [] four turns after this [] after this [] after this [] [] ===============##===============##=============== [] [] 7 Wins in [] 8 Wins in [] 9 Wins in three turns [] four turns [] three turns after this [] after this [] after this [] [] It is X's turn to move. What do you want to do (h=help, q=quit)?

This confirms that Y-shaped winning patterns confers a huge advantage on the starting player. By starting in a corner, he can win in just three moves, the minimun ever needed. Even with no mistakes the second player can lose with only two **O**s on the board.

I was a surprised to see that if the first player starts in the middle, the second player can force a win. Let’s see what that game space looks like, where we force the first move to be in the middle and only look at smart moves after that.

1> c( '/erlang/tic_game_space2', [ {d, c_symmetry_collapse, true}, {d, c_win_pattern_upright_Y, true}, {d, c_win_pattern_tilt_right_Y, true}, {d, c_win_pattern_upside_down_Y, true}, {d, c_win_pattern_tilt_left_Y, true} ]). {ok,tic_game_space2} 2> tic_game_space2:report( summary, middle_init_move, smart_moves, smart_moves). Tic-tac-toe game-space: First moves (player 1): Middle only (1 move) Player 1 move filter: Smart moves only Player 2 move filter: Smart moves only Reduced game space -- 8-fold symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Total number of game paths: 84 Total number of boards: 62 Player 1 winning boards : 0 Player 2 winning boards : 20 Player 1 must respond to: 10 Player 2 must respond to: 32 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 32 Boards produced by player 2: 29 ok 3> tic_game_space2:report( 3> ply_overview, middle_init_move, 3> smart_moves, smart_moves). Tic-tac-toe game-space: First moves (player 1): Middle only (1 move) Player 1 move filter: Smart moves only Player 2 move filter: Smart moves only Reduced game space -- 8-fold symmetry collapse Playing with special rules: V (Y) wins < wins ^ wins > wins Winning patterns are symmetric Player 1 moves, leading to ply 1 1 boards (all continue) 1 boards lead to a win by player 2 Player 2 moves, leading to ply 2 1 boards (all continue) 1 boards lead to a win by player 2 Player 1 moves, leading to ply 3 4 boards (all continue) 4 boards lead to a win by player 2 Player 2 moves, leading to ply 4 3 boards (all continue) 3 boards lead to a win by player 2 Player 1 moves, leading to ply 5 15 boards (all continue) 15 boards lead to a win by player 2 Player 2 moves, leading to ply 6 15 boards (5 continuing) 10 boards won by player 2 5 boards lead to a win by player 2 Player 1 moves, leading to ply 7 12 boards (all continue) 12 boards lead to a win by player 2 Player 2 moves, leading to ply 8 10 boards (0 continuing to ties) 10 boards won by player 2 Player 1 moves (last move) ok

Yep, that confirms it. With these alternative rules, player 2 can always win if player 1 starts in the middle. The following shows that at least player 1 can delay the loss and force player 2 to make 4 moves.

4> tic2:play( ). Playing with special rules: V (Y) wins < wins ^ wins > wins Welcome to tic-tac-toe, the game that predicts the outcomes of every move and lets you erase X's and O's and skip turns. Starting a new game. [] [] 1 Wins in [] 2 Wins in [] 3 Wins in three turns [] four turns [] three turns after this [] after this [] after this [] [] ===============##===============##=============== [] [] 4 Wins in [] 5 Loses in [] 6 Wins in four turns [] four turns [] four turns after this [] after this [] after this [] [] ===============##===============##=============== [] [] 7 Wins in [] 8 Wins in [] 9 Wins in three turns [] four turns [] three turns after this [] after this [] after this [] [] It is X's turn to move. What do you want to do (h=help, q=quit)? 5 Marking X at position 5. [] [] 1 Wins in [] 2 Loses in [] 3 Wins in four turns [] three turns [] four turns after this [] after this [] after this [] [] ===============##===============##=============== [] XXX XXX [] 4 Loses in [] XX XX [] 6 Loses in three turns [] XXX [] three turns after this [] XX XX [] after this [] XXX XXX [] ===============##===============##=============== [] [] 7 Wins in [] 8 Loses in [] 9 Wins in four turns [] three turns [] four turns after this [] after this [] after this [] [] It is O's turn to move. What do you want to do (h=help, q=quit)?

### What if just one Y-pattern wins?

The above analysis shows that making all the Ys winning patterns in tic-tac-toe distorts the game, allowing player 1 to easily win. But what if only one Y-pattern is a winner, instead of all 4 rotations? Maybe that will balance the game a little.

The winning patterns no longer have 8-fold symmetry, but we can still explore the game space.

1> c( '/erlang/tic_game_space2', 1> [ {d, c_symmetry_collapse, false}, 1> {d, c_win_pattern_upright_Y, true} ]). {ok,tic_game_space2} 2> tic_game_space2:report0( ). Full tic-tac-toe game space: Player 1: all moves Player 2: all moves Large game space -- no symmetry collapse Playing with special rules: V (Y) wins Winning patterns are not symmetric Total number of game paths: 243252 Total number of boards: 5412 Player 1 winning boards : 688 Player 2 winning boards : 351 Player 1 must respond to: 2343 Player 2 must respond to: 2022 Tie boards : 8 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 2718 Boards produced by player 2: 2693 ok 3> tic_game_space2:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Large game space -- no symmetry collapse Playing with special rules: V (Y) wins Winning patterns are not symmetric Total number of game paths: 21094 Total number of boards: 2755 Player 1 winning boards : 656 Player 2 winning boards : 0 Player 1 must respond to: 1507 Player 2 must respond to: 592 Tie boards : 0 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 1248 Boards produced by player 2: 1506 ok

It looks like player 1 can still always force a win. But at least tie games are possible with these rules.

Let’s see what the first move looks like.

4> c( '/erlang/tic2', 4> [ {d, c_init_board_predictions, true}, 4> {d, c_win_pattern_upright_Y, true} ]). {ok,tic2} 5> tic2:play( ). Playing with special rules: V (Y) wins Welcome to tic-tac-toe, the game that predicts the outcomes of every move and lets you erase X's and O's and skip turns. Starting a new game. [] [] 1 Wins in [] 2 Leads to [] 3 Wins in four turns [] CAT game [] four turns after this [] [] after this [] [] ===============##===============##=============== [] [] 4 Leads to [] 5 Leads to [] 6 Leads to CAT game [] CAT game [] CAT game [] [] [] [] ===============##===============##=============== [] [] 7 Wins in [] 8 Wins in [] 9 Wins in four turns [] four turns [] four turns after this [] after this [] after this [] [] It is X's turn to move. What do you want to do (h=help, q=quit)?

There are still plenty of ways for the first player to force a win, just not as quickly as before when player 1 could win in just 3 moves instead of 4. So maybe this is a slightly more balanced game.

Also, whereas before starting in the middle let player 2 win, this time starting in the middle will probably just lead to a tie game. I admit I kind of liked it the other way. It suggested a more chaotic, and thus less predictable, game space.

### Conclusion

And that’s what happens to tic-tac-toe when you start changing the rules. We’ve talked about 2 sets of alternative rules, where the Y pattern and its rotations can win the game, and where just one Y pattern can win. Here’s how the sizes of the game space and the total board counts vary under the rule changes.

Game space | Symmetries | Rules | Game paths | Board count |
---|---|---|---|---|

Full | Expanded | Normal | 255168 | 5478 |

All Ys | 209520 | 5214 | ||

One Y | 243252 | 5412 | ||

Collapsed | Normal | 26830 | 765 | |

All Ys | 22100 | 727 | ||

Smart | Expanded | Normal | 3584 | 884 |

All Ys | 33424 | 2985 | ||

One Y | 21094 | 2755 | ||

Collapsed | Normal | 336 | 125 | |

All Ys | 3495 | 412 |

These rules decrease the size of the entire game space slightly, because they lead to more winning situations early in the game. And the smart game spaces are quite a bit larger under the new rules, but only because player 2 can be forced into a loss, and even under normal rules there are many more paths leading to losses than to ties. So the smart game spaces are not really comparable.

The one surprise is that the 2nd player can always win if the first player starts in the middle, but only when all 4 Y-patterns are winners. It’s like the game space gets unstable board gets very crowded with possible winning patterns. I hesitate to compare tic-tac-toe to the game of **go**, but one thing that makes **go** fascinating is the chaotic nature of the game space, where tiny perturbations in initial conditions can lead to widely varying results. It makes it hard to predict pattern evolution and cost boards in the early/middle plys.

There are many other variations yet to be explored. **tic2.erl** and **tic_game_space2.erl** can both be set up to recognize other winning patterns. And more exotic explorations are easily imaginable, even if we’re confined to a 3×3 board. For example, you could play a game where the object is to **AVOID** getting 3-in-a-row or any “winning” pattern. Does the 2nd player have the advantage then? And since tie games are not possible when the 4 Y rotations are winning patterns, either the 1st or 2nd player can always force the other to lose.

Or what if instead of alternating turns, we have the 1st player put down a mark, and then the 2nd player put down **two** marks, and then the first player put down 2 marks, etc. Or what if you add more winning patterns but then only play 8 plys instead of 9, so the game ends when there is one empty spot. That makes tie games again possible when Y patterns are winners.

Or what if the first player starts normally, but then the 2nd player not only marks down the first **O** but also circles three spots on the board as an extra winning combination. And after that play continues like in normal tic-tac-toe, except with the one extra winning pattern. This expands the game space quite a bit because it effectively adds an extra ply. Does it shift the advantage away from the starting player?

Maybe I’ll look at some of these possibilities in a later post.

# Tic-tac-toe in Erlang — smart game space

This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called **tic.erl** and available here.

There are also smaller Erlang modules for analyzing game-spaces called **tic_count.erl** and **tic_game_space.erl**.

The tutorial is organized as follows:

- Introduction
- Top-level loop
- User input
- Board display
- Board abstraction
- Game abstraction
- Next move calculations and predictions
- Predicted outcome abstraction
- Utilities to introduce randomness
- Macros for testing and debugging

### Smart game space

In the previous post we talk about the full tic-tac-toe game space and all possible board arrangements. The **tic_game_space:report0()** function from **tic_game_space.erl** tells us there are 255,168 possible tic-tac-toe games and 5478 distinct tic-tac-toe board arrangements. Or if we treat all rotations and reflections of a board as equal, those counts are reduced to 26,830 games and 765 boards.

But some of these games are very unlikely, and require one or both players to pass up obvious wins and make other mistakes. Most players are unlikely to ever encounter many of these boards without perverse effort. So the question arises, how big is tic-tac-toe if you assume the players are rational.

There is code in **tic_game_space.erl** to answer that question. Starting from the full game space, the function **smart_game_space(..)** is able to strip out all the unwise moves and leave us with only the “smart” game paths. The number of boards for each ply in the smart game space is given in the following table.

Number of marks on board | Number of boards treating rotations and reflections as unique | Number of boards treating rotations and reflections as equal |
---|---|---|

0 (0+0) | 1 | 1 |

1 (1+0) | 9 | 3 |

2 (1+1) | 24 | 5 |

3 (2+1) | 102 | 16 |

4 (2+2) | 136 | 18 |

5 (3+2) | 176 | 23 |

6 (3+3) | 180 | 24 |

7 (4+3) | 164 | 22 |

8 (4+4) | 76 | 10 |

9 (5+4) | 16 | 3 |

Totals | 884 | 125 |

All smart games end after 9 moves in a tie so there are no winning boards in this game space. You can only win in tic-tac-toe if the other player makes a mistake.

The number of boards is reduced from 5478 in the full game space to 884 in the smart game space. In the modulo all-reflections-rotations game space the board count is reduced from 765 to 125.

The reports from **tic_game_space.erl** provide more details. For example, we learn there are only 3584 games in the smart game space, reduced from 255,168 in the full space. Here are the reports that treat rotated and reflected boards as unique.

Eshell V5.6.5 (abort with ^G) 1> c( 'c:/src/erlang/tic_game_space', 1> {d, no_rotation_relection_collapse}). {ok,tic_game_space} 2> tic_game_space:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Total number of game paths: 3584 Total number of boards: 884 Player 1 winning boards : 0 Player 2 winning boards : 0 Player 1 must respond to: 417 Player 2 must respond to: 451 Tie boards : 16 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 467 Boards produced by player 2: 416 ok 3> tic_game_space:report1( ply_overview). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Player 1 moves, leading to ply 1 9 boards (all continue to ties) Player 2 moves, leading to ply 2 24 boards (all continue to ties) Player 1 moves, leading to ply 3 102 boards (all continue to ties) Player 2 moves, leading to ply 4 136 boards (all continue to ties) Player 1 moves, leading to ply 5 176 boards (all continue to ties) Player 2 moves, leading to ply 6 180 boards (all continue to ties) Player 1 moves, leading to ply 7 164 boards (all continue to ties) Player 2 moves, leading to ply 8 76 boards (all continue to ties) Player 1 moves (last move) 16 tie boards ok

Here are the reports that treat rotated and reflected boards as equal. The boards in the first three plys are also listed. Notice there are only 336 games in the game space, down from 26,830 in the full game space.

Eshell V5.6.5 (abort with ^G) 1> c( 'c:/src/erlang/tic_game_space'). {ok,tic_game_space} 2> tic_game_space:report1( ). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Total number of game paths: 336 Total number of boards: 125 Player 1 winning boards : 0 Player 2 winning boards : 0 Player 1 must respond to: 58 Player 2 must respond to: 64 Tie boards : 3 Total number of boards can also be broken down as: Initial board count : 1 Boards produced by player 1: 67 Boards produced by player 2: 57 ok 3> tic_game_space:report1( ply_overview). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Player 1 moves, leading to ply 1 3 boards (all continue to ties) Player 2 moves, leading to ply 2 5 boards (all continue to ties) Player 1 moves, leading to ply 3 16 boards (all continue to ties) Player 2 moves, leading to ply 4 18 boards (all continue to ties) Player 1 moves, leading to ply 5 23 boards (all continue to ties) Player 2 moves, leading to ply 6 24 boards (all continue to ties) Player 1 moves, leading to ply 7 22 boards (all continue to ties) Player 2 moves, leading to ply 8 10 boards (all continue to ties) Player 1 moves (last move) 3 tie boards ok 4> tic_game_space:report1( 0). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Boards in ply 0 ... X.. .X. ... ... -> ... ... .X. ... ... ... ... ok 5> tic_game_space:report1( 1). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Boards in ply 1 X.. X.. ... -> .O. ... ... .X. OX. .X. .X. ... -> ... .O. ... ... ... ... .O. ... O.. .X. -> .X. ... ... ok 6> tic_game_space:report1( 2). Smart tic-tac-toe game space: Player 1: all smart moves Player 2: all smart moves Boards in ply 2 X.. XX. X.X X.. X.. .O. -> .O. .O. .OX .O. ... ... ... ... ..X OX. X.O X.. OX. OX. ... -> ..X ..X X.. .X. ... ... ..O ... ... O.. X.O X.. OX. O.. .X. -> .X. .X. .X. .XX ... ... ..O ... ... .X. XX. X.. .X. .O. -> .O. .OX XO. ... ... ... ... .X. XX. XO. .X. .X. ... -> ... ... X.O .X. .O. .O. .X. ... .O. ok

It’s interesting to see that the first player can start anywhere, but the 2nd player’s first move is constrained. If the first player starts in the middle, the 2nd player must play a corner to avoid losing. If the 1st player starts in the corner the 2nd player must respond by marking the middle. And if the first player starts on the side, the 2nd player must play a corner next to the first player’s mark, or play the middle, or play the side directly opposite.

The listing of the boards for ply 8 (which isn’t shown here) also includes one board where the middle is the one space not filled in. I didn’t expect to see this — I assumed the middle would always be marked after the first 3 or 4 ply. Even tic-tac-toe can hold surprises.

Hmmm, the Wikipedia entry for tic-tac-toe mentions some people also treat a Y-shaped arrangement of marks as a win. I wonder how that affects the game space?