Generalized Entropy and Solution Information for Measuring Puzzle Difficulty

• Author / Creator

  Shen, Junwen

• Metrics for problem difficulty are used by many puzzle generation algorithms, as well as by adaptive algorithms that are expected to provide players with the puzzles at the correct level of difficulty. A recently proposed general metric, puzzle entropy, combines an analysis of game mechanics with a model of player knowledge in the form of inference rules to predict problem difficulty. The entropy of a puzzle is the amount of information required, given a player’s knowledge about the puzzle, to describe a solution to a puzzle. This thesis generalizes the concepts of puzzle entropy and solution information, providing a better foundation for the previous work and creating new algorithms, Minimum Solution Information and Total Solution Information. While functionally similar to past work, the new algorithms allow knowledge about a puzzle to be represented as a policy. We then evaluate the impact of inference rules, policies, and player knowledge in the 2016 game The Witness.

• Subjects / Keywords

  • Puzzle Difficulty Estimation
  • Information Entropy
  • Puzzle Games
  • Heuristic Search
  • Witness Puzzle

• Graduation date

  Fall 2024

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-rzds-5t46

• License

  This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.