Math & Cultural

   Coupon Go Duplicate Endgame Tournament: Play RSVP

    February 15, 2015, beginning at 2:30pm

    RSVP on this page to PLAY in the tournament.

At 2:30 on Sunday afternoon, February 15, MSRI will host a delegation of junior high school students from China, led by Jujo Jiang, a famous professional Go player.  The program will include an introductory lecture on Mathematical Go by Prof. Elwyn Berlekamp.  This will be followed by a "Coupon Go Duplicate Endgame Tournament", in which visitors will also be welcome to participate. Dinner will follow.

Watch Prof. Berlekamp describe his attempts as a mathematician to measure the exact value of go moves, culminating in the creation of "Coupon Go", here: https://www.youtube.com/watch?v=puK3qYiMKpQ.

To register for Tournament play, please click the RSVP button on this page in the upper right corner.

To register for dinner and to attend as a spectator, please click here: http://tinyurl.com/CouponGoSpectator.

Schedule

2:30 Welcoming talks in auditorium.

3:45 Tournament play, round 1 or 2

4:45 Tournament play, round 2 of 2

6:00 Dinner

Here's a description of the tournament rules for the February 15 event at MSRI.

COUPON GO

Coupon Go is a two-person game played with a stack of Coupons in addition to a conventional Go board and stones.

The value of each coupon is a number which is shown on its faces.   The coupons in the stack are numerically ordered, with the biggest coupon on top and the smallest coupon on the bottom.  The value of the top coupon is called the TEMPERATURE of the stack, T.   Throughout the whole stack, the difference between any consecutive pair of coupons is a constant denoted by δ.

For example, if δ = 0.5 and t = 4, then the stack consists of 8 coupons, whose values are 4.0, 3.5, 3.0, 2.5, 2.0, 1.5, 1.0, and 0.5, in that order.

As in conventional Go, players alternate turns.  At each turn, the player may EITHER place a stone of his color on the Go board, OR take the top coupon instead.  Either move or coupon completes his turn, and his opponent gets the next move.   After consecutive passes, the game is over.   Each player's gross Korean/Japanese score is equal to his sore on the Go board, plus the number of stones he has captured, plus the total value of all of the coupons he has taken.   The NET score is Black's score minus White's score.   The net score may be either positive or negative.  

If there is an active ko, taking a coupon, like any play on the board, lifts the ban on retaking the ko.

COUPON GO ENDGAMES

A coupon Go endgame begins with a position on the Go board specified by the tournament director.  "Classical" endgame positions are often taken from a professional game played by Go Seigen in the 1950s, typically 50 to 150 moves prior to the end of that original game.

COUPON GO ENDGAME TOURNAMENT

In any given round of a Coupon Go endgame tournament, all players begin with the same specified position and with the same set of coupons.   Typically each round is divided into two half-rounds.   In the second half-round, the starting conditions are the same, except that all players who played Black in the first half-round play White in the second half-round, and vice versa.

Depending on the details specified by the tournament director, the players in the second half-round might face the different opponents than in the first half-round.

DUPLICATE MATCH POINT SCORING

Duplicate match point scoring (analogous to that used in bridge tournaments) will be used in the event at MSRI on February 15, 2015.   The event will consist of a single round.    Each player will have a different opponent on the second half-round than on the first half-round.

All of the scores will be rank-ordered, and each player will receive a number of matchpoints equal to the number of other players whose scores he bettered.  

As a very simple example, suppose there are only 10 players.  On the first round, suppose the net (Black) scores, ordered by value, are  5, 2, 2, 0, -3.   Suppose on the second round the net (Black) scores, also ordered by value, are  4,3,0,0, -1.  Then the merged list of all scores,  is 5,4,3,2,2,0,0,0,-1,-3.   So the matchpoints corresponding to these scores are as follows:

net Go score            5,    4,    3,    2,     2,      0,    0,    0,   -1,   -3  

Black matchpoints   9,    8,    7,   5.5,  5.5,    3,    3,    3,    1,    0   

White matchpoints  0,    1,    2,   3.5,  3.5,     6,    6,    6,    8,    9

As an individual player, suppose that I played Black on the first half-round, and ended that game with a net score of 2.   Suppose that when I played White on the second half-round I ended that game with a net score of -1.   Then I would receive 5.5 matchpoints for my play as Black, plus 8 matchpoints for my play as White, a total of 13.5 matchpoints altogether.

KOMI

There will be NO KOMI at MSRI on Feb 15.  

Since all scores are relative to other players with the same conditions, the value of any komi would be irrelevant.

Since the number of half-integer coupons will be even, all net scores will be integers.  We hope this may make the tournament directors' jobs slightly easier.

REPORTING 

Every player will be required to record his games, and to submit a game record as well as the net Black score.

Game records may be submitted either on paper or in an appropriate electronic format.

INDIVIDUAL GOAL 

Each player should seek to earn as many matchpoints as he can.  This means trying hard, on each game, to MAXIMIZE YOUR SCORE.   "Playing safe" because you appear to be ahead is typically not the best strategy.  You are competing only indirectly with the opponent sitting opposite, you are more directly competing with all of the other players who started from the same position as you did.  After all, the initial position might favor Black, so getting a net score of 1 or 2 might be a poor performance if other Black players are getting higher net scores.   Similarly, getting a net White score of 0 might be quite good (as in the above example) or quite poor (if most other games in the tournament are ending with negative net scores).

DID YOU BEAT YOURSELF?  OR DID YOURSELVES LOSE RELATIVE TO EACH OTHER?

If you make no mistakes, then no matter how strong were your particular two opponents, or the rest of the field of players in this tournament, you should receive at least a large a net score playing Black as you did playing White.

GOAL OF THE TOURNAMENT DESIGNERS

We strive to learn more about what constitutes perfect endgame play.  By getting records of many human games all starting from the same position, we are hopeful that all locally good moves, even those not initially evident, will be found and played by someone.  So by looking at all of the records of all of these games, we hope to find the "perfect" solution to this particular endgame position under all of the following three conditions: 

  1) No coupons (as in the original Go Seigen record) 

  2) Actual coupons, with δ= 0.5

  3) Very THICK stack of very closely spaced coupons, with δ some very small positive number

We know that the best lines of play in all three cases are closely related.

From our mathematical perspective, case 3) is easier than 2), which is easier than 1).

WESTERN REDUCTIONISM

In some subjects, such as medicine, Asian cultures have emphasized a holistic approach, treating the patient as a single entity and trying to cure all of his inter-related ills.  By contrast, Europeans have emphasized a reductionist approach: identify the single dominant ailment and focus on curing it.  As an extreme example, if the patient has an appendicitis, then cut him open and remove the appendix.   His lesser ills might subsequently be treated separately.

In medicine, both approaches have their pros and cons.  Everyone has long been aware of what western researchers call the "placebo effect". Traditional Asian practitioners attempt to take advantage of this effect.  Westerners, befuddled as to how to control, monitor, measure or replicate such individualized efforts, design experiments intended to separate the placebo effects from the effects of whatever pharmaceutical treatments they might be considering.

In Go, our mathematical approach is aggressively reductionist.   We believe it is complementary to the traditional approach to Go, which emphasizes holistic "whole-board" thinking.  As the endgame progresses, the effects of moves become more and more localized, and it becomes increasingly feasible to analyze the battle in one region independently of battles in other regions.   However, a correct overall strategy still needs to determine the region in which to play as well as where to play in that region.  There are many games in which Black does best to make several consecutive plays in Region A while White does best to make several consecutive plays in Region B.  So the data structure resulting from a local analysis of region A needs to contain more information than the simple result which would occur if both players concentrated all moves in that region.   The goal is a locally-based data structure which provides enough information to facilitate optimum or near-optimum overall play, yet is simply enough that the process of combining data structures from different regions remains tractable.

A modern branch of mathematics called "Combinatorial Game Theory" has made major progress towards that goal.   It offers three distinct but inter-related ways to analyze Go endgame positions, including specific strategies for finding the best move.

1) ORTHODOX analysis is the simplest.  It provides optimum play in the presence of continuous coupons, details of which are discussed below.  For each position in its simple data structure, orthodoxy provides a number called the "mean" (or average) and a "temperature".  Means add numerically, and temperatures maximize.  Means are close approximations to the score; temperatures are measures of the sizes of moves.

Orthodox analysis differs from coupon-free analysis only w.r.t. the pairs of terminal and initial komis which occur at temperature drops.   The reason that the orthodox strategy so frequently coincides  with (or differs only very slightly from) the optimal coupon-free strategy is that these coupons are very often nearly equally divided between the two players.  From another perspective, in each region, the coupon stack tends to be a rather good surrogate for the rest of the board.

An orthodox analysis using continuous coupons is "top-down".  The earlier literature contains several expositions of "thermography", too lengthy to be discussed here.  It is an alternative, "bottom-up" approach which also determines orthodox means and temperatures.

2) CANONICAL analysis is more complicated, but completely precise and accurate.  Unlike orthodoxy, it also gets the last move at the maximum relevant temperature.  Its primary output is the "value" of the position, which may be a number, or an infinitesimal, or something more complicated.  The mathematics to add these values is well-developed.  It applies not only to Go, but to many other games, (e.g., Amazons).

It turns out that kos can be technically partitioned into two sets:  "Stable" and "unstable".   A study of over 60 kos which occurred in professional games determined that approximately half were stable and half were unstable.   Orthodoxy handles stable kos automatically.  Canonical analysis handles many of them with only minor modification.  

Much of the book "Mathematical Go" is devoted to canonical analysis.  The book includes many composed problems which even professional Go players find very difficult, but which combinatorial game theorists can do very quickly with provable correctness.  When the Go position is correctly modeled, the abstract canonical analysis will always correctly determine who can win and how.  We now completely understand almost all regions with temperature one and many of slightly higher temperatures.  But as one moves back to earlier stages of real Go endgames, the analyses become less and less tractable.

3) DOCTRINAL analysis provides the "mean" of any (unstable) "flower-ko" position.  Doctrinal means are numbers, and they add like numbers.  Doctrinal means are good approximations to real scores when the kothreats possessed by Black and White are relatively balanced.  When one player has many more bigger kothreats, the doctrinal means are less relevant.

HISTORY OF COUPON GO

The first professional Coupon Go game was an all-day game between Jiang and Rui at the North American Ing Center in Redwood City on April 21, 1998.   The initial temperature of the stack was 19.5.  The difference between coupons was 0.5.   Nineteen of the thirty-nine coupons had integer values; the other twenty had half-integer values, so the net score on the coupons would necessarily be an integer.   White was given an initial komi of 9.5 points, close to half of the value of the top coupon.

When the 4-point coupon was taken, the endgame position on the board proved extremely interesting.  We analyzed it completely over the next several months.  The results were published by 

Bill Spight [2002] "Go Thermography:  The 4/21/98 Jiang-Rui Endgame", in "More Games of No Chance", vol  42 in MSRI publications by Cambridge University Press.

The first professional Coupon Go tournament was held in Seoul in November 2007.  The second was held at the Mind Sports Center in Beijing in 2010.  The six participants were members of the Chinese team, which then included Rui Naiwei, Shao Weigang, Gu Li, Chang Hao, Ding Wei, Wang, Lei, Huang Yizhong, Zhou Heyang, Xie He, and Shi Yue.

DIRECTOR'S SELECTION OF THE INITIAL TEMPERATURE

The director will normally select the initial temperature to be sufficiently large so that both players's best initial moves will take coupons rather than playing on the board.  Each player is then immediately confronted with two questions:

1) Where is my best move on the board? and 2) How big is it?  In other words, how low must the value of the top coupon become before I prefer to play on the board rather than taking it?

Roughly speaking, the "temperature" of the board is the value of the coupon stack such that the players are indifferent between taking the top coupon or playing on the board.

If the temperature of the board exceeds the temperature of the coupon stack, it is better to move on the board.  Alternatively, if the temperature of the coupon stack exceeds the temperature on the board, then it is better to take the top coupon.

In some positions, there are complications which prevent this statement from being used as a mathematically rigorous definition of the temperature of the board.  For example, in a perfect "mia" situation, there may be a range of temperatures at which one or both perfect players are indifferent between taking the coupon or playing on the board.   Further complications can arise in certain kofights.

THICKER STACKS OF COUPONS

Naiwei Rui once suggested that we might try halving the spacing between coupons, from 0.5 to 0.25. 

Many Go players are accustomed to evaluating the sizes of moves in integers, as in a "10-point gote move" or a "5-point reverse sente move", each of which has temperature 5.   As mathematicians, we see that the temperature of a position is ∆V/∆M where  ∆V is the difference between the values of the two outcomes, and  ∆M is the difference between the number of moves between Black's outcome and White's outcome.   However, the narrow focus on integers can lead novice Go players to misestimate the value of moves in kos.

The temperature of a simple ko in which ∆V = 10, and  ∆M = 3 is 3 1/3.   A simpler example is the very common ko, sometimes called a "one-point ko" or a "half-point ko".  In fact, its temperature is 1/3, and so is its average value.  The Go player can see by experience and/or experimentation that the sum of three such kos yields one point for Black, no matter whose turn it is to move next, nor how many kothreats are available to either of the players.  So on average, each of the three little kos must be worth a third of a point.  Either player, on the next turn, can change this value by 1/3 point in their favor, consistent with the assertion that the temperature is 1/3.

We have also found it relatively easy to construct positions which have other small temperatures, such as 2/3, 3/4, 5/6, 7/8, ... as well as 4/5,...

By decreasing δ (the spacing between consecutive coupons), the tournament director provides encouragement to the players to evaluate the temperature of the board positions more precisely.  But a thicker stack of coupons means a more time-consuming game.   If the temperature of the stack is 5, but the difference between successive coupons is only 0.001, then there are 5000 coupons, and the game with only 60 moves on the board would still consume 5,060 turns.

CONTINUOUS COUPONS [See footnotes]

In the limit as the difference between consecutive coupons approaches zero, the director can shorten the game to a reasonable number of moves by the following rules:

1) The coupon at the top of the stack is T

2) When that coupon is taken, the temperature at the top of the stack remains unchanged at value T.

3) After same-valued coupons are taken by both players on several successive turns, play halts, and the opponent of the player who last took a coupon of value T is awarded a "terminal komi" of value T/2.

4) If T is its predefined terminal value (e.g., zero), the game ends.  Otherwise,

5) To restart play, each player must submit a sealed bid.  The bids are secretly compared and only the higher (winning) bid is announced.  If the bids are tied, then the winning bidder is chosen by some arbitrary rule.  The value of the winning bidder, and his winning bid, T', are announced.

5a). The stack is reduced so that its top coupon is reduced to temperature T'.

5b). The opponent of the winning bidder is given an "initial komi" coupon of value T'/2

5c)  The winning bidder must play on the board, and play resumes.

COMMENT: In most other combinatorial games, such as Amazons or Domineering, the predefined terminal value of the coupon is -1 rather than zero.

QUESTIONS FOR THOUGHT

1) With continuous coupons, why should the rules require the taking of more than three successive coupons before the play is interrupted by another auction to determine the next temperature?

Answer:  Suppose Black takes an active ko, then White takes a coupon, then Black takes a coupon, and then White retakes the ko.  This sequence of four moves correctly leaves the temperature of the stack unchanged.

2) Why does the play with a stack of very closely spaced coupons approach the same plays, with the same result, as play with continuous coupons?

3) With continuous coupons, can the referee's management of the bidding be replaced by a computer program?

4) Position "A" is said to be strictly stable in one of its ancestral positions, "B" iff the temperature of A is less than any of its ancestors in B.

Position "A" is said to be unstable in "B" iff there is some position which is an ancestor of A and a descendant of B which has lower temperature than A.

4a) When is a move to A "sente", and when is it "gote"?

4b) What if A is "quasi-stable" in B?

5) On a 9x9 board, construct an endgame position in which the only winning move is unorthodox.  What does the difficulty of finding such a construction suggest about the frequency with which such positions occur in actual games?

======

FOOTNOTE:

As indicated in the parentheses of item 4), conventional rules end the game when both players elect to pass by taking coupons of value 0.  However, another definition of Go scoring can be obtained by prohibiting passing, and redefining the terminal bid to be of value -1.   With that rule in effect, players will play out the dame at temperature 0.    Either player who so chooses can continue playing at temperature -1, by filling his own territory, playing into his opponent's territory, or returning a captured stone to his opponent's pot.   If he has more such moves than his opponent, his opponent can do no better than take -1 point coupons.  Eventually both players run out of moves on the board at temperature -1, and they take successive coupons whereupon the game ends via rules 3) and 4).

Under these rules, there is no need to score on the board, because all of the points are converted into coupons, EXCEPT for the last two eyes in each live group.  So this score matches a legendary set of ancient Chinese rules, which differs from modern rules in that the modern players get two additional points for each live group.