Calculating a Thermograph

Several discussions have occurred here on SL concerning the calculation of the values of plays and of thermographs, which give more information than just a single number. For a textbook treatment, see Winning Ways by Berlekamp, Conway, and Guy, and On Numbers and Games by Conway.

The following long and detailed discussion has been moved here.

Robert Pauli:
Thanks for your reply, Bill, even if it crushes my beliefs. Somehow my impression was that the binary tree used to compute miai values was made up of locally, say, minimax-best plays, but that doesn't seem to be the case. What you're saying sounds like miai values themself ranking the moves to be used in the tree. Boy, I'm really confused. Not that I'm new to recursion, but where's the ground case here? Temperature zero? At least it can be checked with minimax, and since nothing can be gained the miai value of each move should be zero in that case. Then I can slowly work my way back...let me instanly hurry to my chamber and contemplate... :-)

Bill: This may help. It's from my talk at the Computers and Games 2002 conference. The slides are on my home page.

Later: Slides 5 - 7 are relevant.

Suppose that we have the following game tree, with / indicating a play by Left (Black) and \ indicating a play by Right (White):

              G
             / \
            /   \
           H    -7
          / \
         /   \
       -2    -4

Suppose that Left (Black) plays first. We get the following backed-up minimax values.

             -4
             / \
            /   \
          -4    -7
          / \
         /   \
       -2    -4

For calculating the miai value of G, we add the parameter, t.

              G
             / \
            /   \
           H   -7+t
          / \
         /   \
      -2-2t  -4

Then we get these backed up thermographic values:^[1]

     max(min(-4,-3-t),-5)
             / \
            /   \
  min(-4,-3-t)  -7+t
          / \
         /   \
      -2-2t  -4

The top value represents the left wall of the thermograph of G. Solving for t in

    min(-4,-3-t) = -7+t

we get

    t = 2

So the miai value of G is 2.

That's kind of sketchy, but I hope you get the idea.

(BTW, we are going to have to move some of this discussion. :-))

Robert Pauli:
Wow. Be sure - I don't get a single word. Dummy me thought that it simply would go by propagating averages and then to look at the distance between root and one of its daughters:

           = -5      -
             / \     | = 2
            /   \    |
        = -3    -7   -
          / \
         /   \
       -2    -4

Just an incident that it turns out to be the same ?

Do I need to swallow thermography to get miai values ?

(Move it whereever you want, Bill, I'm lost anyway. :-)

Bill: Sorry, Robert. I was way too sketchy.

You do not need to know thermography to figure out miai values. People, including myself, have been doing that for many, many years. :-)

However, the thermograph (TG) gives more information than just the count and miai value. One thing it can indicate is which plays (each line in the TG is associated with at least one line of play) to choose under which circumstances. That is one question in the DGZ problem. To answer this kind of question you have to look at the walls of the TG.

You brought up the question of minimax. The walls of the TG can be expressed in minimax terms, and that is what I showed.

Going back to the problem. The line of play to use when White plays first to figure out the count and miai value for the bottom right corner is on the 2-3 point. That was obvious to me. The line of play to use when play is restricted to the corner is on the 3-4 point, solidifying the wall. (That is also the one to use at temperature zero, OC.)

The right wall of the TG for the corner tells us that, as a rule, the time to switch between those plays is at temperature 1. We could work that out without the TG by considering that playing on the 2-3 allows Black to make a 3 point reverse sente, while playing on the 3-4 is only 2 points worse, on average, than playing on the 2-3. We can gain one point by playing on the 3-4, at the cost of one move.

Now, since the remaining play on the board has a miai value of one point, thermography does not give us a clue which play is right. However, as it happens, the play that is correct under most circumstances is still correct for the problem.

The thing is, when you are looking for the best play in an area of the board, you do not as a rule look for the best play at temperature 0. That is not realistic in a real game. Usually you want the play that defines the miai value. That's why my eye immediately went to the 2-3 point.

As for figuring miai values by taking averages, you realize that that does not work in the following example.

          = -3.5     -
             / \     | = 3.5
            /   \    |
        =  0    -7   -
          / \
         /   \
       +4    -4

Robert Pauli:

I admit that, even reading a bit thermography, I still can't decipher your tree decorated with t's:

• why do some nodes get no t?
• why do some nodes get more t's?
• why does t's sign differ?
• -3-t seems to be the average of -2-2t and -4, but why is it joined with -4?
• where the heck is -5 from??

Bill: Wow, that's a lot, Robert! Our disucssion has prompted me to think that I should create an Endgame Calculations without Tears? page, but I really can't do much on that until December. Meanwhile, let me give some brief replies.

The coefficient of the t's at the terminal nodes is w - b, where w is the number of White plays starting from the root and b is the number of Black plays. Other coefficients are derived from these.

In min(-3-t, -4) you are comparing the gote and sente possibilities.

-5 is the count if the node is gote. It is derived from solving the system,

   c = -7 + t
   c = -3 - t

If this is some alternate method to find miai values, great,

Bill: It does that, and more. :-)

but my main problem is simply to set up the (binary) tree.

Did a bit homework, reading some DGoZ 2001 articles by Bernhard Herwig about miai values (great job, Bernhard). He explains it via perfect play on N copies of the local position, dividing the total score by N and looking what happens for growing N. (Not a word about my beloved binary trees, however.)

With that I get why averaging a single tree doesn't always work: the context isn't rich enough. Your counter-example completed would then be

   = -4  (not my naive -3.5)
     / \
  = 0  -7
   / \
 +4  -4

because with, say, 3 copies and Black starting it's better for White (going right and for low) always to answer, leading to -4 -4 -4 instead of +4 -7 -7. Naturally one calls this sente, but that explains nothing. (I know I'm boring you - sorry.)

See Method of Multiples.

Another thing I noticed was that there's a difference between the miai value of positions and of moves. To make things plain, I would call them average score and average gain - and, by the way, I would have leaves increasing to the right.

Bill: Japanese yose theory talks about the miai value of a play; CGT talks about the temperature of a game. When the play is orthodox without regard to the ambient temperature, its miai value equals the temperature of the game. Somewhere Charles Matthews and I had a discussion about whether an inferior play had a miai value, and we each seem to have convinced the other to change sides. ;-)

Back to a single tree. At Miai values list / Discussion you told Karl that a node's value only is the average of its daughters (values) if it stays between the granddaughters D and E:

        A
      /   \
     /     \
    B       C
   / \     / \
      D > E
        =

Otherwise A is either D or E, whatever (B+C)/2 is nearer to.

This seems to suggest that one can do without perfect play on N copies and simply propagate up

 A = T if T <= D and T >= E
   = D if there's D and T > D
   = E if there's E and T < E

   with T = (B+C) / 2

provided each leaf is in the turn-is-worthless state (or is at temperature zero) and is assigned the score reached by perfect play no matter who starts.

Hope that now works (else I'm at tears... :-)

Bill: There are three basic cases:

• First, gote, where the count is the mean of B and C.
• Second, sente, where the count is D or E.
• Third, reversal, where the answer lies further down the tree.

In a way, thermography simplifies your task because you do not have to worry about these distinctions. More on the calculation page when I get around to it.

Ok, but how do I set up the tree in the first place? I mean, neither side just has one move, not even in a local position.

Bill: Include every move for each player at every node. (That's often impractical. You can usually eliminate bad plays.)

This is where I originally went wrong, choosing the follow-up position for each side that evaluated best in the empty context. Now I rather guess that positions have to be evaluated in a context crowded with copies of themselves.

Bill: It's not so bad.

So, to find the left/right daughter of a node that is no leaf, that isn't in the turn-is-worthless state (for simplicity I'll assume moves bringing positions nearer to end):

• look at each position Black/White can reach from it in one move
• recursively compute its miai value (or average score)
• choose one with the highest/lowest value

Is this OK, sensei Bill?

Bill: I don't think that takes reversal into account. For an example of reversal, see hanetsugi.

Robert Pauli:
Wherever I stand, the carpet is pulled. Binary trees? No. Average? No. Depth limit? No. :-) Even the method of multiples doesn't seem to be general: kos.

Nevertheless, and how impractical it might be, it's the best I currently have. You don't depend on dubious arguments about sente and gote - you simply turn off intuition and proceed.

That's what I'm after: not a bunch of tricks for the tournament, but an objective method for the aesthetic pleasure.

I'll be happy to see any page that addresses this.

[1] Jeff: I got lost in that diagram. I understand where the -2t and +t came from in the two leaves. But how does -2-2t become -3-t? What I mean is, shouldn't the root node be max(min(-4,-2-2t),-7+t) and the root's left child be min(-4,-2-2t)? What am I missing when you propagate the minmax values up from the leaves?

Bill: Good question, Jeff. Thanks. :-)

Repeating the tree for convenience.

     max(min(-4,-3-t),-5)
             / \
            /   \
  min(-4,-3-t)  -7+t
          / \
         /   \
      -2-2t  -4

The value when we back up one move above -4 and -2 - 2t represents two scenarios: first, White replies to Black's move and goes to -4; second, play stops. We do not contemplate the scenario where Black continues to -2 - 2t, since, at that value of t White goes to 4. When t is higher, White does not reply. For the second scenario we take the value at that node. To get that value we need the values of the children. In this case, a simple gote, it is the average of -4 and -2 - 2t, or -3 - t.

Make sense?

Jeff: Thanks, Bill. Now I Understand the min(-4,-3-t) thing. It has everything to do with the knowledge that black just moved. So now, I'm confused about the root node, since we don't have knowledge of who last moved. I tried plugging in some numbers to see if that would help get me figured out, but it only served to give a concrete example of my confusion:

Imagine the game at low temperature, say 0.1. If black moves first, he may choose to either tenuki (0.1) or move here. If black moves here, we know white will respond because the local temperature is ((-2)-(-4))/2=1. So black's move ends him in -4. If white moves first, he will move here in gote, netting -7+t=-6.9. Thus the value of the position at t=.1 appears to be avg(-4,-6.9)=-5.45

Your formula, however, suggests the value of the root is max(min(-4,-3-t),-5) = max(min(-4,-3-.1),-5) = max(min(-4,-3.1),-5) = max(-4,-5) = -4

My analysis yield -5.45 where yours yields -4. Where am I going wrong with my analysis?

Bill: About the root. I did not explain where the -5 came from. It is the average of -3-t and -7+t, and the mean value of the root. When t > 2, then if Black plays first he gets min(-4, -3-t), which is -3-t, which is less than -5. So Black will not play. If White plays first she gets -7+t, which is greater than -5, so she will not play, either. When t = 2, either player may play and get -5.

max(min(-4,-3-t),-5) is the value of the left wall of the thermograph, which represents the value for Black, playing first. And, as you show, when t = 0.1, it is -4. In fact, it is -4 when t < 1, -3-t when 1 < t < 2, and -5 when t > 2.

min(-7+t,-5) is the value of the right wall of the thermograph, which represents the value for White, playing first. When t < 2 it is -7+t, and when t > 2 it is -5.

Put the left and right wall together and you get the thermograph.

(Note that when t > 2, the value for each player, playing first, is -5, and both walls coincide in a vertical mast. -5 is the mean value of the position, aka the mast value.)

Es claro?

[Jeff[: Clearly I didn't communicate my confusion well enough. When I compute the value at t=0.1, my best reasoning tells me the value of the root node is -5.45. See above for how I derived that. But then I plugged in your formula and got -4. The two answers disagree. This means that my reasoning was wrong, but I can't see the flaw in my reasoning. Does that make sense? Can you see the flaw in the paragraph where I explain that the value of the root is -5.45?

Bill: No flaw in your reasoning. The question is what we are computing. When deriving the backed up values, I said, "Suppose that Left (Black) plays first. We get the following backed-up minimax values." You were trying to compute something else, the value of the root without regard for who plays first. That's different, as I explain below.

max(min(-4,-3-t),-5) is the minimax result, as a function of temperature (t), when Black has the move at the root.

min(-7+t,-5) is the minimax result, as a function of t, when White has the move at the root.

The root has a single value only when t >= 2, when these two functions are equal, and are equal to -5. There is no single value for the root when t = 0.1. At that temperature the result depends upon who has the move. The reason that there is a single value when t > 2 is that neither player will wish to play yet, so it does not matter who has the move. When t = 2, the result is -5, regardless of who plays first, so again it does not matter who has the move.

I hope that is clearer. :-)

Jeff: Much clearer. Sorry for taking a while to respond -- School's kickin my butt (JHU: Evolutionary Computation). My intent was to reply to your message with a general formula or algorithm that is mathematically precise, concise, and clear. When I do, I'll replace this comment with that, since that will be more interesting/useful.

Jeff: Here are my conclusions, after much deliberation. I came up with what seems like the simple way of figuring out the value at any node for any time. And you were right -- it has a lot to do with thermographs. Please feel free to move/edit them if they are too wordy and tedious. Please feel free to edit/promote them if they have value. Bill, thanks again for your patience in helping us understand these things.

Calculating value of a move in terms of global temperature

There are two ways I see to do this, depending on whether you prefer playing with graphs (for this, we use thermographs) or algebra (for this, we use piecewise functions). The two processes are really very similar, but different people think different ways.

To find the value for a given node, first you find the value of its left and right subtree. Keep looking further down the subtree until you find a place where the value of the position is the same, regardless of whose move it is or what the temperature is (the place in the game where both players would pass). The thermograph for that basic case is a vertical line at that value. The algebra is f(t)=v (t is temperature, f is the value for any given temperature).

Thermograph approach

So, now that you have the left and right subtree, how do you get the value of this move? For the thermograph method, plot the thermograph of the two subtrees both on the same graph. Each thermograph has two sides, a side facing toward the other thermograph and a side facing away. All we care about is the sides that are facing toward one another -- the outside half can be discarded/ignored. Now, skew (slide) the two graphs toward one another by T. Here's what this means in more detail, starting at the bottom (temperature=0):

For vertical lines, that means making them diagonal lines (45 degrees toward the other graph) keeping the height of the line (distance above temperature=0) the same (yes, this makes the line longer). For lines that are already diagonal, you'll notice they are currently diagonal away from the other subtree's thermograph. Make these lines vertical, again keeping the height the same.

Erase everything above the point where the two skewed thermographs intersect. Draw a vertical line going straight up from that intersection. Congratulations, you're done. Repeat until you've built up to the move you were looking for in the move tree.

Algebra approach

Each subtree has two value functions: one if it's black-to-move and the other if it's white-to-move. Each of these functions will be piecewise, divided at various values of t (except where the value is constant for all temperatures). Each value will look like n+t, n-t, or simply n. So for this subtree, you need to figure out two piecewise functions.

To figure out the black-to-move function, we will use the white-to-move function of black's subtree. Copy that function, except subtracting t from each piece (it's piecewise defined). Entries that look like n+t become n and entries that look like n become n-t. Do the same to figure out the the white-to-move: copy the black-to-move function of white's subtree, except adding t to each piece.

Placing these two piecewise functions side-by-side, find the value of t for which the two functions are equal. I do this by starting from the piece of each function representing the largest t values, setting those two pieces equal to one another, solving for t, and checking to be sure that t is in the range specified for each of the two pieces. If it isn't in the range, I move down to the next pair of pieces that have overlapping t ranges and repeat until I find a valid value for t. Example (for each, > means greater than or equal):

black-to-move= 6-t (for all t) white-to-move= t+3.5 (t>1.5) 5 (1.5>t>1) t+4 (1>t)

The top range is t>1.5 6-t = t+3.5 6-3.5 = 2t 2.5=2t t=1.25 This does not fit the range for white-to-move. The next range that the pieces overlap is 1.5>t>1 6-t=5 t=1 this is barely in the range, but it works.

Once you find the value of t at which the two intersect, find the value (call it v) at that temperature. Both black-to-move and white-to-move will give the same value for v. Add a piece to each of those functions that says the value is v for t>{that intersection t value}. Remove all the piece (or parts of pieces) from each function that this new piece replaces.

Congratulations, you're done. Repeat until you've built up to the move you were looking for in the move tree.