Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #124546
| 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-03 01:54 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <114oosf$tv19$1@dont-email.me> (permalink) |
| References | (3 earlier) <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> <114obmd$11up$1@nnrp.usenet.blueworldhosting.com> |
Cross-posted to 2 groups.
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.
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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