bug-gnubg
[Top][All Lists]

## Measuring the complexity of a position?

 From: Timothy Y. Chow Subject: Measuring the complexity of a position? Date: Tue, 18 Oct 2022 09:10:04 -0400 (EDT)

In chess, there have been some attempts to measure the "complexity" of a position. Guid and Bratko have written a couple of a papers that discuss the topic, and you can find a few other papers by using Google Scholar to find papers that cite these papers.
```
https://ailab.si/matej/doc/Using_Heuristic-Search_Based_Engines_for_Estimating_Human_Skill_at_Chess.pdf
https://en.chessbase.com/news/2006/world_champions2006.pdf

```
In a recent interview, Anish Giri explained his low "average centipawn loss" (the chess equivalent of backgammon's error rate) by saying that he prefers simple positions.
```
https://youtu.be/aGyXmSCkJ5s?t=247

```
About ten years ago, I took a stab at coming up with a way to measure how hard a position would be for a human player.
```
http://timothychow.net/cg/www.bgonline.org/forums/114010.html

To quote myself:

Let's say that Play A and Play B differ in character if the temperature
map of the opponent's replies are very different from each other. (How
to decide that two temperature maps are "very different" is not a
trivial problem but I think one could come up with a reasonable
metric.) Then a roll is probably difficult to play if there are several
ways to play it that (a) differ in character and (b) are within, say,
0.050 of each other.

```
The reason I said that it's not trivial to decide when two temperature maps are "very different" is that it is probably not enough to simply compare the temperature maps "coordinate by coordinate" in naive way. For example, maybe there are two main candidate plays, and one play gives the opponent 4's to hit and the other play gives the opponent 5's to hit, and the plays are very similar otherwise. "Coordinate by coordinate," the temperature maps look very different, but if you permute the dice rolls appropriately, then they line up nicely, and so are arguably not very different.
```
```
Also, something I didn't say above is that there should be an opportunity to blunder. If all plays have extremely similar equity then I would be inclined to call the position "simple," even if it's not obvious to a human that all the plays have extremely similar equity.
```
```
I think it would be an interesting study to implement some notion of complexity (to start with, one can gloss over the subtleties I mentioned above about determining when two temperature maps are very different, and use a more naive measure), and then analyze a large number of human games to see if (for example) there is a correlation between complexity and human mistakes. Unfortunately:
```
1. I don't have the programming chops to implement this idea, and

2. I don't know where to get a suitable database of games.

```
Problem 2 may be easier to solve---I suspect someone here can point me to a database. As for Problem 1, is anyone with the requisite programming skills interested in a collaboration? I have some ideas for how to get started with a complexity measure, but it will probably require some fine-tuning, depending on what the data say. If this project works out well, I think it could even lead to a publishable paper.
```
Tim

```