Re: Tic Tac Toe Quest

From	Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups	comp.lang.c++, comp.lang.c
Subject	Re: Tic Tac Toe Quest
Date	2026-08-02 04:19 +0100
Organization	A noiseless patient Spider
Message-ID	<114md0v$5dle$1@dont-email.me> (permalink)
References	(2 earlier) <114crl1$rt8j$1@raubtier-asyl.eternal-september.org> <114hep7$203s$1@nnrp.usenet.blueworldhosting.com> <114iekl$2rh3k$1@dont-email.me> <114m5rl$iil$1@nnrp.usenet.blueworldhosting.com> <114maop$4q0u$1@dont-email.me>

Cross-posted to 2 groups.

Show all headers | View raw

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.
>

Thread

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 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 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 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-07-30 14:58 -0700
  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

csiph-web