Computer-based estimation of the difficulty of chess tactical problems : bachelor's thesis

Stoiljkovikj, Simon (author), Guid, Matej (mentor)

In intelligent tutoring systems, it is important for the system to understand how difficult a problem is for the student. However, it is an open question how to automatically assess such difficulty. The aim of our research is to find formalized measures of difficulty that could be used in automated assessment of the difficulty of a mental task for a human. We present a computational approach to estimating the difficulty of problems in which the difficulty arises from the combinatorial complexity of problems where a search among alternatives is required. Our approach is based on a computer heuristic search for building search trees that are “meaningful” from a human's point of view. We demonstrate that by analyzing properties of such trees, the program is capable to predict how difficult it would be for a human to solve the problem. In the experiments with chess tactical problems our program was able to differentiate between easy and difficult problems with a high level of accuracy.

• Language: English
• Keywords: task difficulty, human problem solving, heuristic search, search trees, chess tactical problems
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Publisher: [S. Stoiljkovikj]
• Year: 2015
• Number of pages: 51 str.
• PID: 20.500.12556/RUL-30653
• COBISS.SI-ID: 153625798
• Publication date in RUL: 19.03.2015

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Title: Računalniško ocenjevanje težavnosti taktičnih problemov pri šahu

Abstract

Pri inteligentnih tutorskih sistemih je pomembno, da sistem razume, kako težak je določen problem za učenca. Kako samodejno oceniti tovrstno težavnost, ostaja odprto vprašanje. Namen raziskave je razviti algoritmičen pristop k ugotavljanju težavnosti, ki bi ga lahko uporabljali pri avtomatiziranem ocenjevanju težavnosti problemov za človeka. Osredotočili se bomo na ocenjevanje težavnosti problemov, pri katerih težavnost izvira iz kombinatorične kompleksnosti in kjer je potrebno preiskovanje med alternativami. Pristop temelji na uporabi hevrističnega računalniškega preiskovanja za gradnjo preiskovalnih dreves, ki so ``smiselna'' z vidika osebe, ki problem rešuje. Pokazali bomo, da je s pomočjo analize lastnosti tovrstnih ``smiselnih'' dreves računalniški program sposoben napovedati, kako težak za reševanje je določen problem. Naš program je bil sposoben z visoko stopnjo natančnosti ločevati med enostavnimi in težkimi šahovskimi taktičnimi problemi.

• Keywords: težavnost problema, človeško reševanje problemov, hevristično preiskovanje, preiskovalna drevesa, šahovski taktični problemi