Two problems arise with Scheme B. One, winning players whose dollar-per-chip exchange rate happens to be “higher” than average can’t be paid back fully from that game alone, or ever if he keeps winning. Two, the players may not declare truthfully. Is there a clean way out of this?

The second problem is complicated, so ignore it now. The first problem occurs because the group of players does not, in aggregate, support the payoff profile demanded by the players with above-average dollar-per-chip exchange rates, if they also win more than average. In this context, we see that Scheme A (a group playing with agreed-upon equal-dollar stakes) gets around this problem by essentially setting a common exchange rate for everybody at the minimum of the group (that which enticed the last person to join). This works, but can we combine Scheme A’s payoff fairness with Scheme B’s utility matching fairness?

To some extent, yes. A marginal improvement can be made by noting that, as long as the players do not win 100% of the games, some exchange rate flexibility can be allowed. This is an interesting fundamental trade-off: the less spread out the winning percentages of players, the more spread out they can bid their exchange rates, and vice versa. In the one extreme, players set the same exchange rates (Scheme A) and any game outcome can be supported. At the other extreme, if the players are equally likely to win, then on average no chips change hands, so it wouldn’t matter what exchange rates were set (Scheme B). I should probably quantify what happens in the middle but can’t be bothered to do it today.

The usual adage is that the rules of “Go” are simple, but the strategies are difficult. Sometimes they cite the fact that computers can’t play “Go” very well (compared to, say, chess). I’m not in a position to defend or refute this sentiment yet, but I think this stuff is easier than it first appeared to me years ago, if you think about it the right way. “Go” seems a very mathematical game, almost a counting and topological reasoning game. And all the difficulties arise out of the fact that the counting and reasoning is done in 2D (rather than 1D, which would be simple).

So there is this list of terminology like “liberties,” “eyes,” “false eyes,” “alive and dead regions,” etc., but sometimes they greatly confuse the matter, so I found it easier to recast these basic concepts in more general terms.

There are really only two axiomatic rules to play Go.

Def. 1: A group of stones is some stones of the same color.
Def. 2: A liberty of a group is any of the cardinal neighbor points of the stones in the group that is unfilled.
Rule 1: A group can be captured if all the liberties of the group are filled by the opposing color.
Rule 2: A point that when filled would result in an immediate capture of a group to which the point also belongs cannot be filled, unless it results in a capture of a group of the opposing color and if in the immediate previous move it was not itself captured.

Of course, nobody plays “Go” using only axioms. Instead we use the axioms and properties of the board* to derive new results:

I. The concept of an “alive group” by means of forming “two eyes.” This group of black stones is said to be alive idiomatically because it has “two eyes.” Well, turns out the real proposition is this:
Def. 3: A “connected group” is a group for which there exists no subgroup with all the liberties unfilled by a stone of the same color. (We’re neglecting some issues related to stones on edges and corners.)
Prop. 1: A connected group must be captured together.
Proof: To capture any subgroup of the connected group, its liberties must be taken, but some of its liberties is occupied by a same-color stone not belonging to the subgroup, therefore the subgroup cannot be taken. Since all subgroups of a connected group are like this, no subgroup of a connected group can be captured alone.
Def. 4: An “eye” is a minimal subgroup of a connected group that, if alone on the board, has exactly one liberty for which filling it would trigger Rule 2. To “fill” an eye is to fill all its liberties.
Prop. 2: A connected group with two or more “eyes” cannot be captured.
Proof: Each player can only make one move per turn, and therefore two or more “eyes” cannot be filled simultaneously. Then each eye in the group must be filled separately, in some order. But that would involve invoking Rule 2 at some point for the first of these eyes, when none of the other eyes have been filled. Since the group is connected, it must be captured together, yet we just said it does not have all of its liberties filled at the time that Rule 2 is invoked, and therefore filling the first eye is an unallowed move. Therefore, a connected group with two or more “eyes” cannot be captured.

II. Next, the “false eye” is simple, like the top one here. It’s just not an eye by Def. 4, since the circled black stone and the one above it are not in a connected group with the rest of the black stones.

Corollary 1: A group that is a disjoint union of connected subgroups cannot be captured if each subgroup has two or more liberties that would trigger Rule 2.
(Formations around these liberties are also called “eyes” usually, but I don’t consider them eyes.)

III. Usually the next step is learning how some groups that don’t have two or more eyes are nevertheless “alive,” “dead,” or “unsettled” based on how further moves could necessarily, necessarily not, or possibly — dependent on move order — allow the capture of the group. This is usually part of some rote memorization drill in Go, but it doesn’t have to be this way.

Def. 5: A region is a group along with some additional unfilled space.
Def. 6: A critical point in the unfilled space of a region is a point that if and only if filled, would make the extended group (original group of the region, along with the newly filled point) a connected group with two or more eyes.
Prop. 3: A group in a region is “alive,” if it has two or more critical points.
Proof: Assume it’s the opposing color to move. The best move would be to deny one of the critical points. Yet there are other critical points, so therefore a response at one such point would create a connected group with two or more eyes, which cannot be captured by Prop. 2.

Prop. 4: A critical point, if it exists, has at least two liberties.
Proof: A point with zero or one liberty does not create new eyes upon filling the point, so it cannot be a critical point.

Thus, immediately, the enclosing group of L-shape and Z-shape spaces-of-four are alive, because there are two critical points in the unfilled space. The enclosing group of straight-line spaces-of-five-or-more are also alive, since there are even more critical points.

Def. 7: A critical tree in the unfilled space of a region is a set of points that can be arranged into a hierarchical tree, such that making moves along any complete path in the tree results in a connected group with two or more eyes, and making any other moves does not.
Prop. 5: A region with a critical tree of branching factor at least two at each level (a good tree), is “alive.” If all branches of the root have some child node with a single branch (a bad tree), then the region is “dead.” If only one subtree of the root is good and the remaining subtrees are bad, then the region is “unsettled.”
Proof: In the first case, since the branching factor is at least two, no matter what the opposing color does at each move, there is always another subtree remaining to complete a path. In the second case, then even if the group’s color makes the first move, at some level, the tree does not branch, and the opposing color would play the corresponding non-branched child, making it impossible for a complete path to be made by the group’s color. In the third case, if it’s the group’s color to move, then the “good” subtree would be chosen; if it’s the opposing color to move, also the “good” subtree would be chosen, but in this case, the opposing color occupies the root of the good subtree and denies a complete path to the group’s color.

Corollary 2: Prop. 3 is a special case of Prop. 5 with a one-level tree.

So we see, for instance, that the enclosing group of the spaces-of-four in the square shape is “dead,” since the branches of the critical tree consists of the two internal diagonals of the square shape, the two subtrees of which (both single-branching) are both “bad.”

Corollary 3: A group in a region may be “unsettled,” if the region has exactly one critical point.
Proof: This is a special case of Prop. 5 with a single “good” subtree of depth 1, and possibly some remaining subtrees from the root that may be good or bad. If the group’s color is first to move, then the critical point can be filled and the extended group cannot be captured by Prop. 2. However, if it is the opposing color to move, then the best move would be to deny the critical point with an opposing color stone. In order to capture that stone, the group’s color would have to exhaust all the liberties of the original critical point, thereby making it not a critical point in the resulting configuration by Prop. 4. Whether the new configuration is alive is undetermined as it depends on whether at least some of the other subtrees from the root are good.

In the case of the enclosing group of straight-line and L-shape spaces-of-three, as well as the pyramidal spaces-of-four, for example, there is only one branch from the root and it is a “good” subtree of depth 1. Therefore, by Prop. 5, these groups are “unsettled.”

* Incidently, “Go” potentially has an infinite number of variations, because it can be played under changes of the board topology and handicap stones. The axiomatic rules don’t need to change in that they are topologically agnostic. There are even 3D “Go” boards. Additionally, if multiple moves can be made per turn, the entire game also changes — for instance, you’d need to create three or more eyes to be alive if two moves can be made per turn, etc., all the more reasons to prove general results. (See also this.)

Basics:
The game is played with two joker-included decks of cards. 5, 10, and K are point cards worth face value, except K is worth 10 points. It is a standard 4-player partnership game, so a person and his cross is a team. It is played in multiple rounds and each round there is a dealer (hence a “dealer” team and an opposing “grabber” team). Each team keeps a “level” represented by a card rank (i.e. 2,3,…,A), and each round is associated with the dealer’s level, whose corresponding rank cards are called the level cards.

Goal of the game:
A team’s goal in the game is to rise from the lowest level (2) through the highest level (A) before the other team. To rise to a higher level, the team must accrue enough points in a round by taking tricks with point cards in them. In usual score keeping, only the grabber team’s points are counted — it’s a zero-sum game. So the dealer team can be better thought of as seeking to prevent the other team from accruing points.

Playing the game:
Both teams start the first round at the lowest level 2.

Establishing trump and rank: Each round of play begins by dealing all but the last 8 cards face-down, hands-up, dealer first. During the deal, the trump suit is determined by revealing identical level card(s) of the same suit or identical joker(s). The player first to the table with the most identical cards at any given moment is said to govern the trump in that suit at that moment; except if another player reveals the same number of (or greater) identical jokers, in which case the first of the latter players to do so governs the trump and the round is notrump. A player who governs the trump at a given moment may only continue to reveal cards identical to the winning ones.

Once dealing completes, the last determined trump suit becomes official. The final card ranks in descending order are then defined as follows: color jokers, black jokers, trump suit level cards, other level cards, other trump suit cards in A…2 order, other rank cards in the leading suit in A…2 order, other rank cards of the other suits in A…2 order. There is a little bit of strangeness here: jokers and level cards are considered part of the trump suit for all purposes of play other than this initial rank definition.

Bottom pile: After dealing/trump determination, the dealer takes the last 8 cards into his hand. Then he takes 8 cards from this hand to leave face-down as the “bottom pile”. Point cards left in the bottom cards have consequences for scoring.

Playing tricks, leading: As usual, the dealer leads on the first trick and subsequently the winner of the prior trick leads. The lead can lay down cards with the following “patterns” (to be a pattern, cards in the pattern must be in a single suit): a single card, a multiplicity of identical cards (not just in the same “suit”, c.f. trump suit), “tractors”, and “tosses”.

Tractors are runs of the same multiplicity (>1) of identical cards, where “run” is determined by the final card ranks.

Tosses are combinations of singles, multiples, and tractors whose components are seperately unbeatable in the suit. It does not imply that a different outcome is impossible were the components played sequentially even in an optimal way (so tosses are advantageous, at least on that trick). However, it would be a degenerate contraction play if this were a one-suit game. Anyway, this is the most obfuscating aspect of the game.

Note that there is a recursive expansion of higher order patterns into lower order patterns. Let’s denote the patterns single, multiple, tractor, and toss respectively as S,M,T,X. Then the allowed expansion rules (from observed practice) are M=M*S*, T=M*, and X=T*M*S*. The X expansion is the unique maximal one given by its definition. The T expansion fully and uniquely expands the tractor into its component multiples. The M expansion is different from the rest because it is non-unique.

We can also define an algorithm for matching a subset of some set of cards to any pattern. It involves recursive expansion of the pattern and matching T and M, which are defined by their lengths. Note that T, M, or S are all degenerate forms of X, so without loss of generality we only describe the case for X. Follow this precedence:
1. Given X, the order is to match T* in the expansion, from long to short; each match removes a T from the pattern from further consideration;
2. For the remaining which we call X’, we expand X’=T’*M*S*=M*S* and match the M* from long to short; each match removes an M;
3. For the remaining which we call X”=M*S*, we take the longest remaining M and expand it in X” in all possible ways (which necessarily shortens some M) and sort the resulting list of expanded patterns of X” by longest M, then we discard all but the top of the list, and repeat from 2 on the top of the list; each successful match removes an M; we keep doing this until all the M’s are matched or all M’s are turned into S’s;
4. Match the remaining S* trivially.

To complete the algorithm, define “successful” match to a T or M of a certain length. There are two kinds. In “minimal” pattern matching, a successful match is between T or M in the set of cards whose maximal length is the same as that of the target T or M. In “maximal” pattern matching, a successful match is between any subset of cards that can form T or M of the target T or M length (i.e. they may be part of a longer T or M).

Playing tricks, ranks of same-pattern laydowns: When full pattern matching (i.e. the maximal pattern matching requires no T- or M-expansion) occurs between two laydowns, then we can determine rank between them. One multiple outranks another if its singles all outrank; one tractor outranks another if the lowest multiple of the first outranks the same of the second; one toss outranks another if there exists a correspondence of singles, multiples, and tractor components in the two tosses such that each component of the first outranks the corresponding component of the second.

Playing tricks, following: A follower must play the same number of cards as the lead. In selecting these cards, he must attempt to match the leading pattern out of his leading suit using the minimal pattern matching algorithm. If his leading suit is exhausted in the middle of the algorithm, the remaining can be made up without restriction using any card of any suit. A trick is won by the person first displaying a laydown that is not outranked. A laydown is not outranked if (1) it has the leading pattern (i.e. is a full pattern match to the leading pattern, and of course in some single suit); and (2) it is not outranked among laydowns having the leading pattern. Corollary: The leading laydown can only be outranked by the same pattern with higher rank in the leading suit or by the same pattern with any rank in the trump suit; if the latter is played, that can only be further outranked by the same pattern with a higher rank in the trump suit.

Scoring: The point card values won by the grabber team are added. If the final trick is won by the grabber team, then the bottom pile is revealed, with point card values in the pile generally counting as double value. If the total is <80, the dealer team wins the round, retains deal, and rises 1 level. If the total is >=80, the grabber team wins the round, and becomes dealer. If the total is >=120, the grabber team also skips a level (so rises by 1). These are the usual cases. Ostensibly each additional 40 points allows the winning team to skip another level, but I’ve not seen this in play.

Strategy:
Exercise for the reader.

In this game, each person keeps his own level. During each round, one person is dealer and it is the dealer’s job to entice one other person to be a partner for the round, during the course of play. This is done by the dealer declaring an “identification card” on the first trick such that, when it is first played by anyone other than the dealer, that person is teamed with the dealer. Then the remaining three players become the grabber team, and they must score 130 points to win, otherwise the dealer team wins. Winning means the people in that team get to advance one level. If the grabber team reaches 195 points, the grabber team gets to skip a level. Losing means people in that team stay at the same level.

Notice that there is a bug here in that the dealer can declare in a way that no partner can be found… I guess that’s ok since it would be stupid to do so, but in other literature it is a strategy with point compensations.

In the simplest of examples, you pay some entry fee to play the game, $1 is put in a pot by a counterparty, then a coin is repeatedly flipped and the pot is doubled on every coin flip by the counterparty, until “tail” comes up. You receive the money in the pot. The expected gain of this game is infinite, regardless of the initial entry fee. So it would seem that one should always play the game, regardless of the amount demanded as entry fee. But, as the article points out, “few of us would pay even $25 to enter such a game.”

(This seems to be one of many variations of the paradox.) The explanations given in the link to resolve the paradox aren’t satisfactory. “One can’t buy what isn’t sold” can only be considered a joke, while “expected utility” is somewhat plausible, but doesn’t strike at the central issue, because it can be circumvented with an equally counter-intuitive paradox fitted to the chosen utility function. In contrast to the Gambler’s ruin paradox, I don’t think that an artificial finite bound on the money supply (in this case, of the counterparty) makes sense as an explanation, but what it reveals as the logarithmic growth of the expected gain against the money supply and the general consequence that imposing some kind of finiteness may explain the paradox, is instructive.

Of course, the only way to get any gain is to actually play the game. If you repeatedly play the game, your gain does eventually go to infinity. So why would you be reluctant to pay even $25 to enter? It must be because those large pay-offs are so infrequent that to make the initial money back would take too long. Suppose the entry fee is \(W\). Suppose you call it a day when you have a positive pay-off. For that to happen in round \(n\), it must be true that

where \(f_i\) is the number of flips before tail comes up in round \(i\).

Let’s call n-tuples \((f_1, f_2, \dots, f_n)\) that satisfy the above by the set \(S_n\). The probability of winning in round \(n\) is then

from which we can surely get the average number of rounds it will take to win the game \(\sum_{i=1}^\infty n p_n\). If this is incredibly large even for modest \(W\), which is likely the case, then that would explain the paradox, since a game that on average takes longer than a lifetime to win would be played by no one.