CGTLife Points Values
KarlKnechtel: On SL we have already seen the application of combinatorial game theory to several aspects of Go, mostly to do with raw point counts (see temperature, numbers, infinitesimals and so on... or just go check out the entire CGT path). CGT also applies to eyespace values; and recently, an effort has been made to assign CGT values of connections.
I think this gives us the necessary ingredients to try out CGT techniques in evaluating overall gameplay. Normally CGT is only applied to the study of "local games" (i.e. it is really only relevant in yose), but I am suggesting, basically, that we use the CGT connection evaluation to account for coupling effect.
This is a rough sketch of the algorithm I have in mind, for an evaluation function for one player's stones:
- Assign CGT values to each connected string of same-colour stones on the board. For each group the following values are needed:
- an eyespace value
- a point value associated with the group (likely, two points per stone, plus two points per point surrounded - CGT comes in here in determining how much space is "surrounded")
- possibly, a liberty value.
- Assign a connection CGT value to each pair of strings. This produces a "CGT connection graph". Each node here is a string on the goban; each edge represents a connection which does not use stones in any string besides the ones being connected. The graph will need some modifications before the next step:
- Pruning, to ignore tiny connections between distant groups.
- Possibly the introduction of some negative values to account for connection-coupling effects. I.e., two two-space jumps may individually be secure in the local situation, but the threat to disconnect one may disconnect the other.
- A limit (1) on the total connection value between any pair of nodes.
- Possibly, an eyespace and/or point value associated with making the connection (e.g. there's a small chance of making an eye within a BambooJoint).
We evaluate the total connection value between two nodes as the sum over all paths between the nodes, of the products of values along those paths.
- Now that we have a single CGT connection graph, with each node labelled with a CGT connection value: Generate the power set of graphs using all nodes and some subset of edges. Call this the candidate connection graph set - CCGS. (I.e.: if there are ``m`` nodes and ``n`` (which is `` O(m^2) `` in worst case) edges, there are ``2^n`` graphs in the set. Each is generated by either including or not including each edge, and including every node.) Unfortunately I can't really draw a good diagram of this with the SL diagrams. :/ For each graph in the set, assign a likelihood (not the best term, since it may be negative if negative connection values are in use as described above) equal to the product, for all edges in this graph, of the corresponding CGT connection values on the original CGT connection graph. (The edges in the CCGS are not labelled.)
This is the real tricky part: This is going to be, at worst, `` O(2^(m^2)) `` for ``m`` strings, the way I've described it. Some simplifications are definitely needed.
- For each graph in the CCGS, consider each connected set of nodes (which represent strings on the goban, remember) as a super-string. Superstrings with a CGT eyespace value `` >= 2 ``, or whose eyespace and liberty CGT values will allow them to win a semeai which in turn gives them the needed eyespace value (that's another tricky part), are considered alive, and count their point value. Other superstrings count zero, or possibly a negative value associated with the death of each string in the superstring (not sure). This gives a point value for this candidate connection graph.
- Finally, the whole board value for the one player is the weighted sum of the values over all members of the CCGS (weighted by the likelihood).
Once we have that, we are using WholeBoardConnectionTheory; we can (I think) write programs with a sense of WholeBoardThinking, and apply the usual minimax business. We can consider the 'net score' as (black whole board value - white whole board value), and use minimax to select the move which yields the best improvement in board evaluation. Of course, we still need to prune the tree, and make the evaluation fast. This is way more complex than brute-forcing chess... :)