All tsumetmg are Black to play and either kill or live. The sequence of moves is given in the lower left and may be different per problem. If I have made an error in construction, please tell me so I can fix it.
3 Likes
To clarify, there is no ko rule in any of these problems, and there are no non-local threats to manipulate the move sequence.
EDIT:
Anyone want to arrange a live game? I have a new turn-tracking method I want to try. I’m fine with any time settings as long as it’s no faster than 10 sec. blitz and no slower than 3hours + 6x 60sec byo-yomi.
Maybe this is common knowledge or it has been mentioned before (I don’t know because honestly I did not read this entire thread)
Eiter case here is a rather easy way to determine who’se turn it is. Say it is move no. 73. Substract one and convert to a binary number. In this case the result is 72 = 64 + 8 ~= 1001000
Now take the sum of digits. If the result is divisible by 2, then it is B to move. Otherwise it is W to move. Therefore it is Black to move in the example.
Proof: Left as exercise for the reader.
4 Likes
Yep, though only if you don’t count passes. I’m not sure how to figure it with a simple formula from the OGS move number, unfortunately.
The following algorithm is designed to turn any given move number n into “b”, “w” or “pass”, indicating which move should be played next.
I have tested this algorithm with Matlab and believe it works. Here is the pseudo code:
function Thue-Morse(n)
bin_ind = 0;
while (n > 1) do
let a be the minimal natural number such that n is smaller or equal to (4^(a + 1) - 1) / 3
(easy to compute, but I’m lazy and this is more understandable than some formula with logarithms)
alpha = (4^a - 1) / 3;
if (n > 3 * alpha + 1) then {m = 3; i = 1}
elseif (n > 2 * alpha + 1) then {m = 2; i = 1}
elseif (n = 2 * alpha + 1) then {return “pass”}
elseif (n > alpha) then {m = 1; i = 0}
else {m = 0; i = 0}
endif
n = n - i - m * alpha;
bin_ind = bin_ind + i + m;
end while
if (bin_ind is even) then {return “b”}
else {return “w”}
end
I apologize for posting this without any kind of explanation.
1 Like
11, 17, 25, and Thue-Morse Go: a Proposal
The Thue-Morse Go equivalents of the three ubiquitous orthogo board sizes are 11x11, 17x17, and 25x25. Other cases could be made, I think, but here’s the reasoning whereby I reached this conclusion today at work.
In orthogo each move consists of an average of one placement (passes count as placements), and so the board fills up at an average rate of one point per move. In TMG, however, the average number of placements per move is somewhat higher, and the board fills up at this higher rate per move. Thus for a TMG game to take a similar number of turns to complete to a game of orthogo played on a given sized board, we might expect to need a board that was scaled by roughly that factor.
And so we get by the following reasoning number to scale the size by…
A Non-Mathematician Stumbling Through the TM Sequence
Let Tn and/or T(n) where n is a Natural Number be the sequence consisting of the first 2^n elements in the TM Sequence.
Let Tn.head be the first element of Tn.
Let Tn.tail be the last element of Tn.
Let Tn… and/or T(n)… be the infinite sequence generated by looping through Tn indefinitely.
T0: 0
T1: 01
T2: 0110
T3: 01101001
T4: 0110100110010110
T5: 01101001100101101001011001101001
T0.head = T0.tail
T1.head != T1.tail
Tn.head = Tm.head for all m, n, taken from the Natural Numbers
We already know that for any Tn, T(n+1) can be generated by repeating Tn and then appending the bitwise NOT’d Tn to it. So Tn.tail != T(n-1).tail.
So Tn… where n is an even natural number will always have Tn.head = Tn.tail, and Tn where n is an odd Natural Number will always have Tn.head != Tn.tail.
So we can figure the ratio of double moves to pairs of single moves by calculating it for Tn as n approaches positive infinity.
Seq: ratio, hex
T0…: 0:0, und.
T1…: 0:1, 0.0
T2…: 1:0, 1.0
T3…: 1:1, 0.8
T4…: 3:1, 0.c
T5…: 5:3, 0.a
T6…: 11:5, 0.b
T7…: 21:11, 0.a8
T8…: 43:21, 0.ac
Which works out to about 2/3, a good enough estimate for our purposes, though I’d love it if anyone could figure out more precisely what it’s approaching.
A 9x9 board is perhaps the smallest size on which one can have a reasonable game, perhaps 13x13 is the smallest size which feels mostly like regular go, and perhaps 19x19 is the smallest size wherefore influence is viable (or almost is, according to modern AI). The fact that 17x17 go was eventually almost completely displaced by the three modern board sizes is, I think, an indication that there was something more desirable about those other board sizes which caused them to become preferred, as otherwise one would have expected historical precedent and inertia to maintain the 17x17 board.
Or it may well be historical accident with no rhyme or reason explaining the board sizes which now dominate orthogo, but I am inclined to think not, and thus think it of value to translate those three board sizes which have weathered the test of time, to rough TMG equivalents.
9x9 has 81 points. 81 + 54 = 135. A 12x12 board would of course be closest to this target, but the closest odd board would be the 11x11 board: a board for teaching TMG and playing games of TMG hinging on precise and early reading.
13x13 has 169 points. 169 + ~113 = 282. A 17x17 board is remarkably close with 289 points: a board for playing quick games of TMG or transitioning to 25x25 TMG.
19x19 has 361 points. 361 + ~241 = 602. A 25x25 board overshoots a bit, but not by too much considering its 625 points: a board for experiencing the full range of depth hidden in TMG.
So it is by this reasoning that I came to 11x11, 17x17, and 25x25 as three especially attractive board sizes for TMG. If anyone would like to challenge me to a live game of TMG on any of these sizes, or a correspondence game (or live game(s)) on 11x11, I would love to play.
1 Like
Slight immediate objection to your theory in which I haven’t put much thought at all:
Isn’t the feel of a board size partially related to the ease of creating a new living group? In 9x9 it’s hard to keep three groups alive, but on 19x19 it’s often not so difficult to keep 7 floating around alive (not a good strategy, but still). Although TMG has double moves, I don’t think that the difference between the amount of space needed for a living group between TMG and Orthogo is 2/3, but significantly closer to 1, therefore lowering your estimates a bit.
1 Like
Yeah, the base assumption is quite naive; it was the first reasonable assumption I could quantify. Do you have any more specific numbers than “significantly closer to 1 [than 5/3]”? I would be interested in the board sizes that get recommended then.
It was also inspired by the similarly naive estimation used in the ongoing Diplomatic Go game to estimate the “crowdedness” of a given board size for a given number of players.
"6 groups may live, but 7 will die."
- Go Proverb
1 Like
In David Mitchell’s Go Proverbs (1980) is written:
If you have six groups one is dead.
Proverbial inflation?
2 Likes
Practical Calculation of Present Turn from OGS’s Turn Number
Take one less than the OGS move number, multiply by 7/9, and round to the nearest whole number. That gives the 0-indexed TM Placement number, from which you can check parity or consult your turn tracker to determine who is to play next.
In practice one should do the multiplication in nonary or hex for simplicity’s sake. Just learn the 7/9ths times table with inputs in decimal and outputs in hex, or the 7s times table with inputs in decimal and outputs in nonary and convert to hex.
This is derived by taking 2/3 as the average number of placement pairs which are double moves, which is at least close to the actual value, whatever that is, and multiplying that by the 1/3 of placements in those double moves which are passes, to get 2/9: the fraction of placements which are passes. Subtract from one to get three magic number 7/9: the fraction of placements which are stones.
I intuit that if the fraction of move pairs which are double moves does indeed approach precisely 2/3, then this algorithm will continue to work indefinitely. If, however, 2/3 is not quite the precise value being approached, I rather intuit that the algorithm will fail eventually, probably around 128 or 256 placements, and fall apart from there. I have tested it for the first 8 stone placements and it works, so here’s hoping until we can test it more exhaustively.
I am confused by this, but since I’ve put some thought into this as well, I’ll try to contribute.
The Thue-Morse sequence with added passes can be constructed by taking the sequence
S = B
and repeatedly arrange the resulting sequence in the pattern S S’ P S’ S, where S’ is the sequence S where every B is replaced by W and vice versa. So the next would be
B W P W B
then
B W P W B W B P B W P W B P B W B W P W B
and so on. Every step, the length of the sequence is multiplied by four and one is added. Thus the length after n steps is (1 + 4 + 4^2 + … + 4^n) = (4^(n+1) - 1) / 3
Analogously, the number of passes is also multiplied by four and one is added, however it’s different at the start. So after n steps, the number of passes is (4^n - 1) / 3
Note that (4^(n+1) - 1) / 3 = 4 * (4^n - 1) / 3 + 1 and thus the ratio of passes in the case of this subsequence is
{(4^n - 1) / 3 } / {4 * (4^n - 1) / 3 + 1} which goes towards 1/4 as n goes to infinity.
1 Like
I’ll need to wait until I get home and have pencil and paper to look more closely at that. Multiplying by 0.c (x) will certainly be more facile than 7/9, so part of me hopes you’re correct. The other part of me has fallen in love with the three board sizes I proposed earlier and doesn’t want to have to reconsider them. ;D
I still don’t understand your reasoning, but I found my error; thanks for drawing my attention to it. I’m now getting 0.3 (z) of the moves being passes, same as you. And I don’t need to change my board size suggestions because those weren’t in error, just the number of passes.
Now to test if we can just multiply one less than the OGS Move Number by 0.c (x) outputting in hex and rounding to the nearest whole number (8s round up), and get accurate results ad infinitum. I’m banking on yes, but that might be wishful thinking.
My table (may have minor mistakes):
The “passes” column is the error I was initially making; “passes 2” is the correct formula.
Common Sequences in TMG
I think it might be profitable for study to look at some stone placement sequences which are likely to occur multiple times in the sequence so that we can be aware of them.
The initial is the first element where they appear. The period is how often they are guaranteed to repeat. The incidence where p is the period is 1/(p^1) + 1/(p^2) + 1/(p^3).... The recurrence where i is the incidence is 1/i. The coverage where i is the incidence and l is the length of the sequence is l*i.
The incidence is meant to represent a value which, if you multiply it by a number n, represents how many times the sequence should be expected to begin within the first n digits of the TM Sequence.
The recurrence is meant to represent the average distance between successive germinations of the sequence as the digits of the TM Sequence tested go to infinity.
The coverage is meant to represent the chance that any given move is part of the sequence. This one behaves a bit weirdly since it often counts overlapping sequences, but I think it’s still serving it’s purpose to give a sense of how important familiarity with the given sequence is, perhaps even better than if it didn’t count overlaps.
If any of these stats don’t represent what I think they represent, I would appreciate the info.
Until I find a way to calculate recurrence I have left the field blank. The parenthesized elements are purely informational and depict elements that are guaranteed to follow after every occurrence of the given sequence. All the stats ignore these parentheticals. All numbers below are in hexadecimal.
Length 1 Sequences
- A
- Initial: 0
- Period: 1
- Incidence: und.
- Recurrence: und.
- Coverage: und.
Length 2 Sequences
- AA (B)
- Initial: 1
- Period: 4
- Incidence: 0.55…
- Recurrence: ???
- Coverage: 0.aa…
- AB
- Initial: 0
- Period: 2
- Incidence: 1
- Recurrence: 1
- Coverage: 2
Length 3 Sequences
- AAB
- Initial: 1
- Period: 4
- Incidence: 0.55…
- Recurrence: ???
- Coverage: 1
- ABA
- Initial: 2
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.6db6db…
- ABB (A)
- Initial: 0
- Period: 4
- Incidence: 0.55…
- Recurrence: ???
- Coverage: 1
Length 4 Sequences
- AABA (BBA)
- Initial: 1
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.6db6db…
- AABB (A)
- Initial: 5
- Period: 10
- Incidence: 0.11…
- Recurrence: ???
- Coverage: 0.44…
- ABAA (B)
- Initial: 4
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.924924…
- ABAB (BA)
- Initial: 2
- Period: 10
- Incidence: 0.11…
- Recurrence: ???
- Coverage: 0.44…
- ABBA
- Initial: 0
- Period: 4
- Incidence: 0.55…
- Recurrence: ???
- Coverage: 1.55…
Length 5 Sequences
- AABAB (BA)
- Initial: 1
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.b6db6d…
- AABBA
- Initial: 5
- Period: 10
- Incidence: 0.11…
- Recurrence: ???
- Coverage: 0.55…
- ABAAB
- Initial: 4
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.b6db6d…
- ABABB (A)
- Initial: 2
- Period: 8
- Incidence: 0.249249…
- Recurrence: ???
- Coverage: 0.b6db6d…
2 Likes
Who’s interested in another TMG tourney?
Interest
@kingkaio mentioned interest in another one of these, and I’ve been trying to get some TMG games going lately, so let’s see if others are thinking along the same lines. 
- 0 - No Interest
- 1 - Mild Interest, but Probably Won’t Play
- 2 - May or may not Play
- 3 - Sounds Interesting, I’ll Probably Play
- 4 - Count Me In!
0 voters
Time Settings
The settings shown are chosen to give 3 different game speeds with a roughly equivalent Fischer and Byo-yomi version. The middle settings (Fischer 30 + 15s/move and Byo-yomi 60m+3x30s) will be estimated to take around 2h total, or a bit more if players go into late endgame. If you’re interested in something closer to 10s blitz, check “Something Faster” (in addition to anything else you’d be good with), and be sure to mention your preference in a post below.
- Fischer 20m + 10s/move
- Fischer 30m + 15s/move
- Fischer 40m + 20s/move
- Byo-yomi 40m + 3x20s
- Byo-yomi 60m + 3x30s
- Byo-yomi 1h20m + 3x40s
- Something Faster
- Something Slower
0 voters
Structure
- Round-Robin
- Swiss
- Single Elimination
- Double Elimination
- Other
0 voters
Don’t mind me, I’m just here for the polls. And to state that I keep reading Thue-Morse as “Thuesday to Morseday”.
3 Likes
Common Sequences in TMG
I finished the last two length 5 sequences and added the missing recurrences. It was trivial once I (if I didn’t make a mistake) proved that the recurrence was always equal to the period minus one.
Let p, i, r be the period, incidence, and recurrence respectively.
Let r = 1/i and i = 1/p + 1/(p^2) + 1/(p^3).... These are the definitions as given in post 195.
i = 1/r from r = 1/i.
1/r = 1/p + 1/(p^2) + 1/(p^3)... from i = 1/r and i = 1/p + 1/(p^2) + 1/(p^3)....
The expression 1/p + 1/(p^2) + 1/(p^3)... can be expressed as 0.11... in base p.
In base p we can convert the infinitely repeating mantissa 0.11... into a ratio: 1/(p-1)
1/r = 1/(p-1) from 1/r = 1/p + 1/(p^2) + 1/(p^3)... and 1/p + 1/(p^2) + 1/(p^3)... = 1/(p-1).
r = p-1 from 1/r = 1/(p-1).
Reminder that all numbers are in hex.
Mostly a Repost of Above
Length 1 Sequences
- A
- Initial: 0
- Period: 1
- Incidence: und.
- Recurrence: und.
- Coverage: und.
Length 2 Sequences
- AA (B)
- Initial: 1
- Period: 4
- Incidence: 0.55…
- Recurrence: 3
- Coverage: 0.aa…
- AB
- Initial: 0
- Period: 2
- Incidence: 1
- Recurrence: 1
- Coverage: 2
Length 3 Sequences
- AAB
- Initial: 1
- Period: 4
- Incidence: 0.55…
- Recurrence: 3
- Coverage: 1
- ABA
- Initial: 2
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.6db6db…
- ABB (A)
- Initial: 0
- Period: 4
- Incidence: 0.55…
- Recurrence: 3
- Coverage: 1
Length 4 Sequences
- AABA (BBA)
- Initial: 1
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.6db6db…
- AABB (A)
- Initial: 5
- Period: 10
- Incidence: 0.11…
- Recurrence: f
- Coverage: 0.44…
- ABAA (B)
- Initial: 4
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.924924…
- ABAB (BA)
- Initial: 2
- Period: 10
- Incidence: 0.11…
- Recurrence: f
- Coverage: 0.44…
- ABBA
- Initial: 0
- Period: 4
- Incidence: 0.55…
- Recurrence: 3
- Coverage: 1.55…
Length 5 Sequences
- AABAB (BA)
- Initial: 1
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.b6db6d…
- AABBA
- Initial: 5
- Period: 10
- Incidence: 0.11…
- Recurrence: f
- Coverage: 0.55…
- ABAAB
- Initial: 4
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.b6db6d…
- ABABB (A)
- Initial: 2
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.b6db6d…
- ABBAA (B)
- Initial: 6
- Period: 10
- Incidence: 0.11…
- Recurrence: f
- Coverage: 0.55…
- ABBAB (AA)
- Initial: 0
- Period: 8
- Incidence: 0.249249…
- Recurrence: 7
- Coverage: 0.b6db6d…
In some of my posts above, I discussed how the Thue-Morse turn order does not necessarily make all games perfectly fair, or even fairer. The examples used above were extremely simple cases of division games, but were enough to show that Thue-Morse does not always produce a fair game.
However, let’s reconsider a slightly more complex class of games, Tic-Tac-Toe! (note: @Vsotvep mentioned this example earlier).
- Standard Tic-Tac-Toe is fair, since perfect play leads to a draw.
- Thue-Morse Tic-Tac-Toe is unfair, since the first player (X) can force a win, when playing with the move sequence XOOXOXX… (note: X can force a victory within the first 7 moves).
We can also considered a variant of Tic-Tac-Toe, which is still played on the 3x3 grid, except that the center square starts filled with a wild symbol that can be used by either player to complete a line. Let’s call this “Wild Tic-Tac-Toe”.
- Wild Tic-Tac-Toe with standard alternating turns is unfair, since the first player can force a win.
- Wild Tic-Tac-Toe with Thue-Morse alternation is also unfair, but now the second player can force a win.
2 Likes
How long would it take to solve NxN thue morse Go for something like n<=6 or something small 