TU Darmstadt / ULB / TUprints

Improving research methods for problem solving: The example of Sudoku

Behrens, Thea (2024)
Improving research methods for problem solving: The example of Sudoku.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00027306
Ph.D. Thesis, Primary publication, Publisher's Version

[img] Text
tufte_PhD_thea.pdf
Copyright Information: In Copyright.

Download (6MB)
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Improving research methods for problem solving: The example of Sudoku
Language: English
Referees: Jäkel, Prof. Dr. Frank ; Kühnberger, Prof. Dr. Kai-Uwe
Date: 3 June 2024
Place of Publication: Darmstadt
Collation: 160 Seiten
Date of oral examination: 18 April 2024
DOI: 10.26083/tuprints-00027306
Abstract:

Responding flexibly to new rules or constraints and finding tactics on the fly to achieve arbitrary goals are hallmarks of human intelligence. They allow us to adapt to changes in the environment and to thrive under a wide variety of conditions. Studying the solution strategies in puzzles, i.e., the interaction with novel and arbitrary constraints, is a way to study aspects of these core human abilities. This thesis improves on traditional research methods in the area of problem solving by combining qualitative approaches and quantitative modeling, utilizing a broad range of modeling paradigms: production systems, choice models, and hierarchical Bayesian modeling. The "model organisms" on which we test our methods are digit-placement puzzles, most prominently, Sudoku. Since there are several basic tactics for approaching such puzzles, we can study tactic choice and the factors that might influence it.

We present a series of experiments in which participants fill the entire puzzle freely. Concurrent think-aloud protocols enable us to gain a thorough understanding of the tactics used by participants to fill each digit. The studies demonstrate that various digit-placement puzzles are solved using similar methods, and there are two distinct ways in which participants think about the constraints: cell-based and digit-based. Moreover, participants exhibit clear preferences for specific solution tactics, while also utilizing a diverse range of tactics beyond what is required to solve the puzzles. After analyzing data from more than 200 participants, we discover that preferences for tactics change with experience.

We then conduct experiments in which we limit our participants to filling in only one digit per puzzle. This experimental design allows us to control the applicable tactics for each trial. The response times from two experiments indicate that participants can be biased towards a particular tactic by task instructions and task requirements. Based on our experimental findings, we argue that previous research often used biasing task designs and therefore underestimated participants’ flexibility and overestimated the importance of a problem’s complexity. Furthermore, our experiments demonstrate that participants are able to switch to other tactics if their first attempt does not lead to a solution. We formalize the tactics in a process model and find that the data can only be adequately fitted by including the possibility of switching.

Following up on these experiments, we present a hierarchical Bayesian model for fitting the response times. We demonstrate how to use process models to analyze response time data and obtain parameter estimates that have a clear psychological interpretation. To estimate the duration of each processing step, we assume that each step has a random duration, modeled as draws from a gamma distribution. Modern probabilistic programming tools enable the fitting of Bayesian hierarchical models to data, allowing for the estimation of the duration of a step for each individual participant. This procedure can also be applied when the step count for each trial is latent, as in our Sudoku model. Our model allows us to estimate tactic choices in the Sudoku task for each participant individually. This approach can be applied to other response time experiments where a process model exists, bridging the gap between classical cognitive modeling and statistical inference.

We also demonstrate how problem solving traces can be analyzed statistically using classical production systems. While research on problem solving traditionally relies on think-aloud protocols in single participants, other research areas usually focus on statistical analyses of overt responses pooled over many participants. To obtain sufficient data for fitting quantitative models on the individual participant level, we introduce a new experimental interface which provides enough data to disambiguate rule selections without relying on labor-intensive methods such as the analysis of think-aloud protocols. To account for the probabilistic nature of rule selection, we use standard choice models, such as the Bradley-Terry-Luce model or the elimination-by-aspects model. The model fits confirm that, as expected, spatial and temporal factors influence rule selection in Sudoku. Through clustering, we find that our participants can be divided into four groups with similar rule preferences.

In summary, we believe that a broad range of methodological approaches is necessary in order to make progress in problem solving research. Therefore, this thesis introduces and uses several experimental designs as well as analysis tools and modeling approaches to contribute to understanding how humans solve digit-placement tasks. We show that there is great potential in the combination of these methods to further improve our understanding of general problem solving.

Alternative Abstract:
Alternative AbstractLanguage

Flexibel auf neue Regeln oder Einschränkungen zu reagieren und spontan Taktiken zu finden, um beliebige Ziele zu erreichen, sind Markenzeichen menschlicher Intelligenz. Sie ermöglichen es uns, uns an Veränderungen in der Umwelt anzupassen und unter vielen unterschiedlichen Bedingungen erfolgreich zu sein. Das Beobachten von Lösungsstrategien in Rätseln, also die Interaktion mit neuartigen und willkürlichen Beschränkungen, ist ein Weg, Aspekte dieser zentralen menschlichen Fähigkeiten zu erforschen. Diese Arbeit verbessert die traditionellen Forschungsmethoden im Bereich des Problemlösens, indem sie qualitative Ansätze mit quantitativer Modellierung kombiniert und dabei eine Vielzahl von Modellierungsparadigmen verwendet: Produktionssysteme, Entscheidungsmodelle und hierarchische Bayes'sche Modellierung. Die "Modellorganismen", an denen wir unsere Methoden testen, sind Zahlenrätsel, insbesondere Sudoku. Da es mehrere grundlegende Taktiken gibt, um solche Rätseln zu lösen, können wir die Wahl der Taktik und die Faktoren, die diese Wahl beeinflussen könnten, untersuchen.

Wir stellen eine Reihe von Experimenten vor, bei denen die Probanden das gesamte Puzzle frei ausfüllen. Think-Aloud-Protokolle ermöglichen es uns, ein gründliches Verständnis der Taktiken zu erlangen, die die Probanden beim Ausfüllen der einzelnen Ziffern anwenden. Die Studien zeigen, dass verschiedene Ziffernrätsel mit ähnlichen Methoden gelöst werden und dass es zwei verschiedene Arten gibt, wie die Probanden über die Beschränkungen nachdenken: zellenbasiert und ziffernbasiert. Darüber hinaus zeigen die Probanden klare Präferenzen für bestimmte Lösungstaktiken, während sie gleichzeitig eine Vielzahl von Taktiken nutzen, die über das hinausgehen, was zur Lösung der Rätsel erforderlich ist. Durch die Analyse der Daten von mehr als 200 Probanden stellen wir fest, dass sich die Präferenzen für Taktiken mit durch Erfahrung ändern.

Anschließend präsentieren wir Experimente, in denen wir die Probanden darauf beschränken, nur eine Ziffer pro Rätsel auszufüllen. Diese Versuchsanordnung ermöglicht es uns, die anwendbaren Taktiken für jeden Versuch zu kontrollieren. Die Reaktionszeiten aus zwei Experimenten deuten darauf hin, dass die Probanden durch Aufgabenstellung und Aufgabenanforderungen beeinflusst werden können bestimmte Taktiken zu nutzen. Auf Grundlage unserer experimentellen Ergebnisse argumentieren wir, dass frühere Forschung häufig einseitige Aufgabenstellungen verwendete und daher die Flexibilität der Probanden unterschätzte und die Bedeutung der Komplexität eines Problems überschätzte. Darüber hinaus zeigen unsere Experimente, dass die Probanden in der Lage sind, zu anderen Taktiken zu wechseln, wenn ihr erster Ansatz nicht zu einer Lösung führt. Wir formalisieren die Taktiken in einem Prozessmodell und stellen fest, dass die Daten nur dann adäquat abgebildet werden können, wenn die Möglichkeit des Taktik-Wechselns berücksichtigt wird.

Im Anschluss an diese Experimente stellen wir ein hierarchisches Bayes'sches Modell zum Fitten der Reaktionszeiten vor. Wir zeigen, wie Prozessmodelle zur Analyse von Reaktionszeitdaten verwendet werden können um Parameterschätzungen zu erhalten, die eine klare psychologische Interpretation zulassen. Um die Dauer der einzelnen Verarbeitungsschritte zu schätzen, gehen wir davon aus, dass jeder Schritt eine zufällige Dauer hat, die als Ziehung aus einer Gamma-Verteilung modelliert wird. Moderne probabilistische Programmiertools ermöglichen das Fitten von Bayes'schen hierarchischen Modellen an die Daten, was die Schätzung der Dauer eines Schritts für jeden einzelnen Probanden ermöglicht. Dieses Verfahren kann auch angewendet werden, wenn die Schrittanzahl für jeden Versuch latent ist, wie in unserem Sudoku-Modell. Unser Modell ermöglicht es uns, die Taktik-Präferenzen im Sudoku-Experiment für jeden Probanden individuell zu schätzen. Dieser Ansatz kann auf andere Reaktionszeitexperimente angewandt werden, bei denen ein Prozessmodell existiert, und schließt die Lücke zwischen klassischer kognitiver Modellierung und statistischer Inferenz.

Wir zeigen auch, wie Lösungswege mit klassischen Produktionssystemen statistisch analysiert werden können. Während sich die Forschung zum Problemlösen traditionell auf Think-Aloud-Protokolle einzelner Probanden stützt, konzentrieren sich andere Forschungsbereiche in der Regel auf statistische Analysen expliziter Antworten, die über viele Probanden gemittelt werden. Um genügend Daten für das Fitten quantitativer Modelle auf der Ebene einzelner Probanden zu erhalten, führen wir ein neues Experimental-Design ein, welches genügend detaillierte Daten liefert, um die Regelauswahl zu unterscheiden, ohne auf arbeitsintensive Methoden wie die Analyse von Think-Aloud-Protokollen angewiesen zu sein. Um die probabilistische Natur der Regelauswahl zu berücksichtigen, verwenden wir Auswahlmodelle, wie das Bradley-Terry-Luce-Modell oder das Elimination-By-Aspect-Modell. Die Modell-Fits bestätigen, dass räumliche und zeitliche Faktoren die Regelauswahl bei Sudoku beeinflussen. Durch Clustering stellen wir fest, dass unsere Probanden in vier Gruppen mit ähnlichen Regelpräferenzen unterteilt werden können.

Zusammenfassend ist zu sagen, dass ein breites Spektrum an methodischen Ansätzen notwendig ist, um Fortschritte in der Problemlösungsforschung zu erzielen. Daher werden in dieser Arbeit verschiedene experimentelle Designs sowie Analysewerkzeuge und Modellierungsansätze vorgestellt und verwendet, um zu verstehen, wie Menschen Ziffernrätsel lösen. Wir zeigen, dass in der Kombination dieser Methoden ein großes Potenzial liegt, um unser Verständnis des allgemeinen Problemlösens weiter zu verbessern.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-273067
Classification DDC: 100 Philosophy and psychology > 150 Psychology
Divisions: 03 Department of Human Sciences > Institute for Psychology > Models of Higher Cognition
Date Deposited: 03 Jun 2024 11:15
Last Modified: 12 Jun 2024 06:17
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/27306
PPN: 518981177
Export:
Actions (login required)
View Item View Item