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 ):

Sequences from list_close_sum_na_over_bn_numerator_for_b( N ):

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:

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 Os 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:

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?

Next Page →