Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #400519 > unrolled thread

Tic Tac Toe Quest

Back to article view | Back to comp.lang.c

Contents

  Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-29 14:10 +0200
    Re: Tic Tac Toe Quest Chris Ahlstrom <OFeem1987@teleworm.us> - 2026-07-29 08:14 -0400
      Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-29 14:28 +0200
        Re: Tic Tac Toe Quest Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-29 20:30 +0800
          Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-29 14:38 +0200
            Turbo Vision (was: Re: Tic Tac Toe Quest) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-29 20:46 +0800
              Re: Turbo Vision Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-29 14:57 +0200
                Re: Turbo Vision Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-29 21:14 +0800
                Re: Turbo Vision ... MS-DOS 5 Shell? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:42 +0800
                  Re: Turbo Vision ... MS-DOS 5 Shell? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-08-05 04:13 +0800
                    Re: Turbo Vision ... MS-DOS 5 Shell? usenet@dolik.dev (Andriy D) - 2026-08-05 11:38 +0000
                    Re: Turbo Vision ... MS-DOS 5 Shell? JJ <jj4public@gmail.com> - 2026-08-05 20:46 +0700
        Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-07-31 06:19 +0000
          Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-31 14:20 +0200
            Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-07-31 22:05 +0000
              Re: Tic Tac Toe Quest steve g <Sgonedes1977@gmail.com> - 2026-08-08 01:35 -0400
                Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-08-08 07:32 +0000
                  Re: Tic Tac Toe Quest steve g <Sgonedes1977@gmail.com> - 2026-08-09 19:18 -0400
          Re: Tic Tac Toe Quest James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-07-31 11:22 -0400
            Re: Tic Tac Toe Quest "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-07-31 20:00 -0700
            Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-08-02 01:17 +0000
              Re: Tic Tac Toe Quest Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-08-02 03:41 +0100
                Re: Tic Tac Toe Quest Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-08-02 04:19 +0100
                Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-08-02 21:09 +0000
                  Re: Tic Tac Toe Quest Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-08-03 01:54 +0100
                  Re: Tic Tac Toe Quest James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-08-03 17:25 -0400
                    Re: Tic Tac Toe Quest R Kym Horsell <kym@sdf.org> - 2026-08-03 22:00 +0000
                      Re: Tic Tac Toe Quest bart <bc@freeuk.com> - 2026-08-04 01:37 +0100
                        Re: Tic Tac Toe Quest bart <bc@freeuk.com> - 2026-08-04 01:58 +0100
                          Re: Tic Tac Toe Quest Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-08-04 03:16 +0100
                            Re: Tic Tac Toe Quest bart <bc@freeuk.com> - 2026-08-04 11:51 +0100
                        Re: Tic Tac Toe Quest Ike Naar <ike@sdf.org> - 2026-08-04 06:50 +0000
                          Re: Tic Tac Toe Quest antispam@fricas.org (Waldek Hebisch) - 2026-08-04 11:05 +0000
                      Re: Tic Tac Toe Quest James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-08-04 01:05 -0400
                        Re: Tic Tac Toe Quest ... End game? TikTok? :) "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-04 13:54 +0800
                        Re: Tic Tac Toe Quest "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-08-04 11:50 -0700
              Re: Tic Tac Toe Quest James Kuyper <jameskuyper@alumni.caltech.edu> - 2026-08-02 12:30 -0400
            Re: Tic Tac Toe Quest bart <bc@freeuk.com> - 2026-08-02 11:25 +0100
        Re: Tic Tac Toe Quest Chris Ahlstrom <OFeem1987@teleworm.us> - 2026-08-01 07:40 -0400
    Re: Tic Tac Toe Quest DFS <nospam@dfs.com> - 2026-07-29 15:04 -0400
      Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-29 21:28 +0200
        Re: Tic Tac Toe Quest DFS <nospam@dfs.com> - 2026-07-29 16:25 -0400
    Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-30 17:09 +0200
      Re: Tic Tac Toe Quest Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-07-30 17:53 +0200
        Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-30 21:59 +0200
          Re: Tic Tac Toe Quest Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-07-30 23:00 +0200
            Re: Tic Tac Toe Quest Paul <nospam@needed.invalid> - 2026-07-30 18:56 -0400
              Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-31 20:33 +0200
                Re: Tic Tac Toe Quest "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-07-31 19:53 -0700
            Re: Tic Tac Toe Quest Michael S <already5chosen@yahoo.com> - 2026-07-31 17:53 +0300
              Re: Tic Tac Toe Quest Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-07-31 18:17 +0200
                Re: Tic Tac Toe Quest Michael S <already5chosen@yahoo.com> - 2026-08-01 21:44 +0300
                  Re: Tic Tac Toe Quest Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-08-01 21:43 +0200
    Re: Tic Tac Toe Quest "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 00:45 +0800
      Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-30 22:00 +0200
        Re: Tic Tac Toe Quest "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 13:29 +0800
          Re: Tic Tac Toe Quest Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 14:54 +0800
            Re: Tic Tac Toe Quest Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-07-31 03:00 -0700
              Re: Tic Tac Toe Quest Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 20:57 +0800
              Re: Tic Tac Toe Quest gazelle@shell.xmission.com (Kenny McCormack) - 2026-07-31 14:08 +0000
        Re: Tic Tac Toe Quest ... Discrete mathematics? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 13:30 +0800
        Re: Tic Tac Toe Quest Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-07-31 07:31 +0000
          Re: Tic Tac Toe Quest Bonita Montero <Bonita.Montero@gmail.com> - 2026-07-31 14:21 +0200
            Re: Tic Tac Toe Quest Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-08-02 03:57 +0000
          Re: Tic Tac Toe Quest ... WarGames (1983) Movie CLIP - Tic Tac Toe With Joshua "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:24 +0800
        Re: Tic Tac Toe Quest "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:18 +0800
      Re: Tic Tac Toe Quest Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 04:17 +0800
        Re: Tic Tac Toe Quest ... game programming in C? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 13:27 +0800
          Re: Tic Tac Toe Quest ... game programming in C? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 14:56 +0800
            Re: Tic Tac Toe Quest ... game programming in C? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 19:43 +0800
              VAXen (was: Re: Tic Tac Toe Quest ... game programming in C?) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 20:56 +0800
                Re: VAXen The Natural Philosopher <tnp@invalid.invalid> - 2026-07-31 14:32 +0100
                  I Bought a $200K VAX on eBay & – Now It Runs My Smart Lights! - YouTube "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:20 +0800
                    Re: I Bought a $200K VAX on eBay & – Now It Runs My Smart Lights! - YouTube Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-07-31 22:53 +0800
                      Re: I Bought a $200K VAX on eBay & – Now It Runs My Smart Lights! - YouTube The Natural Philosopher <tnp@invalid.invalid> - 2026-07-31 16:00 +0100
                Re: Tic Tac Toe Quest ... VAXen? VMS? Pascal? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:14 +0800
                  Re: Tic Tac Toe Quest ... VAXen? VMS? Pascal? Spreadsheets! Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-08-05 04:17 +0800
                    Re: Tic Tac Toe Quest ... VAXen? VMS? Pascal? Spreadsheets! "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-05 07:43 -0700
    Re: Tic Tac Toe Quest... vibe-coding? Wargames (1983) the movie? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-07-31 22:43 +0800
    Tic-tac-toe (過三關? 井字棋?) - Wikipedia "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-02 17:19 +0800
      Re: Tic-tac-toe (???? ????) - Wikipedia Your Name <YourName@YourISP.com> - 2026-08-03 10:01 +1200
        Wing Commander III: Heart of the Tiger (was: Re: Tic-tac-toe (???? ????) - Wikipedia) Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-08-03 17:15 +0800
          Re: Wing Commander III ... and Mark Hamill? Star Wars? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-04 13:09 +0800
        Re: Tic-tac-toe ... balance to the Force? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-04 13:06 +0800
        Death Star bombing run mechanical toy? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-04 13:14 +0800
          Re: Death Star bombing run mechanical toy? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2026-08-04 13:49 +0800

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#400700

In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
> On 2026-07-31 02:19, R Kym Horsell wrote:
> ...> With no summetries and counting who start, the order of the squares
>> marked, and the final position as all befining "the game"
>> then there are a couple million possibilities.
> 
> There's only 9 different choices for the first mark, 8 for the second,
> etc. Ignoring the victory conditions, that means at most 9! = 362,880
> games, no matter how you distinguish them. If you stop a game as soon as
> one side wins, it's much smaller, I won't bother figuring out how many.

I think you missed a few.
Games can be shorted if there is a winner.  That adds more possibilities.

There are 2^9 possible ttt boards if the games goes to 9 moves.
But the number of possible boards not looking at symmetries
is more like  3^9  i.e. 38x more.

[toc] | [prev] | [next] | [standalone]

#400702

On 02/08/2026 02:17, R Kym Horsell wrote:
> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>> On 2026-07-31 02:19, R Kym Horsell wrote:
>> ...> With no summetries and counting who start, the order of the squares
>>> marked, and the final position as all befining "the game"
>>> then there are a couple million possibilities.
>>
>> There's only 9 different choices for the first mark, 8 for the second,
>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>> games, no matter how you distinguish them. If you stop a game as soon as
>> one side wins, it's much smaller, I won't bother figuring out how many.
> 
> I think you missed a few.

James' account looks correct to me.  9! is just an upper bound, as he notes.

> Games can be shorted if there is a winner.  That adds more possibilities.

If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces 
from 9!), not "adding more".

Lets represent a game by the sequence of cells (1 to 9) that are taken in succession.  If the rules 
said all games continue until the grid is full, then there would be exactly 9! games, e.g.
    [123456789]
    [174698523]
    [523416789]

To see the effect of games ending in fewer moves, imagine the rules declared the first person a 
winner if he takes cell 1, ending the game.  Then we could allow players to continue playing, while 
understanding that the game was won at move 1, just for fun! to see what might have happened in the 
remaining 8 moves.

So of the 3 "extended games" having the full 9 moves I listed above, the first two were both won on 
move 1.  In fact all extended games starting [1...] are just one "real" game as counted by our 
program, so instead of counting 9! extended games we would count only 9!-8! real games.
> 
> There are 2^9 possible ttt boards if the games goes to 9 moves.
> But the number of possible boards not looking at symmetries
> is more like  3^9  i.e. 38x more.
> 

No, you're overcounting!  Your 3^9 boards include the one where every cell has an x, but there is no 
legal game that results in that - players have to alternate in their play.

Mike.

[toc] | [prev] | [next] | [standalone]

#400703

On 02/08/2026 03:41, Mike Terry wrote:
> On 02/08/2026 02:17, R Kym Horsell wrote:
>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>> ...> With no summetries and counting who start, the order of the squares
>>>> marked, and the final position as all befining "the game"
>>>> then there are a couple million possibilities.
>>>
>>> There's only 9 different choices for the first mark, 8 for the second,
>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>> games, no matter how you distinguish them. If you stop a game as soon as
>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>
>> I think you missed a few.
> 
> James' account looks correct to me.  9! is just an upper bound, as he notes.
> 
>> Games can be shorted if there is a winner.  That adds more possibilities.
> 
> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces 
> from 9!), not "adding more".
> 
> Lets represent a game by the sequence of cells (1 to 9) that are taken in succession.  If the rules 
> said all games continue until the grid is full, then there would be exactly 9! games, e.g.
>     [123456789]
>     [174698523]
>     [523416789]
> 
> To see the effect of games ending in fewer moves, imagine the rules declared the first person a 
> winner if he takes cell 1, ending the game.  Then we could allow players to continue playing, while 
> understanding that the game was won at move 1, just for fun! to see what might have happened in the 
> remaining 8 moves.
> 
> So of the 3 "extended games" having the full 9 moves I listed above, the first two were both won on 
> move 1.  In fact all extended games starting [1...] are just one "real" game as counted by our 
> program, so instead of counting 9! extended games we would count only 9!-8! real games.
>>
>> There are 2^9 possible ttt boards if the games goes to 9 moves.
>> But the number of possible boards not looking at symmetries
>> is more like  3^9  i.e. 38x more.
>>
> 
> No, you're overcounting!  Your 3^9 boards include the one where every cell has an x, but there is no 
> legal game that results in that - players have to alternate in their play.

But also you're undercounting, because board-positions are not games - a given position could be 
reached by many different games, where the order of play is important...

> 
> Mike.
> 

[toc] | [prev] | [next] | [standalone]

#400715

In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
> On 02/08/2026 02:17, R Kym Horsell wrote:
>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>> ...> With no summetries and counting who start, the order of the squares
>>>> marked, and the final position as all befining "the game"
>>>> then there are a couple million possibilities.
>>>
>>> There's only 9 different choices for the first mark, 8 for the second,
>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>> games, no matter how you distinguish them. If you stop a game as soon as
>>> one side wins, it's much smaller, I won't bother figuring out how many.
>> 
>> I think you missed a few.
> 
> James' account looks correct to me.  9! is just an upper bound, as he notes.
> 
>> Games can be shorted if there is a winner.  That adds more possibilities.
> 
> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces 
> from 9!), not "adding more".

If you have have long games and also short games then
there are more than just the long games. Right?
As I said you might suspect the number of games might be close to
2^9 because each sq can be {x,0}. But it's more like 3^9 because
some game are short and empty squares are left. I.e. {0,1,_}.

But my suspicion there might be more than a million legal games
is certainly wrong.  More like a 1/4 million as someone pointed out
and less than 50k of them draws.

My old Prolog program had a severe problem with "marking off"
the solutions and allowed games to run past their proper stopping point.
I fixed that up and it now gets what I assume is a solution someone 
already posted.

I'm almost totally blind so confirming some of these things is a bit
of a chore for me nowadays. Sorry.

[toc] | [prev] | [next] | [standalone]

#400729

On 02/08/2026 22:09, R Kym Horsell wrote:
> In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>> ...> With no summetries and counting who start, the order of the squares
>>>>> marked, and the final position as all befining "the game"
>>>>> then there are a couple million possibilities.
>>>>
>>>> There's only 9 different choices for the first mark, 8 for the second,
>>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>>> games, no matter how you distinguish them. If you stop a game as soon as
>>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>>
>>> I think you missed a few.
>>
>> James' account looks correct to me.  9! is just an upper bound, as he notes.
>>
>>> Games can be shorted if there is a winner.  That adds more possibilities.
>>
>> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces
>> from 9!), not "adding more".
> 
> If you have have long games and also short games then
> there are more than just the long games. Right?

Well, yes, but maybe you're overlooking that ALL the longer play sequences that started with the 
short game are not valid games, and so must not be counted.  The figure of 9! previously counted all 
those long play sequences, so the total is /reduced/ from the upper bound of 9!.

> As I said you might suspect the number of games might be close to
> 2^9 because each sq can be {x,0}. But it's more like 3^9 because
> some game are short and empty squares are left. I.e. {0,1,_}.

You're trying to count total board positions, but those are not what was asked for.  The OP wanted 
possible /games/, where games consist of the sequence of moves made at each turn, not the final 
board possition.  E.g. the board position

   X X X
   O O _
   _ _ _

is a win for X, and there have been 5 moves, and I reckon there are 3!*2! = 12 possible ways that 
board position could have been reached in a valid game.  I.e. that single board position would need 
to be counted somehow as 12 games in the total.

Also, there is no valid game that reaches board position

   X X X
   _ _ _
   _ _ _

which is one of you 3^9 board positions.  So that board position needs to be counted as 0 in the 
game count, not 1.

It would certainly be possible to get a correct game count by working through board positions, but 
its fiddly because assuming you work through all 3^9 positions, you would need to:
a)  identify whether the position can legally occur in a valid game, as the
     final position.  I reckon the following conditions test this:
     - there is exactly one winning line
     - if X has the winning line, there is one more X than O on the board
       [because X went first, which is my working assumption]
     - if O has the winning line, the number of X's and O's on the board
       must match
     Ignore invalid positions!
b)  for each valid position, count the number of games (play
     sequences) that could lead to that position.  This is easy -
     if there are m X's and n Y's on the board, there are m!n! possible
     sequences in which they could have been played, so count m!n!
     games for this board possition.

Should give matching results with other methods.  [Well, I've assumed X plays first, because that's 
how I've always played, but the adjustment is obvious if either player may start...]

> 
> But my suspicion there might be more than a million legal games
> is certainly wrong.  More like a 1/4 million as someone pointed out
> and less than 50k of them draws.
> 
> My old Prolog program had a severe problem with "marking off"
> the solutions and allowed games to run past their proper stopping point.
> I fixed that up and it now gets what I assume is a solution someone
> already posted.
> 
> I'm almost totally blind so confirming some of these things is a bit
> of a chore for me nowadays. Sorry.

Sorry to hear that! (And certainly no need to apologise for anything...)

Mike.

[toc] | [prev] | [next] | [standalone]

#400779

On 2026-08-02 17:09, R Kym Horsell wrote:
> In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>> ...> With no summetries and counting who start, the order of the squares
>>>>> marked, and the final position as all befining "the game"
>>>>> then there are a couple million possibilities.
>>>>
>>>> There's only 9 different choices for the first mark, 8 for the second,
>>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>>> games, no matter how you distinguish them. If you stop a game as soon as
>>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>>
>>> I think you missed a few.
>>
>> James' account looks correct to me.  9! is just an upper bound, as he notes.
>>
>>> Games can be shorted if there is a winner.  That adds more possibilities.
>>
>> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces 
>> from 9!), not "adding more".
> 
> If you have have long games and also short games then
> there are more than just the long games. Right?

No, I specified stopping a game as soon as it is won. The moves of every
short game are a subset of multiple longer games. For instance,
(1,2,5,3,9) is a subset of (1,2,5,3,9,4,6,7), (1,2,5,3,9,6,7,4),
(1,2,5,3,9,7,4,6), (1,2,5,3,9,7,6,4), (1,2,5,3,9,4,7,6) and
(1,2,5,3,9,6,4,7). but those longer games shouldn't be included, only
the shorter one, so stopping as soon as a game is won reduces the number
of different games; it doesn't increase it.

> As I said you might suspect the number of games might be close to
> 2^9 because each sq can be {x,0}. But it's more like 3^9 because
> some game are short and empty squares are left. I.e. {0,1,_}.

I think it's inappropriate to consider games that reached the same final
position by a different sequence of moves to be the same game. That's
how you keep the count so low.

[toc] | [prev] | [next] | [standalone]

#400787

In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
> On 2026-08-02 17:09, R Kym Horsell wrote:
>> In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>>> ...> With no summetries and counting who start, the order of the squares
>>>>>> marked, and the final position as all befining "the game"
>>>>>> then there are a couple million possibilities.
>>>>>
>>>>> There's only 9 different choices for the first mark, 8 for the second,
>>>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>>>> games, no matter how you distinguish them. If you stop a game as soon as
>>>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>>>
>>>> I think you missed a few.
>>>
>>> James' account looks correct to me.  9! is just an upper bound, as he notes.
>>>
>>>> Games can be shorted if there is a winner.  That adds more possibilities.
>>>
>>> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces 
>>> from 9!), not "adding more".
>> 
>> If you have have long games and also short games then
>> there are more than just the long games. Right?
> 
> No, I specified stopping a game as soon as it is won. The moves of every
...

Maybe we are talking at cross-purposes.

I think you're alluding to "no legal game can be a prefix of another
legal game (although 2 legal games can share the prefix)".

IOW the total number of possible games is the sum  of the games of length
5, length 6, ... length 9.

I.e. the total is more than then number of games of length 9.

[toc] | [prev] | [next] | [standalone]

#400793

On 03/08/2026 23:00, R Kym Horsell wrote:
> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>> On 2026-08-02 17:09, R Kym Horsell wrote:
>>> In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>>>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>>>> ...> With no summetries and counting who start, the order of the squares
>>>>>>> marked, and the final position as all befining "the game"
>>>>>>> then there are a couple million possibilities.
>>>>>>
>>>>>> There's only 9 different choices for the first mark, 8 for the second,
>>>>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>>>>> games, no matter how you distinguish them. If you stop a game as soon as
>>>>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>>>>
>>>>> I think you missed a few.
>>>>
>>>> James' account looks correct to me.  9! is just an upper bound, as he notes.
>>>>
>>>>> Games can be shorted if there is a winner.  That adds more possibilities.
>>>>
>>>> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces
>>>> from 9!), not "adding more".
>>>
>>> If you have have long games and also short games then
>>> there are more than just the long games. Right?
>>
>> No, I specified stopping a game as soon as it is won. The moves of every
> ...
> 
> Maybe we are talking at cross-purposes.
> 
> I think you're alluding to "no legal game can be a prefix of another
> legal game (although 2 legal games can share the prefix)".
> 
> IOW the total number of possible games is the sum  of the games of length
> 5, length 6, ... length 9.
> 
> I.e. the total is more than then number of games of length 9.
> 

I've done a simulation. Figures may not be right, but they look plausible:

Total number of games:  362880      (Ignores who goes first)
Won by player 1:        212256
Won by player 2:        104544
Drawn:                   46080

Players make all possible permutations of moves in turn, with no 
strategy. Games last from 5 to 9 moves:

34560 games with 5 moves (all won)
31968 games with 6 moves
95904 games with 7 moves
72576 games with 8 moves
127872 games with 9 moves (46080 were drawn)

Drawn games always take 9 moves.

[toc] | [prev] | [next] | [standalone]

#400797

On 04/08/2026 01:37, bart wrote:
> On 03/08/2026 23:00, R Kym Horsell wrote:
>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>> On 2026-08-02 17:09, R Kym Horsell wrote:
>>>> In comp.lang.c Mike Terry 
>>>> <news.dead.person.stones@darjeeling.plus.com> wrote:
>>>>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>>>>> ...> With no summetries and counting who start, the order of the 
>>>>>>> squares
>>>>>>>> marked, and the final position as all befining "the game"
>>>>>>>> then there are a couple million possibilities.
>>>>>>>
>>>>>>> There's only 9 different choices for the first mark, 8 for the 
>>>>>>> second,
>>>>>>> etc. Ignoring the victory conditions, that means at most 9! = 
>>>>>>> 362,880
>>>>>>> games, no matter how you distinguish them. If you stop a game as 
>>>>>>> soon as
>>>>>>> one side wins, it's much smaller, I won't bother figuring out how 
>>>>>>> many.
>>>>>>
>>>>>> I think you missed a few.
>>>>>
>>>>> James' account looks correct to me.  9! is just an upper bound, as 
>>>>> he notes.
>>>>>
>>>>>> Games can be shorted if there is a winner.  That adds more 
>>>>>> possibilities.
>>>>>
>>>>> If a game ends with a winner in less than 9 moves, that /reduces/ 
>>>>> the possibilities (i.e. reduces
>>>>> from 9!), not "adding more".
>>>>
>>>> If you have have long games and also short games then
>>>> there are more than just the long games. Right?
>>>
>>> No, I specified stopping a game as soon as it is won. The moves of every
>> ...
>>
>> Maybe we are talking at cross-purposes.
>>
>> I think you're alluding to "no legal game can be a prefix of another
>> legal game (although 2 legal games can share the prefix)".
>>
>> IOW the total number of possible games is the sum  of the games of length
>> 5, length 6, ... length 9.
>>
>> I.e. the total is more than then number of games of length 9.
>>
> 
> I've done a simulation. Figures may not be right, but they look plausible:
> 
> Total number of games:  362880      (Ignores who goes first)
> Won by player 1:        212256
> Won by player 2:        104544
> Drawn:                   46080
> 
> Players make all possible permutations of moves in turn, with no 
> strategy. Games last from 5 to 9 moves:
> 
> 34560 games with 5 moves (all won)
> 31968 games with 6 moves
> 95904 games with 7 moves
> 72576 games with 8 moves
> 127872 games with 9 moves (46080 were drawn)
> 
> Drawn games always take 9 moves.

No, I think this includes duplicates. If a particular 9-move sequence is 
won after 6 moves say, then the remaining combinations that start with 
the same 6 need to be skipped otherwise they are counted again.

However the new figures seem too small! I'll have to look more closely.

[toc] | [prev] | [next] | [standalone]

#400800

On 04/08/2026 01:58, bart wrote:
> On 04/08/2026 01:37, bart wrote:
>> On 03/08/2026 23:00, R Kym Horsell wrote:
>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>> On 2026-08-02 17:09, R Kym Horsell wrote:
>>>>> In comp.lang.c Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>>>>>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>>>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>>>>>> ...> With no summetries and counting who start, the order of the squares
>>>>>>>>> marked, and the final position as all befining "the game"
>>>>>>>>> then there are a couple million possibilities.
>>>>>>>>
>>>>>>>> There's only 9 different choices for the first mark, 8 for the second,
>>>>>>>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>>>>>>>> games, no matter how you distinguish them. If you stop a game as soon as
>>>>>>>> one side wins, it's much smaller, I won't bother figuring out how many.
>>>>>>>
>>>>>>> I think you missed a few.
>>>>>>
>>>>>> James' account looks correct to me.  9! is just an upper bound, as he notes.
>>>>>>
>>>>>>> Games can be shorted if there is a winner.  That adds more possibilities.
>>>>>>
>>>>>> If a game ends with a winner in less than 9 moves, that /reduces/ the possibilities (i.e. reduces
>>>>>> from 9!), not "adding more".
>>>>>
>>>>> If you have have long games and also short games then
>>>>> there are more than just the long games. Right?
>>>>
>>>> No, I specified stopping a game as soon as it is won. The moves of every
>>> ...
>>>
>>> Maybe we are talking at cross-purposes.
>>>
>>> I think you're alluding to "no legal game can be a prefix of another
>>> legal game (although 2 legal games can share the prefix)".
>>>
>>> IOW the total number of possible games is the sum  of the games of length
>>> 5, length 6, ... length 9.
>>>
>>> I.e. the total is more than then number of games of length 9.
>>>
>>
>> I've done a simulation. Figures may not be right, but they look plausible:
>>
>> Total number of games:  362880      (Ignores who goes first)
>> Won by player 1:        212256
>> Won by player 2:        104544
>> Drawn:                   46080
>>
>> Players make all possible permutations of moves in turn, with no strategy. Games last from 5 to 9 
>> moves:
>>
>> 34560 games with 5 moves (all won)

So assuming X plays first, games of 5 moves would have 3 X's  in a line, and 2 O's (anywhere). 
There are 8 lines where X can win, and for each of these there are Choose(6,2) = 15 choices for 
cells O has taken.  Well that's counting final board positions, and each of those can occur in 
(3!)(2!) = 12

So that gives 8 * 15 = 120  5 move (game ended) board positions
               120 * 12 = 1440  5 move games.  (Not 34560)

But if we then "complete" the games by playing 4 further moves to fill the grid, there are 4! = 24 
ways to do this for each 5 move game, giving

               1440 * 24 = 34560   (your figure)

>> 31968 games with 6 moves
>> 95904 games with 7 moves
>> 72576 games with 8 moves
>> 127872 games with 9 moves (46080 were drawn)
>>
>> Drawn games always take 9 moves.
> 
> No, I think this includes duplicates. If a particular 9-move sequence is won after 6 moves say, then 
> the remaining combinations that start with the same 6 need to be skipped otherwise they are counted 
> again.

Right - your 5 game figure suggests that's exactly what's happened.  Probably the same for all the 
other counts, but I just looked at 5-move games because that's simple to calculate manually.

Hmm, when we add all your possibilities together that gives exactly 362880 = 9!  So the total of all 
games you counted was the full 9-move "completed game" count, supporting the idea that you made the 
same error in each case.  If so, we could manually "correct" your results by dividing each of them 
by their duplication factor.  [E.g. 6-move games have 3 cells unplayed, which can be filled in 3! = 
6 ways, so 6 is the duplication factor for these games.]

That would give:

   moves  'completed'-games  dup-factor   actual-game-count
   5        34560              4!=24        34560/24 =   1440
   6        31968              3!=6         31968/6  =   5328
   7        95904              2!=2         95904/2  =  47952
   8        72576              1!=1         72576/1  =  72576
   9       127872              0!=1        127872/1  = 127872
                                                       ------
   total                                               255168

That agrees with Chris Ahlstrom's previous reporting of what some AI said which is encouraging! :)

Mike.

[toc] | [prev] | [next] | [standalone]

#400813

On 04/08/2026 03:16, Mike Terry wrote:
> On 04/08/2026 01:58, bart wrote:
>> On 04/08/2026 01:37, bart wrote:
>>> On 03/08/2026 23:00, R Kym Horsell wrote:
>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>> On 2026-08-02 17:09, R Kym Horsell wrote:
>>>>>> In comp.lang.c Mike Terry 
>>>>>> <news.dead.person.stones@darjeeling.plus.com> wrote:
>>>>>>> On 02/08/2026 02:17, R Kym Horsell wrote:
>>>>>>>> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>>>>>>>>> On 2026-07-31 02:19, R Kym Horsell wrote:
>>>>>>>>> ...> With no summetries and counting who start, the order of 
>>>>>>>>> the squares
>>>>>>>>>> marked, and the final position as all befining "the game"
>>>>>>>>>> then there are a couple million possibilities.
>>>>>>>>>
>>>>>>>>> There's only 9 different choices for the first mark, 8 for the 
>>>>>>>>> second,
>>>>>>>>> etc. Ignoring the victory conditions, that means at most 9! = 
>>>>>>>>> 362,880
>>>>>>>>> games, no matter how you distinguish them. If you stop a game 
>>>>>>>>> as soon as
>>>>>>>>> one side wins, it's much smaller, I won't bother figuring out 
>>>>>>>>> how many.
>>>>>>>>
>>>>>>>> I think you missed a few.
>>>>>>>
>>>>>>> James' account looks correct to me.  9! is just an upper bound, 
>>>>>>> as he notes.
>>>>>>>
>>>>>>>> Games can be shorted if there is a winner.  That adds more 
>>>>>>>> possibilities.
>>>>>>>
>>>>>>> If a game ends with a winner in less than 9 moves, that /reduces/ 
>>>>>>> the possibilities (i.e. reduces
>>>>>>> from 9!), not "adding more".
>>>>>>
>>>>>> If you have have long games and also short games then
>>>>>> there are more than just the long games. Right?
>>>>>
>>>>> No, I specified stopping a game as soon as it is won. The moves of 
>>>>> every
>>>> ...
>>>>
>>>> Maybe we are talking at cross-purposes.
>>>>
>>>> I think you're alluding to "no legal game can be a prefix of another
>>>> legal game (although 2 legal games can share the prefix)".
>>>>
>>>> IOW the total number of possible games is the sum  of the games of 
>>>> length
>>>> 5, length 6, ... length 9.
>>>>
>>>> I.e. the total is more than then number of games of length 9.
>>>>
>>>
>>> I've done a simulation. Figures may not be right, but they look 
>>> plausible:
>>>
>>> Total number of games:  362880      (Ignores who goes first)
>>> Won by player 1:        212256
>>> Won by player 2:        104544
>>> Drawn:                   46080
>>>
>>> Players make all possible permutations of moves in turn, with no 
>>> strategy. Games last from 5 to 9 moves:
>>>
>>> 34560 games with 5 moves (all won)
> 
> So assuming X plays first, games of 5 moves would have 3 X's  in a line, 
> and 2 O's (anywhere). There are 8 lines where X can win, and for each of 
> these there are Choose(6,2) = 15 choices for cells O has taken.  Well 
> that's counting final board positions, and each of those can occur in 
> (3!)(2!) = 12
> 
> So that gives 8 * 15 = 120  5 move (game ended) board positions
>                120 * 12 = 1440  5 move games.  (Not 34560)
> 
> But if we then "complete" the games by playing 4 further moves to fill 
> the grid, there are 4! = 24 ways to do this for each 5 move game, giving
> 
>                1440 * 24 = 34560   (your figure)
> 
>>> 31968 games with 6 moves
>>> 95904 games with 7 moves
>>> 72576 games with 8 moves
>>> 127872 games with 9 moves (46080 were drawn)
>>>
>>> Drawn games always take 9 moves.
>>
>> No, I think this includes duplicates. If a particular 9-move sequence 
>> is won after 6 moves say, then the remaining combinations that start 
>> with the same 6 need to be skipped otherwise they are counted again.
> 
> Right - your 5 game figure suggests that's exactly what's happened.  
> Probably the same for all the other counts, but I just looked at 5-move 
> games because that's simple to calculate manually.
> 
> Hmm, when we add all your possibilities together that gives exactly 
> 362880 = 9!  So the total of all games you counted was the full 9-move 
> "completed game" count, supporting the idea that you made the same error 
> in each case.  If so, we could manually "correct" your results by 
> dividing each of them by their duplication factor.  [E.g. 6-move games 
> have 3 cells unplayed, which can be filled in 3! = 6 ways, so 6 is the 
> duplication factor for these games.]
> 
> That would give:
> 
>    moves  'completed'-games  dup-factor   actual-game-count
>    5        34560              4!=24        34560/24 =   1440
>    6        31968              3!=6         31968/6  =   5328
>    7        95904              2!=2         95904/2  =  47952
>    8        72576              1!=1         72576/1  =  72576
>    9       127872              0!=1        127872/1  = 127872
>                                                        ------
>    total                                               255168
> 
> That agrees with Chris Ahlstrom's previous reporting of what some AI 
> said which is encouraging! :)

OK, that's a much easier way of working it out! I was using a 
dict/hashtable to record and count only unique sets of moves.

I'm getting that 1440 figure now but the 6/7/8 ones are slightly higher 
(and they add up to 362880 still) Maybe I'll look at it some more, but 
now we have answers anyway.

[toc] | [prev] | [next] | [standalone]

#400810

On 2026-08-04, bart <bc@freeuk.com> wrote:
> Drawn games always take 9 moves.

Here is a drawn game that took 8 moves:

  OXX
  X_O
  OOX

[toc] | [prev] | [next] | [standalone]

#400814

Ike Naar <ike@sdf.org> wrote:
> On 2026-08-04, bart <bc@freeuk.com> wrote:
>> Drawn games always take 9 moves.
> 
> Here is a drawn game that took 8 moves:
> 
>   OXX
>   X_O
>   OOX

No, if the player refuses to move, than it is walk-over.  Note
that if both players move with reasonable competence, then the
play is always a draw.  But this fact does not allow you declare
a draw before any move.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#400803

On 2026-08-03 18:00, R Kym Horsell wrote:
...> I think you're alluding to "no legal game can be a prefix of another
> legal game (although 2 legal games can share the prefix)".
> 
> IOW the total number of possible games is the sum  of the games of length
> 5, length 6, ... length 9.
> 
> I.e. the total is more than then number of games of length 9.
It's simpler than that. Every legal game ends as soon as there are three
of one symbol in a row, column, or diagonal. The game cannot continue
past that point.

[toc] | [prev] | [next] | [standalone]

#400808 — Re: Tic Tac Toe Quest ... End game? TikTok? :)

On 8/4/2026 1:05 PM, James Kuyper wrote:

>
> It's simpler than that. Every legal game ends as soon as there are three
> of one symbol in a row, column, or diagonal. The game cannot continue
> past that point.


No, you can flip the game board and
star Kung Fu MMA, film the whole
fight and upload it to TikTok or
YouTube. :)


-- 

    @~@   Simplicity is Beauty! Remain silent! Drink, Blink, Stretch!
   / v \  May the Force and farces be with you! Live long and prosper!!
  /( _ )\ https://sites.google.com/site/changmw/
    ^ ^   https://github.com/changmw/changmw
          The game is afoot... Meow...

[toc] | [prev] | [next] | [standalone]

#400826

On 8/3/2026 10:05 PM, James Kuyper wrote:
> On 2026-08-03 18:00, R Kym Horsell wrote:
> ...> I think you're alluding to "no legal game can be a prefix of another
>> legal game (although 2 legal games can share the prefix)".
>>
>> IOW the total number of possible games is the sum  of the games of length
>> 5, length 6, ... length 9.
>>
>> I.e. the total is more than then number of games of length 9.
> It's simpler than that. Every legal game ends as soon as there are three
> of one symbol in a row, column, or diagonal. The game cannot continue
> past that point.

Right! To play after that is, well, wrong to me.

[toc] | [prev] | [next] | [standalone]

#400709

On 2026-08-01 21:17, R Kym Horsell wrote:
> In comp.lang.c James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
>> On 2026-07-31 02:19, R Kym Horsell wrote:
>> ...> With no summetries and counting who start, the order of the squares
>>> marked, and the final position as all befining "the game"
>>> then there are a couple million possibilities.
>>
>> There's only 9 different choices for the first mark, 8 for the second,
>> etc. Ignoring the victory conditions, that means at most 9! = 362,880
>> games, no matter how you distinguish them. If you stop a game as soon as
>> one side wins, it's much smaller, I won't bother figuring out how many.
> 
> I think you missed a few.
> Games can be shorted if there is a winner.  That adds more possibilities.

No, every short game is the beginning part of a 9-move game. therefore,
9! is an overcount, not an undercount. If you win a game in 5 moves, the
shortest possible, there's still 4 unmarked boxes. If we ignore that
it's a victory and continue playing, that's 4 choices for the next box,
3 choices for the following one, 2 for the one after that, and the last
move is forced. That means there's 4*3*2*1 = 12 different unstopped game
for that one game that stops as soon as victory is reached.
> There are 2^9 possible ttt boards if the games goes to 9 moves.

If you count games only by the ending position, and not by the order in
which the squares were marked, and continue playing after victory until
all boxes are marked, then  2^9 is the correct figure. To me, the order

> But the number of possible boards not looking at symmetries
> is more like  3^9  i.e. 38x more.

I would guess you get the 3 by considering, X, O, and unmarked? If so,
you're counting incomplete games in that 3^9. In completed games there
must always be at least 5 marked boxes. Also, in legal games, the number
of Xs minus the number of O's can only have the values -1, 0, or 1. Your
count includes games that violate that rule. Therefore, if you ignore
the order in which the squares are marked, the count is a lot less than 3^9.
If you take count games as equivalent if they can be rotated and/or
mirrored to match each other, and always start with an X, the number of
distinct games is MUCH smaller.

[toc] | [prev] | [next] | [standalone]

#400707

On 31/07/2026 16:22, James Kuyper wrote:
> On 2026-07-31 02:19, R Kym Horsell wrote:
> ...> With no summetries and counting who start, the order of the squares
>> marked, and the final position as all befining "the game"
>> then there are a couple million possibilities.
> 
> There's only 9 different choices for the first mark, 8 for the second,
> etc. Ignoring the victory conditions, that means at most 9! = 362,880
> games, no matter how you distinguish them. If you stop a game as soon as
> one side wins, it's much smaller, I won't bother figuring out how many.

There may be twice as many depending on whether X or O goes first.

If the board has only two adjacent cells, these are all the possible games:

--       empty board
X-       X goes first
XO       Then O

--
-X
OX

--
O-
OX

--
-O
XO

Here each game always has two moves (and nobody can win). But there are 
2x2! distinct games, not 2! (More if you allow 90-degree rotations.)

If you don't care who goes first (say the first player is always A, the 
second B), then it will be 2 games. And taking out reflections (same as 
180-degree rotations), then it will be only one game,

[toc] | [prev] | [next] | [standalone]

#400692

Bonita Montero wrote this screed in ALL-CAPS (fixed):

> Am 29.07.2026 um 14:14 schrieb Chris Ahlstrom:
>
>> "Yes, tic-tac-toe is a strongly solved game that always ends
>> in a forced draw when both players use optimal strategy."
>
>> I.e. You're beating a dead horse.
>
> Then show me the results, i.e. the number of possible
> wins and the number of possible undecided games.

AI Overview

    There are 255,168 possible valid games of standard
    tic-tac-toe, 19,683 total board positions, and 765 essentially
    different board states.

    Total Game Sequences

    255,168 total playable games: This counts every unique sequence of moves
    from start to finish, stopping as soon as a player wins or the
    board fills up.

    131,184 wins for X (the first player)

    77,904 wins for O (the second player)

    46,080 draws (cats' games

Now back to coding my MIDI program.

-- 
It usually takes more than three weeks to prepare a good impromptu speech.
		-- Mark Twain

[toc] | [prev] | [next] | [standalone]

#400556

On 7/29/2026 8:10 AM, Bonita Montero wrote:

> Write a program that calculates the number of possible ways to
> win a Tic Tac Toe round and the number of possible undecided
> rounds. Don't show the code here immediately but after some
> days. Just show the results.
> C and C++ are allowed since the solution will be very similar.

Possible wins = 8

Possible draw/undecided = 76


reasoning below, no code shown

















































Possible wins = 3 pieces in a row = 3 columns + 3 rows + 2 diagonals = 8

Draw/Undecided = 3 items placed in any of 9 positions (less 8 winning 
positions) =

9 choose 3

n! / (n - r)!r!

9! / (9 - 3)!3!

362880 / (720 * 6) =  84

84 - 8 = 76

I had to look up the formula for 9 choose 3.

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web