Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/525
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Maliković, Marko | en_US |
dc.contributor.author | Janičić, Predrag | en_US |
dc.date.accessioned | 2022-08-13T10:14:44Z | - |
dc.date.available | 2022-08-13T10:14:44Z | - |
dc.date.issued | 2013-01-01 | - |
dc.identifier.issn | 13896911 | en |
dc.identifier.uri | https://research.matf.bg.ac.rs/handle/123456789/525 | - |
dc.description.abstract | Chess endgame strategies describe, in a concise and intuitive way, the rules that a player should follow to ensure a win (or a draw). Endgame strategies are useful for both computer and human players. Their correctness can be proved in several ways. In this article we present one of them: a computer assisted proof based on reduction to propositional logic, more precisely to SAT. We focus on a strategy for the KRK endgame. The reduction to SAT is performed by using a constraint solving system URSA. The relevant lemmas produced SAT instances with hundreds or even thousands of variables and clauses, but URSA still successfully handled them. We would like to emphasise that this is the first computer-assisted high-level proof of the correctness of a strategy for some chess endgame. The presented methodology can be applied to other endgames and other games as well. Therefore, the point of this article is not only presenting a proof of correctness of an endgame strategy, but also presenting a new methodology for computer-assisted reasoning about chess endgames. | en |
dc.relation.ispartof | ICGA Journal | en |
dc.title | Proving correctness of a KRK chess endgame strategy by sat-based constraint solving | en_US |
dc.type | Article | en_US |
dc.identifier.doi | 10.3233/ICG-2013-36203 | - |
dc.identifier.scopus | 2-s2.0-84884165018 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/84884165018 | - |
dc.contributor.affiliation | Informatics and Computer Science | en_US |
dc.relation.firstpage | 81 | en |
dc.relation.lastpage | 99 | en |
dc.relation.volume | 36 | en |
dc.relation.issue | 2 | en |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.cerifentitytype | Publications | - |
item.grantfulltext | none | - |
item.openairetype | Article | - |
crisitem.author.dept | Informatics and Computer Science | - |
crisitem.author.orcid | 0000-0001-8922-4948 | - |
Appears in Collections: | Research outputs |
SCOPUSTM
Citations
2
checked on Dec 20, 2024
Page view(s)
18
checked on Dec 24, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.