ChatGPT has been all over the new recently. Here is a recent “chat” I had with it:

Me: Generate a variable ordering heuristic for constraint satisfaction problems that has not been tried before.

ChatGPT: One possible variable ordering heuristic for constraint satisfaction problems that has not been tried before is based on the concept of information entropy. Information entropy is a measure of the amount of uncertainty or randomness in a system.

To apply this heuristic, we can first calculate the information entropy of each variable in the constraint satisfaction problem. This can be done by considering the number of possible values that each variable can take and the constraints that are imposed on it. For example, if a variable has a large number of possible values and few constraints, it will have a high level of entropy. On the other hand, if a variable has a small number of possible values and many constraints, it will have a low level of entropy.

Once the entropy of each variable has been calculated, we can order the variables according to their entropy. Specifically, we can assign higher priority to variables with lower entropy, as they will have fewer possibilities and be more constrained. This can help reduce the search space and potentially lead to a more efficient solution.

It is worth noting that this heuristic is just one possible approach and may not always be effective in practice. It is always important to carefully evaluate the performance of any variable ordering heuristic and consider how it may be improved or modified to better fit the specific needs of a particular problem.

Me: Isn’t this just the well known domain over degree approach?

ChatGPT: The domain over degree heuristic is a commonly used variable ordering heuristic for constraint satisfaction problems that aims to reduce the search space by prioritizing variables with fewer possible values (also known as a smaller domain) over those with a larger domain. This is similar to the approach I described, which involves ordering variables according to their entropy, which is also a measure of the number of possible values that a variable can take.

However, there are some key differences between these two approaches. The domain over degree heuristic only considers the number of possible values for each variable and does not take into account the constraints that are imposed on the variable. In contrast, the entropy-based heuristic takes both the number of possible values and the constraints into account when calculating the entropy of each variable.

In addition, the entropy-based heuristic considers the overall level of randomness or uncertainty in the system, while the domain over degree heuristic only looks at the number of possible values for each variable in isolation. This means that the entropy-based heuristic may be able to capture additional information about the structure of the problem and potentially lead to more efficient solutions.

Overall, while the domain over degree heuristic and the entropy-based heuristic are similar in some ways, they differ in their approaches to ordering variables and may have different performance characteristics depending on the specific problem being solved.

I posted this exchange at the Constraints Google Group and Juan Francisco Diaz posted that he approached the originality question by asking GPT:

Do you know papers talking about the entropy-based heuristic approach?

and received the reply:

Yes, there are several papers that discuss the entropy-based heuristic approach for variable ordering in constraint satisfaction problems. Here are a few examples:

1. “Entropy-based variable and value ordering heuristics for constraint satisfaction problems” by Richard E. Korf and Andrew J. Fellegi (1993) presents an entropy-based variable ordering heuristic and an entropy-based value ordering heuristic, and evaluates their performance on a range of constraint satisfaction problems.
2. “A comparison of heuristics for the maximum constraint satisfaction problem” by Peter van Beek and Peter van der Wal (1995) compares the performance of the entropy-based heuristic with other variable ordering heuristics on the maximum constraint satisfaction problem, which is a variant of the constraint satisfaction problem in which the goal is to find an assignment that satisfies the maximum number of constraints.
3. “Efficient entropy-based variable ordering heuristics for graph coloring problems” by Jia-Huai You and T. K. Satyanarayana (2003) presents an entropy-based variable ordering heuristic for graph coloring problems and compares its performance with other heuristics on a variety of graphs.

These papers may provide more detailed information about the entropy-based heuristic approach and its applications to constraint satisfaction problems.

Register for ChatGPT and ask it “What is a constraint satisfaction problem?”

Then ask it to “Write a program to solve the N-Queens Problem.”

Then start looking for another line of work. 🙂

No, seriously, instead start thinking about how we can use this kind of technology for “progress towards the Holy Grail“. In particular, how we can progress beyond what this technology can do on its own, by working on “bridging CP and ML“. 

I posted the “Puzzles” blog entry to LinkedIn and Supriyo SB Chatterjee responded by noting that “solving for Scrabble is a CSP too”. (Some time ago Supriyo won the New England Regional Colleges Scrabble Championships.) Indeed it is, an interesting kind of CSP.

When it is your move you need to make a choice that satisfies a number of constraints. You can only use letters from your tray (which you then replace). You have to form a word in the Scrabble Dictionary. You have to place the word to link up properly with what is already on the board. And your move changes the board (and your tray), so you have a “sequence” of problems to solve, where each problem in the sequence is dependent on your solution to the previous one.

I thought of calling this a “sequential CSP”. Of course, there have been many variants of CSP, including some with some form of “sequential” nature. Sequentially Dependent Meta-Constraint Satisfaction Problem: An Application to Video Games seems particularly relevant here. I thought of the acronym “SCSP”, but it has already been used at least twice, for Semiring-based CSP and for Structural CSP. So then I thought “SQCSP”, even though that risks confusion with Quantified CSPs. But there is the Semi-Qualitative Constraint Satisfaction Problem (SQCSP).

Of course, there is another aspect of Scrabble: it is a game, with two adversaries. So actually the adversarial constraint satisfaction paradigm seems relevant here. Looking back I see that Ken, James, Paidi and I didn’t actually use the “ACSP” acronym when we wrote up adversarial constraint satisfaction for ECAI 2004. Perhaps just as well: “a CSP”?

So one outcome of this was the thought that it could be useful to have some kind of list, taxonomy or categorization of the many variants of constraint satisfaction problems. Perhaps even a survey. I’ve posted on the Constraints Google Group asking people to provide pointers to CSP variants and hope to assemble a list to make available at the constraints Resources site.

Back to Scrabble, beyond just finding moves that satisfies the constraints, there are interesting issues of optimization and strategy. For example, do you want to go for a lower value move now to try to set up a high value one later or to prevent your opponent from using a potentially valuable position? I imagine there are books on Scrabble strategy.

Scrabble certainly has been computerized. In a match held way back in 1998, MAVEN defeated World Champion Joel Sherman and runner-up Matt Graham, playing together. But perhaps Scrabble can still inspire new ways of thinking about constraint satisfaction.

Looking for papers on explanation for constraint satisfaction I ran across Meta-explanation in a Constraint Satisfaction Solver by the pioneering French AI scientist Jacques Pitrat. From the abstract:

Meta-explaining is useful to a human or an artificial researcher in order to learn how to use its knowledge efficiently. For instance, when the system RESEARCHER solves the same prob- lem using two different methods, it can meta-explain why it finds a more elegant solution with one of them. 

It might be interesting to compare Pitrat’s work here to the work I did with Chavalit Likitvivatanavong and Rick Wallace in Deriving Explanations and Implications for Constraint Satisfaction Problems.

Pitrat’s paper is related to a very ambitious — and very “meta” — research agenda that he was pursuing. See A Step toward an Artificial Artificial Intelligence Scientist, Artificial Beings: The Conscience of a Conscious Machine, and his blog. Unfortunately Pitrat passed away recently; the record of a day of tribute can be found here. 

The great physicist George Gamow wrote a book entitled One Two Three . . . Infinity: Facts and Speculations of Science, which I recall as one of the books I encountered in my high school library that inspired my interest in mathematics. This post is what I hope will become one of a series on “Where do ideas come from?”. (As always further contributions from readers in the Comments are encouraged.)

“Consistency”, as a form of inference, is arguably what distinguishes the AI approach to constraint satisfaction. “In the beginning” there were three forms of consistency, which were described in terms of the “constraint graph” representation of constraint satisfaction problems: “node consistency”, “arc consistency” and “path consistency”, which involved respectively nodes (vertices), arcs (edges) and paths (sequences of edges leading from one vertex to another). Nodes, arcs, paths: that seemed to cover the possibilities for graph consistency.

However, Montanari demonstrated that path consistency could be reduced to consistency for paths of length 2, involving just 2 edges. Looking at it in terms of the number of vertices involved: node consistency involves just 1, arc consistency 2, path consistency 3. “Node, arc, path” … it isn’t obvious that there is anything more to see here. But “1, 2, 3” … that practically begs to ask the question: Does it stop there; shouldn’t there be a “4-consistency, a 5-consistency, … ? And thus the idea for “k-consistency” was born. Putting this together with an algorithm for achieving k-consistency (and thus ultimately a complete set of solutions, purely by inference) resulted in an MIT AI Memo in 1976, which in 1978 became my first major journal publication.

There are two meta lessons here with regard to the question “where do ideas come from”.

The first is the importance of representation. A classic example is Kaplan and Simon’s investigation of the mutilated chessboard problem. Here, it was the switch from talking about different graph structures — nodes, arcs, and paths — to talking about the number of vertices involved. Another representational shift — from viewing constraints as represented by edges to viewing them as represented by nodes (in an “augmented” constraint graph) — enabled the algorithm I devised to achieve higher order consistency.

The second is the notion of extrapolation, as an instance of the even broader concepts of generalization and completion. Here “1, 2, 3” suggests “k”. It just doesn’t seem right that we would have to stop at 3. 🙂

Of course, we don’t actually go to infinity — unless we consider problems with an infinite number of variables. Hmm, that’s an idea …