What is the theoretical value of the first move of a game?

[RobertJasiek]

Computers do not study all positions but a small sample of positions.

There might or might not be a correlation between computer evaluation of moves and human move values.

Humans can calculate or estimate move values for endgame moves, endgame-like moves, the first move and maybe other moves with particular circustances. Humans, however, still cannot only assess all moves by move values because some aspects, such as influence, cannot always be converted to parts of move values. Therefore, we still cannot relate move values to computer values for all moves.

Once more: computers do not use move values.

[Bill Spight]

Oops, I have to clarify my point concerning computer vs human play.
Taking aside the deep analysis made by a computer or a human through a vast tree of variants, my understanding is the following.
Let's suppose it is black to play.
A computer evaluates all the positions reached by a black move and chooses the best move according to these evaluations. If you substract to these evluations the evaluation of the currtent position you can see that the choice made by the computer can be seen as based on the value of each black move (but of course the computer has not to do explicitly these substractions).
Humans may act strictly as a computer but in order to choose their move they also can take into account another approach to gather some more information: they imagine they pass and they find the best white move. Using such information they can return to the computer method in order to definitely chosose their move. In that case, beside the move evaluation made by the computer the human add something like a swing evaluation in order to have a better understanding of the position.
To my knowledge I don't think a computer improve its analysis by finding the best white move when the pass move looks completetly stupid.
So my conclusion is the following:
Computer use basically "move values" though humans may add some swing values to improve their analysis.

Instead of talking about humans and computers let me talk about two different human theories of evaluating games and nodes in a game tree. Suppose that we have a game in which the players take turns. One player, say, Black, makes a move and then the other player, White, makes a move, then Black, then White, and so on. At each node of the game tree only one player can move. Each player tries to maximize the result of her play. From the standpoint of Black, White is trying to minimize Black's result, and vice versa, so the term, minimax, is used to describe the evaluation of these nodes. At the end of the search tree we have leaf nodes, which have a well defined value, or score. In go a win by ½ pt. is as good as a win by 35½ pts., so we can just evaluate a win as +1, a loss as -1, and a tie, if we have those, as 0. Now let's back up one move from the leaf nodes. Suppose that Black is to play from that node. Then she will move to one of the leaf nodes that maximizes her result, and we evaluate that node as the maximum value of its children. Similarly, if White is to play from a node, we back up the minimum value for Black of the children of that node as its value. Note that by minimax evaluation if you start at node A and move to node B, if your move is correct the difference between the values of A and B is zero. If you make a mistake, then the value of node B is less than that of node A. A move cannot gain anything, it can only lose. Economists call such a loss an opportunity cost.

In the go endgame, however, the board breaks up into independent regions (except, perhaps, in a ko fight), each of which may be considered as a game. Although the players take turns on the whole board, they do not have to take turns in each game. This leads to a different kind of game tree, where each player can potentially play from each node of the tree — except leaf nodes, OC. We cannot simply evaluate a node by backing up the value of one of its children. In fact, it is not exactly obvious how to evaluate it. But go players did figure out a way, two centuries or more ago. Obviously, if a node (position) has a local score, that is its value. Furthermore, if a position is a simple gote, where Black can move to a position with a score and White can also move to a position with a score, it makes sense to evaluate the original position as the average of those scores. It has an average value. Voila! Sente positions are less obvious, but a kind of backup was used, not from the immediate position after the sente play, but from the position after the (correct) reply. Hence the saying, Sente gains nothing. Double sente positions are even less obvious, and go players never figured out how evaluate them, with the exception of a few players like myself, back in the 1970s. Even so, I could not get Go World to publish my article about double sente. {shrug} Even today, O Meien does not talk about double sente. Back to the story. Now that go players could evaluate local positions by averaging gote values or by backing up sente values, plays normally make gains. At least, gote and reverse sente plays do. Also, the difference between moving to a local score of 30 is better than moving to a local score of 28. That is because no local score determines by itself the result of the game. A local score of 28 may be enough to win the game, but a local score of 30 may be necessary, and gives in general a better chance of doing so.

So we have two different types of games, two different types of game trees, and two different types of evaluation.

[Gérard TAILLE]

That's very clear for me Bill (I worked for lot of years on a draughts program and it's not difficult for me to understand what you mean concerning tree exploration).
Dividing the goban into independant regions each one considered as a small game is a very interesting idea but only in the very final stage of the game.
Typically, when it remains area where different possbilities may exist then we cannot handled this area as an independant region.
For example:

$$B
$$ -------------------
$$ | . . . . . . . . .
$$ | . a b . . . . . .
$$ | . O X X . . . . .
$$ | . . O X X X X X X
$$ | . O O . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .

Click Here To Show Diagram Code

[go]$$B
$$ -------------------
$$ | . . . . . . . . .
$$ | . a b . . . . . .
$$ | . O X X . . . . .
$$ | . . O X X X X X X
$$ | . O O . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .[/go]

In the diagram above, when you analyse a white move, how can you choose the correct move (a ot b) whithout knowing what will happen in the other regions of the goban.

Anyway I effectively can see the interest of using different evaluations depending on the circumstancies.
BTW do you think that computers may use also different evaluation techniques depending of the circumstancies (for instance in the example you mentionnened when independant areas can be identified)?

[John Fairbairn]

O Meien does not talk about double sente.

Eh? He may not rabbit on about it but he does mention it, so it's in his mind. Example 3 Diagram 5: Black 1 is double sente and must not be overlooked. Example 4 Diagram 5: White can play the double sente of 1 and 3, which I felt very smug about.

[RobertJasiek]

"computers may use also different evaluation techniques depending of the circumstancies"

Since when might programmers not be free?:)

[Knotwilg]

There are two aspects to the answer:
1. defining "the theoretical value of the first move of the game"
2. computing or estimating it

1. there's a lot between the quotation marks; possible rewordings
a) "a fair compensation for moving second"
b) "the difference between black moving first and white moving first"
c) "the contribution of the first move to the final score"

2. we know a few things:
a) this is the definition of komi and it has historically shifted from 5,5 to 7,5 while also maybe being dependent on the rule set used and with (or without) the goal to avoid a draw. It's the expected score of a game without such compensation, or rather the mean of the normal distribution of the results of a large number of games played. Let's agree there's a 90% probability that a fair compensation is between 6 and 8
b) this difference is twice the number of points under a)
c) this is probably what is meant here but the answer isn't different than a) or b) (depending on the question). The worst one can do at move 1 is passing (hypothesis not tested: maybe playing 1-1 is worse). In the course of the game, the impact of a move on the final score can change a lot. This is evoked by the concept "temperature". Making life for a large group or not can make the end result differ by dozens of points (the are is "hot"). After having made life, no such move exists, not in the vicinity of the group (local temperature drops) or anywhere (global temperature drops). At move 1 however, temperature is pretty low. The difference between playing or not playing is about 14 points.

[Bill Spight]

O Meien does not talk about double sente.

Eh? He may not rabbit on about it but he does mention it, so it's in his mind. Example 3 Diagram 5: Black 1 is double sente and must not be overlooked. Example 4 Diagram 5: White can play the double sente of 1 and 3, which I felt very smug about.

Thanks for reminding me. I had evaluation in mind. In that context he doesn't even mention sente, much less double sente.

[Bill Spight]

That's very clear for me Bill (I worked for lot of years on a draughts program and it's not difficult for me to understand what you mean concerning tree exploration).
Dividing the goban into independant regions each one considered as a small game is a very interesting idea but only in the very final stage of the game.
Typically, when it remains area where different possbilities may exist then we cannot handled this area as an independant region.
For example:

$$B
$$ -------------------
$$ | . . . . . . . . .
$$ | . a b . . . . . .
$$ | . O X X . . . . .
$$ | . . O X X X X X X
$$ | . O O . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .

Click Here To Show Diagram Code

[go]$$B
$$ -------------------
$$ | . . . . . . . . .
$$ | . a b . . . . . .
$$ | . O X X . . . . .
$$ | . . O X X X X X X
$$ | . O O . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .
$$ | . O . . . . . . .[/go]

In the diagram above, when you analyse a white move, how can you choose the correct move (a ot b) whithout knowing what will happen in the other regions of the goban.

For evaluation purposes the rest of the board is represented by a single parameter, t, called the temperature of the environment, or the ambient temperature. If you have more information you can incorporate that as part of the game. (Games can be added together.) At sufficiently high temperature neither player will play in this game, with correct play. As you reduce the temperature, at some point both players will be indifferent between playing locally or playing elsewhere. That temperature is the average gain of this game for a gote play or reverse sente play.

At lower temperatures the payoff for each player moving first is determined by minimax at that temperature, with the proviso that the second player moves last. Let me illustrate with a simple gote and a simple sente.

Suppose that there is a simple gote such that whoever plays first gets a local score of 10 pts. Let's say that the ambient temperature is 14. Now if Black takes the gote White replies on the rest of the board (in the environment). Black has a score of 10, from which we subtract 14 for a net score of -4. Whether that is good or bad we don't know yet. If Black plays in the environment and White takes the gote the result is a net score of 14 - 10 = 4, which is plainly better for Black, so Black plays elsewhere. The same goes for White. Now suppose that the ambient temperature is 10. If either player takes the gote and the other player replies in the environment, the net score is 0, and the same is true if the first player plays in the environment first. Each player is indifferent between playing in the game and playing in the environment. So a play in the gote gains 10 pts. We can find t by solving the equation, 10 - t = t - 10. We have also determined the average value of the gote position, which is 0.

Now suppose that the ambient temperature is 5. An unusual situation, but there we are. If Black plays first the result at temperature 5 is 10 - 5 = 5, as Black will prefer to take the gote. Similarly, the result if White plays first will be -5 from Black's point of view. In a more complicated position Black might have a choice of plays, one of which might have a better result for Black at temperature 5, in which case she will play it. (OC, we have simplified the situation by using a single parameter for the rest of the board. This theory is for heuristics.)

Now let's look at a Black sente. Suppose that Black to play can move to the simple gote above, and that White to play can move to a position with a local score of -15, from Black's point of view. Obviously, above a temperature of 10 neither play will play. What if the temperature is 8? If Black plays first to the gote, we already know that White will reply in the gote instead of the environment, so the result will be -10 for Black. If White plays first locally, the result will be -15 + 8 = -7, which is better for Black than -10, and worse for White. White will play in the environment. At temperatures below 10 Black can guarantee a result of -10 by playing locally. She can play locally, or not, as she pleases, since White will not play the reverse sente. Now let the temperature be 5. Black to play still gets -10, while if White plays locally the result will be -15 + 5 = -10. At this temperature both players are indifferent between playing locally or in the environment. The value of the position is -10 and the gain from the reverse sente is 5. Edit: We could have found this by solving the equation, -10 = -15 + t.

This is not the traditional way of finding these values. The method is mine, but it is based upon thermography, which is presented in Conway's On Numbers and Games (ONAG), as well as Winning Ways by Berlekamp, Conway, and Guy. Berlekamp extended thermography to cover kos, and I redefined it in 1998 to cover multiple kos. This method is a simplification of my method back then. The ONAG version uses the idea of tax instead of the value of plays elsewhere.

On the question of the choice of plays, Robert Jasiek and I have discussed that often here on L19. Those discussions will probably show up if you search for thermography.

Anyway I effectively can see the interest of using different evaluations depending on the circumstancies.
BTW do you think that computers may use also different evaluation techniques depending of the circumstancies (for instance in the example you mentionnened when independant areas can be identified)?

Plainly there is a value to breaking down the problem of play into smaller problems. It is not so easy to do rigorously, but Martin Mueller has tackled the problem, although I don't know of anything recent.

[Gérard TAILLE]

$$B
$$ -------------------
$$ | X b X X X a X . .
$$ | X O X X X O X. .
$$ | X O X X O O X . .
$$ | O O O O O O X X X
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$

Click Here To Show Diagram Code

[go]$$B
$$ -------------------
$$ | X b X X X a X . .
$$ | X O X X X O X. .
$$ | X O X X O O X . .
$$ | O O O O O O X X X
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$[/go]

It is not easy for to understand how the environment can me summarized by a sigle number t (for temperture). Can we take an example in order for me to understand your point.

Let's take as the local region the upper left corner in the diagram above.
First of all I try to count the position:
If it is white to play, white plays "a" and the score (for black point of view) is -23.
If is is black to play, black plays "a" and we reach a position where white or black can then play "b".
if now black plays "b" the score is +0
and if now white plays "b" the score is -6
As a consequence after black "a" the position is estimated -3 (the average value between +0 and -6)
Finally the initial position is evaluate -13 (the average value between -23 and -3).
On average the "a" move earns 10 points and then the "b" move earns 3 points.

Now let me take two scenarios for the environment:
S1 : four gote areas which earn : 11, 8, 5 and 2 points
S2 : five gote area which earns : 10, 8, 6, 4, 2 points

In the S1 scenario black has to play in the environment but in the S2 scenario black has to play locally.
I do not know what is the temperature of S1 or S2 but my feeling is that, depending of the temperature definition, I will probably be able to build two different environments with the same temperature and different play for black.

May be I could agree temperature may be a great "help" to guess the correct move but in any case you have to read a great part of the yose, haven't you?
In my example the "standard" method to guess the correct move is "simply" to estimate the local situation (here 10 points) and to verify this guess by reading the yose. For the time beeing I do nont really see the advantage of the temperature notion. I suspect my example is not that significant for the temperature notion.

[RobertJasiek]

Endgame positions can be studied during the early endgame with temperature of the environment or during the late endgame when the correct solution can be found.

During the early endgame and at a moment of quiescence, one can make the assumption of linearly decreasing values of simple local gote endgames in the environment. The largest such gote is said to have the temperature T as its value. We have proven that T/2 is a good approximation for the value of starting play in the global environment. Therefore, the temperature is useful.

[Gérard TAILLE]

Robert, I understand that T/2 is quite good approximation.
In my scenarios S1 and S2 I imagine you can calculate the exact value of this temperature. If my understanding is correct this temperature is here equal to 6 but I am not completly sure.

[Bill Spight]

$$B
$$ -------------------
$$ | X b X X X a X . .
$$ | X O X X X O X. .
$$ | X O X X O O X . .
$$ | O O O O O O X X X
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$

Click Here To Show Diagram Code

[go]$$B
$$ -------------------
$$ | X b X X X a X . .
$$ | X O X X X O X. .
$$ | X O X X O O X . .
$$ | O O O O O O X X X
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$ | . . . . . . . . .
$$[/go]

It is not easy for to understand how the environment can me summarized by a sigle number t (for temperture). Can we take an example in order for me to understand your point.

The main point is that the theory is heuristic. As I am sure you know, the best play is not always the biggest play.

The other point is that games add and subtract. This is the basis for combinatorial game theory (CGT). Go players did not come up with that idea, but they do realize that the interaction between independent positions matters, even without ko. The thing is, then, that if you have information about other games that is relevant, it is not part of the environment. It is foreground knowledge, not background. (BTW, I came up with the idea of the environment independently, long before I heard about CGT, just from studying go endgames. )

Let's take as the local region the upper left corner in the diagram above.
First of all I try to count the position:
If it is white to play, white plays "a" and the score (for black point of view) is -23.
If is is black to play, black plays "a" and we reach a position where white or black can then play "b".
if now black plays "b" the score is +0
and if now white plays "b" the score is -6
As a consequence after black "a" the position is estimated -3 (the average value between +0 and -6)
Finally the initial position is evaluate -13 (the average value between -23 and -3).
On average the "a" move earns 10 points and then the "b" move earns 3 points.

Right.

Furthermore, if the ambient temperature is less than 3 and Black plays first, White replies locally. Even though this is a gote position, Black can play with sente under those conditions.

Now let me take two scenarios for the environment:
S1 : four gote areas which earn : 11, 8, 5 and 2 points
S2 : five gote area which earns : 10, 8, 6, 4, 2 points

The term, environment, has more than one sense. For evaluation purposes we only care about its temperature. But if we want to include more information, then we add together all the other areas of interest to the original game to get a new game.

In the S1 scenario black has to play in the environment but in the S2 scenario black has to play locally.
I do not know what is the temperature of S1 or S2 but my feeling is that, depending of the temperature definition, I will probably be able to build two different environments with the same temperature and different play for black.

The temperature of S1 is 11, the temperature of S2 is 10. Your second statement is true, because the theory is heuristic. It's not always right to play the averages.

For instance, suppose that your original position plus a simple gote with an average value of 0 in which a play gains 11 pts. are the only unplayed positions left on the board with Black to play. Even though Black's play gains only 10 pts. in your original position Black should play there. Then after White replies in the other position, Black can take the last play for an additional 3 pts. Black's total gain is then 10 - 11 + 3 = 2 pts. instead of 11 - 10 = 1 pt.

Note that this calculation is at temperature 0. If we include an environment for the combined game, Black's total gain at temperature t when she takes the 10 pt. play first is 2 - t pts. That is better, on average, than taking the 11 pt. play first when 2 - t > 1, i.e., when 1 > t. So above temperature 1 Black's average gain is better by taking the 11 pt. gote.

May be I could agree temperature may be a great "help" to guess the correct move but in any case you have to read a great part of the yose, haven't you?

The theory gives you a good guess to the best play in most circumstances. That's why go players came up with it in the first place. Tristan Cazenave has even done some research on the effectiveness of always playing the biggest play in actual games. It works well. Big duh.

But also, when you are reading extensively, the theory gives you a good first sequence of plays to read.

In my example the "standard" method to guess the correct move is "simply" to estimate the local situation (here 10 points) and to verify this guess by reading the yose. For the time beeing I do nont really see the advantage of the temperature notion. I suspect my example is not that significant for the temperature notion.

In a real game the ambient temperature is usually close to that of the gain from taking the biggest play. However, there are occasions when it is rather less. In such cases, as my example of the combined game illustrates, you may be able to figure out when the biggest play is probably not best.

[Gérard TAILLE]

Trying to understand what you said I have now a difficulty:

In your previous post you wrote :

Suppose that there is a simple gote such that whoever plays first gets a local score of 10 pts. Let's say that the ambient temperature is 14. Now if Black takes the gote White replies on the rest of the board (in the environment). Black has a score of 10, from which we subtract 14 for a net score of -4. Whether that is good or bad we don't know yet. If Black plays in the environment and White takes the gote the result is a net score of 14 - 10 = 4, which is plainly better for Black, so Black plays elsewhere. The same goes for White.

Let's take this local score of 10 points and the environment made of 14 gote areas with values 14, 13, 12 .., 3, 2, 1. If I understand your last post the ambiant temperature for this environment is equal to the biggest gote area t = 14.
If now black plays first the local 10 points it appears to me that black will get a net score of 10 - 14/2 = +3 and not 10 - 14 = -4 ?

Second example. We saw that, by playing the first move of a game, black will earn 14 points. Does that mean the temperature is 14 ? Finally we know that the result of the game is expected to be 7 points for black. My conclusion : starting from a (quiet?) position in which the evaluation is 0 (an empty board is only a trivial example) if it is black to play and if the temperature is equal to t then the expected result is about equal to t/2.
Is it the idea?

[Bill Spight]

Trying to understand what you said I have now a difficulty:

In your previous post you wrote :

Suppose that there is a simple gote such that whoever plays first gets a local score of 10 pts. Let's say that the ambient temperature is 14. Now if Black takes the gote White replies on the rest of the board (in the environment). Black has a score of 10, from which we subtract 14 for a net score of -4. Whether that is good or bad we don't know yet. If Black plays in the environment and White takes the gote the result is a net score of 14 - 10 = 4, which is plainly better for Black, so Black plays elsewhere. The same goes for White.

Let's take this local score of 10 points and the environment made of 14 gote areas with values 14, 13, 12 .., 3, 2, 1. If I understand your last post the ambiant temperature for this environment is equal to the biggest gote area t = 14.
If now black plays first the local 10 points it appears to me that black will get a net score of 10 - 14/2 = +3 and not 10 - 14 = -4 ?

What is missing from the quote is something I said earlier, which is that we find the minimax result at the ambient temperature, with the second player playing last, not the result at the end of play. In my 1998 paper I did use the result at the end of play, but doing so required a bit of cleverness. The current method is simpler.

If we start from a position that has a certain value and one player makes a play that gains x and then the second player makes a play that gains x, the new position has the same value as before. So if Black plays locally and gains 10 pts. and then White plays in the environment and gains 14 pts., the result is a net loss of 4 pts. for Black. True, if we played everything out to the end, Black might gain 3 pts. instead of losing 4 pts., but Black would have done better to play in the environment and get a final gain of 7 pts. Anyway, sticking to the current temperature simplifies things.

Second example. We saw that, by playing the first move of a game, black will earn 14 points. Does that mean the temperature is 14 ? Finally we know that the result of the game is expected to be 7 points for black. My conclusion : starting from a (quiet?) position in which the evaluation is 0 (an empty board is only a trivial example) if it is black to play and if the temperature is equal to t then the expected result is about equal to t/2.
Is it the idea?

I suppose that you are talking about the first play on an empty 19x19 board. Well, we guess that the first move gains around 14 pts., based on komi. Anyway, whatever it gains on average is the temperature of the empty board. Now, if the drops in temperature of the whole board, except for sente sequences, are approximately uniformly small, then the expected gain from playing first at temperature t is t/2. That seems to usually be the case.

An exception is temperature 1 at territory scoring. Fairly often the effective temperature drop is from 1 to 0, which is a large drop by comparison with the typical drop at other temperatures. Sometimes you can take advantage of that drop by getting the last play at temperature 1. Also, ko fights can keep the temperature elevated, so that winning the ko happens before a significant drop in temperature.

[RobertJasiek]

Bill, I lost track. What is your current method and why is it simpler than your 1998 paper?