Playing Logic Programs with the Alpha-Beta Algorithm

Autor:	Roberto Di Cosmo, Jean-Vincent Loddo
Rok vydání:	2007
Předmět:	Set (abstract data type) Discrete mathematics Computer Science::Computer Science and Game Theory Correctness Computer science Constraint logic programming ComputingMilieux_PERSONALCOMPUTING Combinatorial game theory Game tree Mathematical proof Algorithm Logic programming
Zdroj:	Logic for Programming and Automated Reasoning ISBN: 9783540412854 LPAR
Popis:	Alpha-Beta is a well known optimized algorithm used to compute the values of classical combinatorial games, like chess and checkers. The known proofs of correctness of Alpha-Beta do rely on very specific properties of the values used in the classical context (integers or reals), and on the finiteness of the game tree. In this paper we prove that Alpha-Beta correctly computes the value of a game tree even when these values are chosen in a much wider set of partially ordered domains, which can be pretty far apart from integer and reals, like in the case of the lattice of idempotent substitutions or ex-equations used in logic programming. We do so in a more general setting that allows us to deal with infinite games, and we actually prove that for potentially infinite games Alpha-Beta correctly computes the value of the game whenever it terminates. This correctness proofs allows us to apply Alpha-Beta to new domains, like constraint logic programming.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ef71ca4be849db2071b043d5ee7a00a3 https://doi.org/10.1007/3-540-44404-1_14 Zobrazit plný text záznamu