|
|
Post by Lars Ericson on Aug 5, 2015 9:09:03 GMT -8
Kind of interesting. From Roland Kaminski, on their mailing list: there are no plans on our side to use OpenMP, OpenCL, or Cuda to parallalize clasp or clingo. In fact, it is very hard to map CDCL (the algorithm our solver is based on) to such APIs. The problem is that the solver spends its main time in unit propagation, which is a P-complete algorithm. Just check the first point on the corresponding wikipedia article: "In complexity theory, the notion of P-complete decision problems is useful in the analysis of both: 1. which problems are difficult to parallelize effectively, and; 2. which problems are difficult to solve in limited space." Those of you with training in complexity theory, parallel algorithms, decision procedures in logic, and GGP, please discuss this assertion and its implications for general game players. |
|
|
|
Post by Andrew Rose on Aug 27, 2015 23:01:23 GMT -8
Firstly, I note that just because the Clingo "unit propagation" algorithm is (claimed to be) P-complete, it doesn't necessarily tell us anything about GGP. Theoretically, it would be very possible for GGP to use a less complex subset of unit propagation and therefore a non-Clingo (or modified-Clingo) version could potentially be able to avoid the issues which arise from P-completeness.
However, as it transpires, "The Game Description Language is Turing Complete" (Saffidine, IEEE Transactions on Computational Intelligence and AI in Games, 2014). As a result, you can express all sorts of problems in it of various complexity classes - including that nightmare of all classes, NP-complete. For example, the Hamiltonian Circuit problem ("Hamilton" in the Stanford repository) is NP-complete in the number of nodes.
However, there are two things to note, even now that we know that NP-complete problems can be expressed in GDL.
1) Just because a class of problems (like Hamiltonian Circuits) is NP-complete, that doesn't mean that any particular instance is hard to solve. Indeed, even without a specialized algorithm, Sancho solves the Stanford version in a few seconds at most. NP-complete just means that (until somebody shows P=NP) the problems usually become exponentially harder to solve in the size of the problem (in this case, the number of nodes). Most of the problems in the Stanford repository are small enough that they can be solved quickly these days. It does mean that it would be trivial to create problems which GGP players could never solve though.
2) Heuristic approaches to hard problems, whilst not offering perfect solutions, can often provide solutions that are "good enough". The Travelling Salesman Problem (TSP) is a good example, where very good solutions (within a % or two of optimal) can often be found quickly, even if proving an optimal solution is beyond current computing resources. Finding generally applicable heuristics is (part of) what GGP's all about.
Finally, if you're interested in this stuff, I thoroughly recommend Coursera's "Discrete Optimization" course. It really is excellent (and has a competition in the form of a leaderboard for each of the puzzles they through at you). Indeed, I'd even dare to claim that the course is much better than the GGP course. (*Gasp*)
|
|
|
|
Post by maciej on Aug 28, 2015 12:52:40 GMT -8
(...) However, as it transpires, "The Game Description Language is Turing Complete" (Saffidine, IEEE Transactions on Computational Intelligence and AI in Games, 2014). As a result, you can express all sorts of problems in it of various complexity classes - including that nightmare of all classes, NP-complete. For example, the Hamiltonian Circuit problem ("Hamilton" in the Stanford repository) is NP-complete in the number of nodes. (...) NP-complete just means that (until somebody shows P=NP) the problems usually become exponentially harder to solve in the size of the problem (in this case, the number of nodes). Just to clear to avoid any potential confusion. NP-complete is not exactly the same as NP-hard. Basically, a problem is NP-complete if it's both NP (non-deterministic polynomial time) and every problem in NP can be reduced to this problem in polynomial time. There can be problems which are NP-hard but not NP-complete, so I assume that NP-hard is the nightmare:  |
|
|
|
Post by Lars Ericson on Aug 29, 2015 4:58:59 GMT -8
Key issue: Who can dig up the research that says that GPUs are uniquely unsuited to P-Complete problems versus regular CPU chips? Because Clingo does go for parallelism, there are explicit multithreading switches. I think he is saying that there is a lot of cross-talk between threads or something, although at first glance this is not the parallelism in the Clingo thread switch (I see the word "competing" in the thread switch). GPU threads do cross-talk just fine. So I don't get it.
|
|
