A Monte Carlo Tree Search Based Conflict-Driven Clause Learning SAT Solver
| dc.contributor.author | Schloeter, Jens | |
| dc.contributor.editor | Eibl, Maximilian | |
| dc.contributor.editor | Gaedke, Martin | |
| dc.date.accessioned | 2017-08-28T23:48:11Z | |
| dc.date.available | 2017-08-28T23:48:11Z | |
| dc.date.issued | 2017 | |
| dc.description.abstract | Most modern state-of-the-art Boolean Satisfiability (SAT) solvers are based on the Davis-Putnam-Logemann-Loveland (DPLL) algorithm and exploit techniques like unit propagation and Conflict-Driven Clause Learning. Even though this approach proved to be successful in practice and most recent publications focus on improving it, the success of the Monte Carlo Tree Search (MCTS) algorithm in other domains led to research in using it to solve SAT problems. While a MCTS-based algorithm was successfully used to solve SAT problems, a number of established SAT solving techniques like clause learning and parallelization were not included in the algorithm. Therefore this paper presents ways to combine the MCTS-based SAT solving approach with established SAT solving techniques like Conflict-Driven Clause Learning and shows that the addition of those techniques improves the performance of a plain MCTS-based SAT solving algorithm. | en |
| dc.identifier.doi | 10.18420/in2017_257 | |
| dc.identifier.isbn | 978-3-88579-669-5 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik, Bonn | |
| dc.relation.ispartof | INFORMATIK 2017 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-275 | |
| dc.subject | Boolean Satisfiability | |
| dc.subject | SAT Solving | |
| dc.subject | Monte Carlo Tree Search | |
| dc.subject | Conflict-Driven Clause Learning | |
| dc.title | A Monte Carlo Tree Search Based Conflict-Driven Clause Learning SAT Solver | en |
| gi.citation.endPage | 2560 | |
| gi.citation.startPage | 2549 | |
| gi.conference.date | 25.-29. September 2017 | |
| gi.conference.location | Chemnitz | |
| gi.conference.sessiontitle | Studierendenkonferenz Informatik 2017 (SKILL 2017) |
Dateien
Originalbündel
1 - 1 von 1