4 Search Results for "Ulrich-Oltean, Felix"

Document
Invited Talk
DOI: 10.4230/LIPIcs.CP.2024.1
Solving Patience and Solitaire Games with Good Old Fashioned AI (Invited Talk)

Authors: Ian P. Gent

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
While games like Chess, Checkers and Go have been the subject of extensive research in AI for decades, there has been comparatively little study of single player card games. These games are generally called "Patience" in British English and "Solitaire" in US English, and have been popular for hundreds of years and remain so today. In fact, our ignorance of the winnability percentage of just one such game - "Klondike" - has been described as "one of the embarrassments of applied mathematics" by the distinguished statistician Persi Diaconis. I will talk about "Solvitaire", a program to solve patience games given a simple JSON description of the rules of the game and the initial layout. We have used Solvitaire to determine the winnability percentage of dozens different single-player card games with a 95% confidence interval of ± 0.1% or better. For example, we now know the winnability of Klondike as 81.945% ± 0.084% (in the "thoughtful" variant where the player knows the rank and suit of all cards), a 30-fold reduction in confidence interval over the best previous result. The vast majority of results we obtained with Solvitaire are either entirely new or represent significant improvements on previous knowledge. Solvitaire is very much a "Good Old Fashioned AI" approach to solving patience games, without using Machine Learning or Neural networks. It uses exhaustive depth-first search to explore all possible ways that a game could possibly be won, ensuring that games reported unwinnable really are so. This can involve searching extraordinary seach spaces with depths in the millions even including cases where unwinnability is proven. Numerous techniques imported from AI search play an important role in making this search practicable. Particularly important ones are: the use of a transposition tables; the exploitation of symmetry in search; the use of dominances to force certain moves to be made when it is safe to do so; and the use of streamliners. Solvitaire does have some games it performs poorly on, where exhaustive search is unable to prove that no win is possible but an alternative simple proof is in fact available. I will also talk about using constraint models do this, leading to slight improvements in some variants of Klondike but dramatic improvements in others. This talk will include personal anecdotes, explaining for example why it is dedicated to my mother Margaret Gent (1923-2021) for her patience in teaching me to love the game of patience.
Cite as

Ian P. Gent. Solving Patience and Solitaire Games with Good Old Fashioned AI (Invited Talk). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gent:LIPIcs.CP.2024.1,
  author =	{Gent, Ian P.},
  title =	{{Solving Patience and Solitaire Games with Good Old Fashioned AI}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.1},
  URN =		{urn:nbn:de:0030-drops-206863},
  doi =		{10.4230/LIPIcs.CP.2024.1},
  annote =	{Keywords: AI Search, Solitaire and Patience Games}
}
Document
DOI: 10.4230/DagMan.10.1.1
Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)

Authors: James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter

Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)

Abstract
Knowledge Representation and Reasoning is a central, longstanding, and active area of Artificial Intelligence. Over the years it has evolved significantly; more recently it has been challenged and complemented by research in areas such as machine learning and reasoning under uncertainty. In July 2022,sser a Dagstuhl Perspectives workshop was held on Knowledge Representation and Reasoning. The goal of the workshop was to describe the state of the art in the field, including its relation with other areas, its shortcomings and strengths, together with recommendations for future progress. We developed this manifesto based on the presentations, panels, working groups, and discussions that took place at the Dagstuhl Workshop. It is a declaration of our views on Knowledge Representation: its origins, goals, milestones, and current foci; its relation to other disciplines, especially to Artificial Intelligence; and on its challenges, along with key priorities for the next decade.
Cite as

James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{delgrande_et_al:DagMan.10.1.1,
  author =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  title =	{{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}},
  pages =	{1--61},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2024},
  volume =	{10},
  number =	{1},
  editor =	{Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1},
  URN =		{urn:nbn:de:0030-drops-201403},
  doi =		{10.4230/DagMan.10.1.1},
  annote =	{Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.38
Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints

Authors: Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Many constraint satisfaction and optimisation problems can be solved effectively by encoding them as instances of the Boolean Satisfiability problem (SAT). However, even the simplest types of constraints have many encodings in the literature with widely varying performance, and the problem of selecting suitable encodings for a given problem instance is not trivial. We explore the problem of selecting encodings for pseudo-Boolean and linear constraints using a supervised machine learning approach. We show that it is possible to select encodings effectively using a standard set of features for constraint problems; however we obtain better performance with a new set of features specifically designed for the pseudo-Boolean and linear constraints. In fact, we achieve good results when selecting encodings for unseen problem classes. Our results compare favourably to AutoFolio when using the same feature set. We discuss the relative importance of instance features to the task of selecting the best encodings, and compare several variations of the machine learning method.
Cite as

Felix Ulrich-Oltean, Peter Nightingale, and James Alfred Walker. Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ulricholtean_et_al:LIPIcs.CP.2022.38,
  author =	{Ulrich-Oltean, Felix and Nightingale, Peter and Walker, James Alfred},
  title =	{{Selecting SAT Encodings for Pseudo-Boolean and Linear Integer Constraints}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.38},
  URN =		{urn:nbn:de:0030-drops-166670},
  doi =		{10.4230/LIPIcs.CP.2022.38},
  annote =	{Keywords: Constraint programming, SAT encodings, machine learning, global constraints, pseudo-Boolean constraints, linear constraints}
}
Document
DOI: 10.4230/DagSemProc.09261.26
Sequencing and Scheduling in Coil Coating with Shuttles

Authors: Wiebke Höhn, Felix G. König, Marco E. Lübbecke, and Rolf H. Möhring

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
Applying combinatorial optimization in real life yields cost savings delighting the industry. Beyond that, at the core of some applications also lies a pretty (sub)problem rejoicing the mathematician. In our application coils of sheet metal are coated with k layers out of hundreds of colors. Coils are stapled together to run through k coaters, and non-productive time occurs e.g. when the color in a coater needs to be changed. Some coaters have two parallel tanks, enabling either parallel colors or cleaning of one tank during production. We present our sequencing and scheduling scheme in use at the plant today, lower bounds proving solution quality, and problems in the edge-wise union of interval graphs as a pretty mathematical subproblem.
Cite as

Wiebke Höhn, Felix G. König, Marco E. Lübbecke, and Rolf H. Möhring. Sequencing and Scheduling in Coil Coating with Shuttles. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hohn_et_al:DagSemProc.09261.26,
  author =	{H\"{o}hn, Wiebke and K\"{o}nig, Felix G. and L\"{u}bbecke, Marco E. and M\"{o}hring, Rolf H.},
  title =	{{Sequencing and Scheduling in Coil Coating with Shuttles}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.26},
  URN =		{urn:nbn:de:0030-drops-21654},
  doi =		{10.4230/DagSemProc.09261.26},
  annote =	{Keywords: Sequencing, scheduling, coil coating, mutli-interval graphs, heuristics, branch and price}
}
  • Refine by Author
  • 1 Delgrande, James P.
  • 1 Gent, Ian P.
  • 1 Glimm, Birte
  • 1 Höhn, Wiebke
  • 1 König, Felix G.
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 AI Search
  • 1 Applications of logics
  • 1 Constraint programming
  • 1 Declarative representations
  • 1 Formal logic
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2024
  • 1 2009
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact