Measuring the complexity of a position?

[Timothy Y. Chow]

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