Team: 45
School: Santa Fe High
Area of Science: Information Theory
Interim: Team Number: 045
School Name: Santa Fe High School
Area of Science: Information Theory
Project Title: Entropy in Chess
Sponsoring Teacher: Brian Smith
Problem Definition:
Information theory deals with the quantification or storage of information, and measures information content in the form of entropy. So, a coin flip — which only has two possible outcomes — would provide less information, thus, lower entropy, than that of a dice roll with three times the number of outcomes. However, despite the fact that chess is a game that has perfect information for both players(both players have exact knowledge of the board state) and has been investigated using combinatorial game theory, our group hopes to quantify information trends and different game states using information theory to gain better insight into the mechanics of chess.
Problem Solution:
Our group hopes to aggregate hundreds of games of chess to find trends in how information changes throughout the game. We have done this assuming all moves are equiprobable, and we hope to create another model with weighted move probabilities in order to see a more realistic range of information content values for a game of chess. In doing so, we hope to analyze this data in order to quantify how players impact the entropy of the game and how these entropy values can predict the eventual outcome of said game.
Problem Progress:
Currently we have a completed python script that takes a Portable Game Notation file (a file that stores and organizes the moves of the chess game along with other metadata) and separates it into each respective game. Once the script has separated each game, it writes each game to a new pgn file, without losing the metadata. We have another program that can read in any number of these game files whereupon it subsequently plays out the events of each pgn file while calculating the conditional and Shannonian entropies at every single move. Our program then will write the move that occurred, the Shannon entropy, the conditional entropy, and many other statistics to an output file. Subsequently, this output file is plotted as a scatter plot, along with the line of best fit. We have run our program on the 2021 chess world championship games and found a negative slope on these linear regressions which points to the overall information content of the game decreasing at high level play. We hope to make another model which completes this calculation with weighted probabilities for the chess moves of each player, based on what are the better moves as determined by a chess engine.
Problem Results:
Our calculation for Shannon entropy has shown that the more moves or options a player has the greater the entropy. We also have found that information tends to decrease throughout a chess game. After further tuning and eventual completion of our model, we hope to have found broader informational trends that can be applied to other games. These may also have a larger impact on game theory as a whole. We think that these trends could be used in more than just chess and could be applied in real-world scenarios — especially those of game engine design and or information theory’s application to games. After isolating and calculating the entropy of each player, we expect to find that the winning player has much higher entropy and that the losing player has waning entropy as the game progresses until they are eventually in checkmate.
Citations:
“Elements of Information Theory†by Joy A. Thomas and Thomas M. Cover
“Papaâ€, 2021 January 31, https://www.chessprogramming.org/Papa
“Chess PGN (Portable Game Notation)â€, 2021 January 31, https://www.chess.com/terms/chess-pgn
“Information Theoryâ€, 2021 January 31, https://en.wikipedia.org/wiki/Information_theory
“The Game Theory of Chessâ€, 2021 January 31, https://tidingsmedia.org/blog/the-game-theory-of-chess
Team Members:
Armando Martinez-Brito
Aengus McGuinness
William Barral
Roman Nappi
Sponsoring Teacher: Brian Smith