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

Groups > comp.lang.c++ > #124419 > 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 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

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

#124532

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]

#124537

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]

#124546

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]

#124559

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]

#124568

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]

#124573

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]

#124579 — 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]

#124582

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]

#124536

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]

#124535

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]

#124525

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]

#124450

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]

#124451

Totally wrong. Try it with some code.

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

#124453

On 7/29/2026 3:28 PM, Bonita Montero wrote:

> Totally wrong. Try it with some code.

same results:


#include <stdio.h>
int main(void){
	printf("Possible wins = 8\n");
	printf("Possible draw/undecided = 76\n");
	return 0;
}

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

#124468

As no one here shows a solution I show mine in C++23:

#include <iostream>
#include <array>

using namespace std;

int main()
{
	constexpr int8_t Free = -3, White = 0, Black = 1;
	array<array<int8_t, 3>, 3> board;
	board.fill( { Free, Free, Free } );
	unsigned undecided = 0, wins = 0;
	auto recurse = [&]( this auto &self, int8_t colour ) noexcept -> void
	{
		bool full = true;
		for( size_t row = 3; row--; )
			for( size_t col = 3; col--; )
				if( int8_t &coin = board[row][col]; coin == Free )
				{
					full = false;
					coin = colour;
					int needed = colour ? 3 : 0;
					bool won = board[row][0] + board[row][1] + board[row][2] == needed
							|| board[0][col] + board[1][col] + board[2][col] == needed;
					if( int mid = board[1][1]; !won && (row == col || row + col == 2) )
						won = (board[0][0] + mid + board[2][2]) == needed
							|| (board[0][2] + mid + board[2][0]) == needed;
					if( !won )
						self( colour == White ? Black : White );
					else
						++wins;
					coin = Free;
				}
		undecided += full;
	};
	recurse( White );
	cout << "wins:      " << 2 * wins << endl;
	cout << "undecided: " << 2 * undecided << endl;
}

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

#124470

On 2026-07-30 17:09, Bonita Montero wrote:
> As no one here shows a solution I show mine in C++23:

> [snip code]

Since your code doesn't compile without errors with my g++ -std=c++23,
and especially since you said in your OP:  "Just show the results.",
mind to post the result that your code is supposed to produce? Thanks.

Janis

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

#124475

Am 30.07.2026 um 17:53 schrieb Janis Papanagnou:

> Since your code doesn't compile without errors with my g++ -std=c++23,
> and especially since you said in your OP:  "Just show the results.",
> mind to post the result that your code is supposed to produce? Thanks.

It compiles with current MSVC, g++-14 and clang++-20.

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

#124478

On 2026-07-30 21:59, Bonita Montero wrote:
> Am 30.07.2026 um 17:53 schrieb Janis Papanagnou:
> 
>> Since your code doesn't compile without errors with my g++ -std=c++23,
>> and especially since you said in your OP:  "Just show the results.",
>> mind to post the result that your code is supposed to produce? Thanks.
> 
> It compiles with current MSVC, g++-14 and clang++-20.

Maybe. (I'm no MS user, so that's quite meaningless for me.)[*]

What about the actual result I had been kindly asking you to provide.

Janis

[*] In case you intend to "fix" your code here's the error messages:

$ g++ -std=c++23 -o ttt_bm ttt_bm.cc 

ttt_bm.cc: In function ‘int main()’:
ttt_bm.cc:12:25: error: expected identifier before ‘this’
    12 |     auto recurse = [&]( this auto &self, int8_t colour ) 
noexcept -> void
       |                         ^~~~
ttt_bm.cc:12:25: error: expected ‘,’ or ‘...’ before ‘this’
ttt_bm.cc: In lambda function:
ttt_bm.cc:20:28: error: ‘colour’ was not declared in this scope
    20 |                     coin = colour;
       |                            ^~~~~~
ttt_bm.cc:28:25: error: ‘self’ was not declared in this scope
    28 |                         self( colour == White ? Black : White );
       |                         ^~~~

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

#124481

On Thu, 7/30/2026 5:00 PM, Janis Papanagnou wrote:
> On 2026-07-30 21:59, Bonita Montero wrote:
>> Am 30.07.2026 um 17:53 schrieb Janis Papanagnou:
>>
>>> Since your code doesn't compile without errors with my g++ -std=c++23,
>>> and especially since you said in your OP:  "Just show the results.",
>>> mind to post the result that your code is supposed to produce? Thanks.
>>
>> It compiles with current MSVC, g++-14 and clang++-20.
> 
> Maybe. (I'm no MS user, so that's quite meaningless for me.)[*]
> 
> What about the actual result I had been kindly asking you to provide.
> 
> Janis
> 
> [*] In case you intend to "fix" your code here's the error messages:
> 
> $ g++ -std=c++23 -o ttt_bm ttt_bm.cc
> ttt_bm.cc: In function ‘int main()’:
> ttt_bm.cc:12:25: error: expected identifier before ‘this’
>    12 |     auto recurse = [&]( this auto &self, int8_t colour ) noexcept -> void
>       |                         ^~~~
> ttt_bm.cc:12:25: error: expected ‘,’ or ‘...’ before ‘this’
> ttt_bm.cc: In lambda function:
> ttt_bm.cc:20:28: error: ‘colour’ was not declared in this scope
>    20 |                     coin = colour;
>       |                            ^~~~~~
> ttt_bm.cc:28:25: error: ‘self’ was not declared in this scope
>    28 |                         self( colour == White ? Black : White );
>       |                         ^~~~
> 

CoPilot gives me this.

"The errors all come from one root cause: C++23 does not support this auto &self inside a lambda.
 That syntax was proposed for “lambda recursion” but never made it into the standard.
 So g++ rejects it, and then all later errors are just fallout from the first one.
"

include <iostream>
#include <array>
#include <functional>

using namespace std;

int main()
{
    constexpr int8_t Free = -3, White = 0, Black = 1;
    array<array<int8_t, 3>, 3> board;
    board.fill( { Free, Free, Free } );
    unsigned undecided = 0, wins = 0;

    std:function<void(int8_t)> recurse;

    recurse = [&](int8_t colour)
    {
        bool full = true;
        for (size_t row = 3; row--; )
            for (size_t col = 3; col--; )
                if (int8_t &coin = board[row][col]; coin == Free)
                {
                    full = false;
                    coin = colour;

                    int needed = colour ? 3 : 0;
                    bool won = board[row][0] + board[row][1] + board[row][2] == needed
                            || board[0][col] + board[1][col] + board[2][col] == needed;

                    if (int mid = board[1][1]; !won && (row == col || row + col == 2))
                        won = (board[0][0] + mid + board[2][2]) == needed
                           || (board[0][2] + mid + board[2][0]) == needed;

                    if (!won)
                        recurse(colour == White ? Black : White);
                    else
                        ++wins;

                    coin = Free;
                }
        undecided += full;
    };

    recurse(White);

    cout << "wins:      " << 2 * wins << endl;
    cout << "undecided: " << 2 * undecided << endl;
}

bullwinkle@SKYLARK:~/Downloads$ g++ -std=c++23 -o ttt_bm ttt_bm.cc
bullwinkle@SKYLARK:~/Downloads$ ./ttt_bm
wins:      418176
undecided: 92160
bullwinkle@SKYLARK:~/Downloads$ g++ -v
...
gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04.1)

   Paul

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

#124515

Am 31.07.2026 um 00:56 schrieb Paul:

> CoPilot gives me this.
> 
> "The errors all come from one root cause: C++23 does not support this auto &self inside a lambda.
>   That syntax was proposed for “lambda recursion” but never made it into the standard.
>   So g++ rejects it, and then all later errors are just fallout from the first one.

I guess Copilot is wrong. Grok, Claude and GPT say it's part of the
standard. Maybe the initial compiler was too old. And it's not plausible
why this shouldn't have gone into the standard since it's simple and
useful.

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

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

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

csiph-web