Category Archives: chess

Solving Sudoku and the n-Queens problem

I’ve put together a solver for Sudoku , as well as one for the n-Queens problem. This was inspired and informed by some ideas and algorithms in the book Artificial Intelligence: A Modern Approach by Stuart Russel and Peter Norvig. The solvers were quite fun to write and surprisingly easy to put together, both done in an afternoon.

The approaches taken for these two problems are different, so I’ll highlight the key aspects and compare them at the end.

A typical sudoku puzzle
A typical sudoku puzzle (source: wikipedia)

The sudoku solver first uses the AC-3 algorithm to infer reductions in the domain (possible values) of variables before the search. If this reduces the domains to one value per cell, the puzzle is effectively solved. If some variable’s domain becomes the empty set (no value for a cell that can satisfy all constraints), the puzzle is unsolvable. Otherwise, a search is done to find a solution.

The search uses backtracking. It is a depth-first search (DFS), going deep down one path before checking others, with in-place modification of the puzzle board as it goes, and undoing the changes when it has gotten stuck and needs to backtrack. Order of solutions tried in the DFS matters, as some orders can prune large parts of the tree. The following heuristics are used to sort variables and values:

  • Minimum value remaining heuristic — prioritizes cells that have few legal values
  • Least constraining value heuristic — after choosing a cell, this prioritizes the value option that least inhibits other cells

Forward checking is used to maintain arc consistency for a variable after a value is chosen for it. This infers domain reductions in neighbouring variables. The the search proceeds until it finds a solution or fails (not solvable). If the puzzle is solvable, a solution is returned. Here is an example, using an “evil difficulty” puzzle found online:

import sudoku 

# Taken from https://www.websudoku.com/
evil = [
0,0,7,0,0,5,0,9,0,
6,2,0,1,0,7,0,0,8,
0,1,0,0,0,0,0,0,0,
0,0,0,0,0,3,5,0,0,
0,8,0,0,6,0,0,3,0,
0,0,5,4,0,0,0,0,0,
0,0,0,0,0,0,0,6,0,
9,0,0,6,0,1,0,2,4,
0,6,0,8,0,0,1,0,0
]

solved = sudoku.search(evil)
if solved: sudoku.print_solution(solved)

>>>
8 3 7 | 2 4 5 | 6 9 1 
6 2 4 | 1 9 7 | 3 5 8 
5 1 9 | 3 8 6 | 7 4 2 
- - - - - - - - - - - 
2 4 6 | 9 1 3 | 5 8 7 
7 8 1 | 5 6 2 | 4 3 9 
3 9 5 | 4 7 8 | 2 1 6 
- - - - - - - - - - - 
1 5 8 | 7 2 4 | 9 6 3 
9 7 3 | 6 5 1 | 8 2 4 
4 6 2 | 8 3 9 | 1 7 5 

The algorithm used for solving sudoku is systematic and exhaustive. In contrast, different algorithms are best suited for the n-Queens problem, another well known puzzle. The challenge is to place n queens on an nxn board, such that no two queens attack each other.

My n-Queens solver uses the local beam search algorithm, an adaptation of another algorithm named beam search. It starts off with some randomly generated configurations and does greedy stochastic hill climbing search on each one. If one of them finds a solution, that’s returned. Otherwise, the k best results are used for the next search. This algorithm requires parallel searches, so the solver utilizes multiprocessing. The idea behind hill climbing algorithms is to follow the steepest path up locally. As the nearest hill may not be the highest hill, it is prone to get stuck in local minimums (dead ends). Randomization is the trick used to solve this, by restarting the search in different places. The randomization also ensures that a solution is eventually found if one exists.

The solution for an 8×8 board is instantaneous, but it took a few minutes on 4 cores to find a solution for 128×128. Supposedly, this algorithm has been used to solve the millions queens problem in under 2 seconds, but it was probably a more optimized solution, and written in a language like C++.

Can the backtracking algorithm used for the sudoku solver be used for the n-Queens problem? It can, but it turns out that it requires much more computation time. It was the approach taken before hill climbing blew it out of the water. When stochastic hill climbing with restarts (a similar algorithm that does not utilize parallelization) was found to work so quickly for the n-Queens problem (in the 1990s), it resurged interest in this algorithm for a host of other problems. For example, it is used by airlines for flight scheduling due to its efficiency and its online property of being able to incorporate new data easily.

On the other hand, while it would also work for sudoku, the solution for sudoku appears to be solved with much less computation when using backtracking search. In the n-Queens problem, the solutions are densely distributed in the search space, whereas for sudoku, they are not. The answer to the question, “which algorithm should I use for this problem?” is not an easy one, and according to the no free lunch theorem, there is no one algorithm that is best for all problems.

You can check out the solvers at n-queens-solver and sudoku-solver.

My own chess engine

I’ve written a chess engine named Slonik. It implements the Universal Chess Interface (UCI), so you can download any popular chess interface, like Scid vs Pc. or Chessbase, to analyze with or play against Slonik.

I’ve written this engine from scratch, and chose to write it in Python, so that I can iterate quickly. That makes the engine slower, but maybe one day I will port it to C++. However, I am happy with it’s playing strength, all considering. The details of the engine are on the github page, but to summarize:

  • Alpha-beta minimax, quiescence search
  • Bitboard piece/board representation
  • Various search heuristics, such as the history heuristic, extensions, reductions, etc.
  • Hand-coded evaluation function
  • Transposition hash table

I plan to return to working on this engine’s AI — specifically to use deep learning and reinforcement learning techniques rather than the current hand-coded evaluation function.

My Mistakes

TL;DR:

  • Being afraid to lose
  • Playing “hope chess”
  • Spending incredible amounts of time “studying” but not mentally exerting myself
  • Fixating on openings and trying to stupidly memorize chess
  • Relying too heavily on computer analysis
  • Not paying attention to the meta-learning process

I learned chess at around age 11 or 12 and soon after joined Polgar Chess Club which was in Queens, NY at the time. I was immediately one of the best kids there and regularly won almost all the scholastic tournaments.  I became afraid to lose and whenever the position got tough, even against players I’d be expected to lose against, I would often start shaking. I would wish that someone would have taught me to learn to invest in loss, a concept typically learned from the domain of martial arts, but of course applicable to any art and any learning. I remember sometimes seeing Fabiano Caruana come to the club and play when he was only about 6 years old. I didn’t know back then that today he would be one of the top 5 highest rated players in the world. It is not surprising to me now, as I recall that I never saw him cry or shiver at the chessboard when he was losing. Somehow at a very young age he had the right mindset.

Throughout my chess development, I also would often play “hope chess.” In the linked article, Dan Heisman breaks down what I call “hope chess” into more specific subcategories (one of which he calls “hope chess” so hopefully it is not confusing), but I am referring to it in a more general manner. Sometimes I would sit and concentrate at the board for a long time, but it is hard to call what I was doing “thinking”—rather it was just worrying and hoping. That is either hoping that my opponent would make a mistake and fall for a trap, or hoping that the move I played would be good despite that I didn’t think hard for my opponent.

As a kid I also recall that I had (in my opinion) the work ethic of a champion. I had incredible discipline and would spend hours going through chess positions in my books. Despite this effort, I never achieved the type of success I thought I should have. I was at some point in the top 100 list for my age (though nowhere near the top of that list), but soon after hitting my first real slump, I lost interest in chess entirely (due to depression) and stopped playing for some years.

Some time later, I had a resurgence in my efforts and started to put in what felt like a “last ditch effort.” I began to “study” chess again, not realizing that I was going to repeat my past mistakes. I recalled that once, my childhood friend, Lev Milman, who is now an International Master, made significant improvements studying on his own. When I had asked him what his method was, he said that he would “Fritz everything.” Fritz is a computer chess engine of at least Grandmaster strength. I took his advice a bit too literally. I played many blitz games online and “analyzed” all of them with whatever the top engines were at the time. I developed an impressively sized database with all of my so-called analyses, covering a tremendous breadth of opening and middle game positions that I was likely to run into or had run into in my games.

I developed some good techniques of using chess engines to aid in analysis and understand of a position, and even a sophisticated understanding of which engines to use for which positions. Some of those skills are useful. However, in the end, I made no noticeable progress to show for my efforts and I once again dropped chess almost entirely for a few more years. I can see now that I had tried too hard (once again) to use my work ethic to improve, and bypassed the type of real mental effort that is required to do real learning. Chess is a complicated game that can’t be memorized and brute forced. This is obvious from an objective standpoint, but I see many people falling into this same trap of relying on sheer effort and will. It is from Tim Ferris that I learned of the Pareto Principle: for most events, roughly 80% of the effects come from 20% of the causes. Sometimes that is more like 99% to 1%.

I’ve made many mistakes in my learning process. Some of the worst ones are psychological. The biggest mistake is not so much particular to chess, but to learning in general. It’s important when you’re trying to improve at anything, to be critical of the process itself. That is everything from the plan you set out for yourself to the actual mental processes that you are going through in executing that plan. Just as important is to be keenly aware of your emotions. It is sometimes, as it was with me, just when you are making breakthroughs that you feel like giving up, and sometimes when you feel very confident that you make your biggest mistakes.

I’ve outlined here some of the mistakes I’ve made and the utter failures that have led me to quit chess twice now. In future posts I want to outline and dive into their opposites—positive changes that I’ve made which are contributing to my improvement.

Basic Mistakes To Avoid: Improve Your Chess Significantly

I posted the following answer on Quora quite a while ago. It was my first post on Quora (one of my only posts there so far), just to see how it works, but the response turned out to be popular, so I figured — what better first real post than a test-proven success?

Here’s that post:

  1. An amateur’s chess game is most improved by avoiding cheap tactics. Amateurs often spend too much time on ‘strategy,’ trying to look at the positional pros and cons of hypothetical situations 10 moves ahead, only to be forked by a pawn on the next move.
  2. Amateurs make the mistake of spending too much time studying openings. It is possible to become a 2200 player on almost no opening knowledge, by improving your tactics.
  3. A common mistake, not just for amateurs, is to avoid thinking about certain moves as if thinking about them meant playing them. For example, a person will often avoid considering a Rook sacrifice for a pawn, because their brain immediately assigns a negative feeling to such a move (fear of losing material). Awareness of that will give yourself permission to contemplate the said brilliant Rook sacrifice.
  4. Having said all this, when no tactics are in sight, some general guidelines are available to guide your play. They are to
  • control the center (not by occupying those squares, but by having pieces attack them. For example, a knight on f3 controls the center squares d4 and e5, while a knight jumping to e5 releases control of those squares).
  • avoid having any hanging/unprotected pieces or fortify those said pieces.
  • avoid letting your opponent occupy any advanced posts for too long.
  • double check your move for any tactical errors before it is played.

Looking back at this post, I would modify the word “tactics” in point #2 with “chess vision,” because tactics, in the sense that it is usually defined, is only one (albeit important) piece of the puzzle that must be developed when improving chess vision. I want to go into this in more detail in future posts, because that difference is pivotal in understanding how to study chess. Also, the list here is rather simplistic and misses many other important parts of the thought process, but I’ll be sure to get into that in future posts!

Why Cavemen Suck at Chess

Turn back time several thousand years and imagine this situation:

You’re traveling with your tribe, trying to get to your cave before dusk. You get tired and decide to stop by a fallen tree to rest. Suddenly, you hear a noise in the shadows behind you. You leap to your feet and duck your head, fiercely sweeping your eyes back and forth, spear in hand. Unsure what caused the rustle in the leaves, you run back to rejoin with the rest of the group.

Your decision in this scenario is instinctive but actually quite logical. The noise might be a rabbit to game, but it might also be a wolf ready to attack. Your brain is hardwired to know that it’s more costly to miss the sign of a threat than to miss the sign of an opportunity.

Due to this ingrained truth, our brain is much more vigilant of negative scenarios, and we have far greater incentive to avoid negative events than we do to go after positive ones.

This was well summed up by Neuropsychologist Rick Hanson when he said:

To keep our ancestors alive, Mother Nature evolved a brain that routinely tricked them into making three mistakes: overestimating threats, underestimating opportunities, and underestimating resources (for dealing with threats and fulfilling opportunities).

This is true for all of us, due to our common humanity. To avoid these three mistakes is a most difficult task, because like some of the biggest mistakes in life, they’re errors of omission. You make errors of omission by default, and you have to constantly remind yourself to avoid them.

We are all subject to this, because of that same common humanity. This is true in life in general, and guess what — life imitates chess. Let us roll the clock right back to present time, and imagine this situation:

It’s your move and you’ve been contemplating the same moves over and over in your head. You feel like you’ve thought long enough and the return on investment for additional thinking time is severely diminishing. You make your move and your nerves are starting to calm down when — damnit! You just missed a brilliant Rook sacrifice that would have made Mikhail Tal proud.

There is a whole host of reasons that you may have missed the Rook sacrifice. You may be very nervous about your friend’s board, not feeling well because you missed your snack, suffering from lack of sleep, or distracted by something. However, it would be a mistake to overlook the possibility that negativity bias is at play.

All too often, we avoid thinking about ‘losing a Rook for a pawn,’ because our brain has assigned negative feelings to such a move. Furthermore, the brain’s overwhelming inclination to dwell on this negative occurrence (missing that move, for example) can leave us unable to play well for the rest of the game. What’s more — it may be a move that you never would have missed in a tactical exercise (more on this later, though). Psychology is key in chess (one reason why it’s better to play against people than computers when you’re trying to improve). That is why the first game of a world championship match can have drastic effects on the rest of the match and alter history.

What’s even more interesting, though, going back to the Rook sacrifice example, is that your brain will usually also assign negative feelings to even contemplating such a Rook sacrifice. Your reptilian brain will keep you from taking on the correct thought processes required to analyse your move! That brings us to the next psychological phenomenon, magical thinking, which we all do naturally to some extent. This phenomenon affects our chess play in some really interesting ways, and often works together with the negativity bias. This will be the subject of another article soon. The point to bring home here is that by actively being aware of underlying thought processes, you can greatly improve your chess.

Magical Thinking

In clinical psychology, magical thinking is a condition that causes the patient to experience irrational fear of performing certain acts or having certain thoughts because they assume a correlation with their acts and threatening calamities.

In the most severe cases, magical thinking is a sign of psychosis, whereby a person has difficulty differentiating between reality and the fiction created in their minds.  People with Obsessive Compulsive Disorder often fear that thinking certain things will make them happen, so they create habitual motions or gestures to which they have likewise attributed certain results.

While in its extreme forms, it can be a sign of OCD or psychosis, magical thinking occurs for everyone to an extent, and it filters into the thought processes used in deciding your move during a game of chess.

Based on negativity bias from earlier bad experiences, or even just simply from generalization, your brain may assign a negative feeling associated with a certain type of move (like a Queen takes Knight sacrifice), and then due to magical thinking, your brain averts you from considering the sacrifice, as if thinking it meant playing it. Magical thinking can also take the form of pretending (and subconsciously believing) that if you avoid thinking about what your opponents replies or threats might be, they won’t happen. Players up to 1600 do this all the time, and stronger players fall victim to it too, though more rarely. If you recognize that you do this, think also about why you do it.  Some people fall into this mind-trap only after several games, and this could be mental exhaustion or frustration – it is easier to use this mental ‘tactic’ than to analyze the position. Perhaps you are not having fun playing right now and just don’t feel like trying your hardest. It’s a separate point but if you’re not just killing some time and are trying to improve, try your best every move or don’t play at all! Playing when you’re not having fun is a quick way to get burned out, and it’s not sustainable. You can’t improve if you’re not having fun.

Magical thinking is not all bad, as it can be a way of coping with stress or inspire confidence, like having a good luck charm. However, it can also hurt your chess if you are not aware of it. When I was was much younger, I would sometimes exert full concentration into hoping my opponent would play into a trap move, as if that would make it more likely to occur. It would be beneficial for the player to recognize when these psychological phenomenon occur.  If you recognize and acknowledge that you are using generalization to determine what will ‘likely be a good move’ without paying attention to the nuances of the specific position, you can start actively recognizing your assumptions during the game and create a goal to overcome them. Specific goals like this can be more fruitful than just having a goal to win. Start to think about these things, especially during your slow games!