# Thue-Morse (Fair Sharing) Sequence: A possible alternative to komi?

I said above:

Let me be more precise, since the word “fair” is somewhat vague and subjective. What I mean to say is that the Thue-Morse sequence does not necessarily remove the inherent advantage of one of the players.

This can be seen even in the simple “game” of splitting up a finite set of items (of various values), which is an example that has been used as motivation for the Thue-Morse sequence.

Consider if there are four items, worth \$200, \$125, \$100, and \$50. Clearly, player A (picking first and fourth) will get \$250 of value, while player B only gets \$225.

If the four items were instead worth \$200, \$150, \$125, and \$50, then player A would get \$250 of value, while player B will get \$275.

You might be able to argue that Thue-Morse was still a “fair” (or maybe even the “fairest”) method to divide the items in the above scenarios, however, clearly there can be an inherent advantage for one player over the other. In either case, the two people involved would argue about who should get to be player A or B, and perhaps the only “fair” way to further settle that would be a coin flip.

One final example: the four items are worth \$200, \$100, \$75, and \$25. Thue-Morse would give a clearly bad result, since whoever wins the coin flip to be player A gets to take \$225 (vs \$175 for player B), while obviously one could just split the fairly with \$200 going to player A and \$100 + \$75 + \$25 going to player B.

5 Likes

I love this, as a game concept, not as a way to eliminate komi. Who wants to try (in a week, when holiday is over)?

As for fairness, that is not something that translates at all. Fairness here is used as a mathematical term, and thus does not correlate to the linguistic interpretation of what “fair” means.

In fact, since go is a perfect information game without draws, there must be a winner, so it can never be made “fair” without hiding some of the information or allowing draws to happen.

3 Likes

I would like to try it, but I would need an easy way to know when to pass. Sadly the move-tree will be no help.

Edit: The move order is not as bad as I though

`bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wbwb_bwbw_wb_bw_wbwb_bwbw_wbwb_bw_wb_bwbw_wb_bw_wbwb_bw_wb_bwbw`

Edit2: python code to translate OGS move number to player action (play/pass)
``````def thueMorse(n: int) -> int:
return bin(n).count('1')%2

def move(n: int) -> None:
thueMorse_move = 0
for i in range(0, n):
if (i%2 == thueMorse(thueMorse_move)):
thueMorse_move += 1
if ((n-1)%2 != thueMorse(thueMorse_move-1)):
print('pass', end=' ')
if n%2:
print('b')
else:
print('w')
``````
4 Likes

Too bad that you can’t use PASS when planning conditional moves. That would make it fairly easy to play.

3 Likes

Sounds cool as a variant, I’d definitely give it a try.

1 Like

Here is another visualization of the move sequence (up to 1000), with double moves highlighted in red.

I think this move sequence would have a rather chaotic impact on the game. Not only will the double moves change life/death status, validity of tesuji/joseki/etc, the timing of any strategic move is important in relation to the chaotic sequence of double and single moves.

For example, if one were to ask “Is the L group dead?” under this variant, I think the answer might depend not only on who’s turn it is, but also precisely where in the move sequence you are.

6 Likes

True, non-integer komi (to avoid draws) does not equalize the theoretical advantage (one color should always win under perfect play). In principle, there should be some integer komi where perfect play (under a reasonably specified ruleset to avoid no results and endless games) would result in a draw. However, in practice, an appropriately set non-integer komi does seem to at least narrow the practical advantage disparity vs not using komi at all (the winning chances for two equally skilled players seem to move closer toward 50-50).

I am not at all convinced that Thue-Morse would narrow the practical advantage disparity. Maybe it does or maybe it even makes the advantage disparity worse. It’s just a completely different game, still with players taking turns, but just sometimes they are allowed to play two stones and sometimes just once, in a big chaotic and asymmetric mess.

I expect that if people try to play this variant, they will initially find roughly balanced performance, simply for the fact that all learned go tactics, strategy, and theory would have to be thrown out and everyone will be on the same initial footing back at the drawing board. I think only basic reading (visualization) skill will be readily transferable, but one will have to actively resist learned patterns, intuition, shape, gut feelings, etc.

2 Likes

I think the opposite is true… thue-morse literally exists to remove the advantage of going first. This is purely an order of play equaliser and says nothing about either player’s ability to recognise the best move, it simply corrects the advantage that one side would have of going first, meaning it doesn’t matter if you play first or second, because it evens out rather quickly.

The only reason Go has no draws is because we artifically set komi to be a non-integer value. Go in its natural state can (and indeed the mythical “perfect game” would) end in a draw. You can also just play with NZ rules who use integer komi and allow draws

Sounds fun, doesn’t it? (because obviously what Go really needs is MORE complexity!)

3 Likes

Bots would love this variant because ladders (their only weakness) NEVER work

6 Likes

@Kosh v me (experiment 1)

4 Likes

yes, i think this is the best way for deciding komi, even better than the current rule of 6.5

another suggestion i read somewhere else is the “i cut, you choose” approach. player A placed a black stone somewhere on the board, and then B can decide whether he wants black or white. this way, A will try his best to make the 1st move neutral (whatever it means).

all these would seems much simpler than the ABBABAAB .

3 Likes

No it doesn’t. Take for example Tic-Tac-Toe, in which the Thue-Morse sequence will guarantee a win for the first player (play in the center).

Of course that game is too small to be taken serious, in this manner, but the same will hold for 4 in a row on a large board (where the first player wins at the 7th move). I’m pretty sure the first player will win 5 in a row as well (although I didn’t go through all combinations to check).

The reason the sequence is fair in other situations (let’s say dividing a pile of cookies by choosing them one by one following the Thue-Morse sequence), is that your move does not affect the value of the other possible moves (choosing a cookie does not change the desirability of the other cookies). I don’t see the same thing happening with moves in a game, since the moves drastically change the value of the other moves.

At the n-th move, write n in binary and count the number of 1’s. If it’s odd, then it is white’s turn, if it is even, then it is black’s turn. To keep track of which “real” move it is (as the move counter will not help), you could just write the move numbers in chat each turn, or you could count the stones on the board + prisoners.

5 Likes

@andysif: This is known as the Pie Rule. I think it is even more fair than a coin toss.

@Kosh: I had never considered Komi bidding before. I think it is genius. My only edit would be to switch your suggestion of a coin toss with using the Pie Rule instead. If neither player can agree on who gets to suggest the first move, then I am 100% for deciding that dispute with a coin toss .

3 Likes

Some earlier discussion from reddit:

4 Likes

Did you see my follow-up post where I give some simple examples where Thue-Morse fails to equalize the advantage, or even just switches the advantage to B?

Thue-Morse is designed to be fairer than alternation, but there are no general mathematical guarantees that it will eliminate the first move advantage for all games (even for simple item division games). The mathematical guarantees are asymptotic results (i.e., looking at the limit for infinite sequences) and should require at lease some technical conditions to hold true (to avoid cases where it will not work). For finite sequences (i.e., a finite game like go, or just the division of a finite number of items), you can have cases where Thue-Morse does not balance the advantage (e.g., tic-tac-toe as @Vsotvep mentioned, or the item division scenarios that I mentioned above).

Even with infinite sequences, you can still construct examples where one of the players will have an advantage. It is easy to give A the advantage by just making one item (or the first move) worth a lot, while the rest are much smaller (and could be made to be vanishing toward zero such that the relative advantage can be arbitrarily large). You could even construct an infinite sequence that gives B the advantage, by setting the values in relation to the move sequence. For example, start with 100, 100, 100, 1, and then continue with smaller numbers. Of course, these are just simple examples, but you could specifically craft longer, more complex sequences that also create imbalance.

Assuming that the advantage would be balanced in a Thue-Morse go variant is just an intuitive speculation. It may be the case, but it would need to be proven (analytically is probably impossible). Empirically, however, if this variant took off, people spent centuries playing and studying it, many books/videos/etc are created, pro-leagues are established, AI engines built, etc., then maybe we could collect enough data that could support or refute that hypothesis. Actually, maybe just throwing some AI power at the game could bring some insight.

You also quoted the part of what I said about the strategy-stealing argument, but didn’t make any remark about that. That could still apply, depending on how we define what happens when the first move is a pass.

I think this is a very interesting variant to consider, more for the aspect that it wildly changes the game, rather than that it might be more balanced. However, I do not think it is a suitable alternative to komi since:

1. It wildly changes the game, with new tactics and strategy that will only barely resemble go.
2. It does not necessarily balance the advantage.
4 Likes

A side note on strategy stealing: it does not work in Go since not every stone on the board is necessarily a benefit. It could end up in a shortage of liberties. This is very theoretical and unlikely for the first move on the board, but strategy stealing by itself is a purely theoretical argument.

Wikipedia says that black can do it by passing, which irritates me. A pass is not a move, it is a signal that you consider the board finished. Weird thing to do on move 1.

At the very least with the introduction of this Thue-Morse sequence, it’s all over for stealing the strategy. The order of moves ABBABAAB… is not the same as the inverse of BBABAAB… after black benefits on move one. Therefore black can not just copy the winning strategy from white, if it exists.

3 Likes

The strategy-stealing argument (SSA) for go hinges completely on the fact that a player can choose to pass. If passing is not allowed on the first move, then, yes, the argument does not work, since we have not shown that the initial position is not like some sort of zugzwang. If both players keep on passing, refusing to make any moves, then I think the game would just end as a draw (assuming no komi, of course).

For the Thue-Morse sequence, I agree that the SSA might not apply. However, one could always define the consequences of the first move being a pass as swapping roles and delaying the start of the sequence. That might seem a bit arbitrary, but hey it’s a hypothetical variant and I’m just suggesting it to make a point.

So, let’s consider an additional tweak (specification) to the Thue-Morse variant, where black is allowed to pass his first move, which then just delays the start of the sequence by (with the two players essentially trading colors). Of course, I don’t think that’s what others have intended, but that’s what I meant above when I said that the SSA could possibly apply depending on how we define what happens in the event of a first move pass.

1 Like

A lot of the problems with fairness in the thue morse examples you gave with money are removed if you play the game twice right and swap who goes first? So if you think there’s an advantage for going first/second then playing twice and swapping who goes first evens it out.

Of course then you run into the problem that arises in chess in that a set of games has to end somehow. So you could do a thue morse sequence to decide who plays which colour each game for a fixed number of games. But again it only seems fair that it should be an even number of games which can still be a draw like in the recent World Championship games with Carlsen and Caruana, so you need a tie break plan like they have with blitz games.

The game of Tak (a recent game based on a very old game in a fantasy book series) uses a unique set of starting rules that I have never seen before. The first player places an opposing piece on the board, the second player player then places one of their opponent’s pieces, then play starts in a normal sequence. This appears to level the game quite a bit, but exactly how much is debatable and if it would apply to Go is also debatable (a wasted stone is pretty easy to place in any corner with very little impact on the game.) However here’s what a sequence might look like for Go:

1. Black places a White stone on the board.
2. White places a Black stone on the board.
3. Black now starts to play a normal sequence, placing for the first time their own color stone and play continues from there.

I suspect in this case the stones would need to be placed on star points, or potentially next to star points.

Go is such a deep game, from a strategy perspective, that the idea of trying to balance it seems almost pointless. You are almost never going to meet someone with whom you would play an even game. The odds of meeting someone exactly on your own level are ridiculously small, and I think a better way to handle this is with automatically calculated komi based on previous win/loss records (rank). So, negative komi for very large distances in ability feel intuitively like the best option.

Note that I despise handicap stones, as they feel too heavy handed as a tool and modify the behavior of play too greatly, forcing white to play a game filled with invasions. And while reverse Komi might also require such a style of play, it feels less like it while playing.

1 Like

So white gets tengen and black a stone next to tengen?