Constraint Programming and Hick’s Law

Dhananjay Pandit
Jul 20, 2017 · 5 min read

I just realized that I hadn’t written anything on Medium in about a year. This is a topic I wanted to write about for quite some time now. Fortunately, tansaku provided the much needed motivation to start writing again and so here I am. Thanks Sam! :)

I took a graduate computer science course last semester called Knowledge Representation. Knowledge Representation is one of the fundamental areas in Artificial Intelligence. It is concerned with how knowledge can be represented in formal languages and manipulated in an automated way so that computers can make intelligent decisions based on the encoded knowledge. If you found that to be incomprehensible, do not worry, you don’t need to know anything about it to continue reading.

In this course, I was introduced to the concept of Constraint Programming. This paradigm is radically different to the object oriented or functional approach. I say this because you do not tell the computer the solution, nor do you tell the steps to take to get to the solution. You specific certain constraints for the computer and ask it to “magically” get an answer for you!

One solution of 8 Queens puzzle

I’ll explain this with the 8 Queens Puzzle. The aim of this puzzle is to place 8 queens on a chessboard such that no 2 queens attack each other, i.e. you cannot have 2 queens in the same row or column or diagonal. A naive way would be trial and error but it seems too optimistic given that there are only 92 solutions and 4,426,165,368 possible combinations. You might think about greedy method or dynamic programming which are tedious and lengthy. However, let me make a case in point for constraint programming approach.

Constraint programming needs 4 lines of code to solve not just 8, but ’N’ queens problem. Without digressing, the pseudo-code for the 4 lines are:

Define a 8 * 8 boardFirst constraint: Each column has exactly one queenSecond constraint: Each row has exactly one queenThird constraint: No two queens are on the same diagonal

You just specify these constraints and the computer will spit out an answer for you in no time. I found this paradigm fascinating. As you can tell, lines 2–4 can be written in any order, the execution is not sequential because they are just constraints. I grew fond of the constraint programming as the semester progressed and its immense potential started to dawn on me. There was a very interesting point which I realized as I was building my project for this course.

I was working on a large data set and computation times were going through the roof. I do not have the exact time it took because I remember I ended up terminating the process after 20 minutes. It crossed the 20 minutes multiple times and I was reducing the number of constraint trying to find a point where the execution would terminate and give an answer. I was hitting my saturation point and increased the number of constraints for the program. Lo and behold, the execution completed and I got an answer in a minute. Upon digging deeper into this, I understood that higher the number of constraints, faster the execution. At first, it felt contradictory to me. How can you find an answer faster if your solution space is severely restricted? Turns out, the constraint solver works on the method of elimination and higher number of constraints allow it to discard the non-solutions. Mind = blown!

It is at this point that I had an epiphany. Isn’t this true of the human decision making process as well? Don’t we make faster decisions if we have less choice and more constraints? I have experienced this while buying an electronic gadget. More research lead to more confusion. On the other hand, if I just have to select from one which my friend’s have, it is a much faster selection. My choice is limited in the latter example and that led to a quicker “solution”. Does this also explain why women take more time deciding what to buy than men? Evidently, the girl who was accepted by all 8 Ivy League schools had a harder decision to make than someone who got into 1. I found this extremely interesting and excitedly texted my dear mentor Sreeraman Thiagarajan who was quick to point out that I have merely rediscovered Hick’s Law.

Hick’s Law

Hick’s law, or Hick-Hyman law describes the time it takes for a person to make a decision as a result of the possible choices he or she has: increasing the number of choices will increase the decision time logarithmically. Mathematically, it is given by: T = b * log2(n + 1) where n represents equally probable choices, b is a constant and T denotes the average reaction time required to choose among the choices.

Overwhelmed by this new “discover” I decided to find if Hick’s Law is applied in computer science. Turns out it is a really important factor in Web Design! The more options a user has to pick from — be it navigation, products or images to look at — the more energy it takes to make a decision. In the end, the energy required to make the decision becomes so large the benefit of making it doesn’t seem worthwhile.

Remember that annoying “user experience” survey which pop up while you are browsing a site? You might decide to fill out the survey, purely out of goodness of your heart. Then you see that there are 50 questions in the survey, each with 8 choices each! Do you continue? Is the survey worth your time and effort? After all, the survey doesn’t benefit me anyway. And you press the close button and leave the survey.

In summary, in web design, Hick’s law asks you to remove unessential choices thus reducing the number of decision user has to make, speeding up the interaction and possibly increasing those conversions. Curate content into appropriate categories. Remove long navigational lists. Make effective use of filter and search options.

How psychology and computer science seem to be coupled together despite being vastly different enthralls me to no end. All my life I gave myself a hard time for not being able to get into more schools. As it turns out, this allowed me to take faster (and better?) decisions! :)

)

Dhananjay Pandit

Written by

Some people choose to see the ugliness in this world, the disarray. I choose to see the beauty.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade