On May 24th 2000 the Clay Math Institute announced a $1,000,000 prize for solving one of 7 maths problems. Since then only 1 has been solved. The mathematician that solved the problem rejected the money.¹

One of those problems is the P vs NP question which relates to how we estimate time and space complexity for algorithms in computer science and software engineering.

Complexity

Complexity is an estimate of the growth in either time or space given an increase in the size of the input. Some algorithms have a linear relationship between time and input, we signify this complexity as O(n).

Constant complexity is signified as O(1) this means that as we increase n (the size of the input) the time and space is consistent, the algorithm doesn't take any longer and doesn't require more RAM.

An example of an algorithm that take constant O(1) space is finding the largest number in an unordered list of n numbers. You'll notice below, as we move through the list there's only one element we need to keep track of. This element is the largest item we've seen up to that point. When we see a larger number we replace the tracked number with this new larger number.

No matter how many items we include in this list we would still only need to track a single number, so the space complexity of this algorithm is O(1). We might apply this algorithm to find the largest file on a computer.

In terms of time complexity if we were to add more files or more items to this list the amount of time it takes would increase proportionally to the number of items we add. We therefore say this algorithm has an O(n) time complexity.

If we wish to improve the time complexity of finding the largest file, we can do this by having something track the largest file in the systems and checks and updates this whenever a file is written. This would provide us with a constant time O(1) algorithm as we avoid having to check all the file sizes every time we request the largest file. The trade off here is added complexity when updating any file on our system. If we were to reduce the size of the largest file the second largest might now be the largest and we'd have to find which file that might be.

We don't often require knowing what the largest file on the system might be so this added complexity is probably a waste of resource, additionally the overhead of creating, updating and deleting files has now increased. An O(n) search is probably enough for most machines.

Sorting

Sorting is often used to explain time complexity as there are a number of ways to sort items each with their own complexity. It's also useful because we can visualise sorting. Below I have provided an example of bubble sort, this has a time complexity of O(n²).

This isn't the most efficient way to sort a list of items, but it's a good representation of an O(n²) algorithm.

Categorising complexity

So far we've been discussing polynomial time algorithms, there exist algorithms which take exponential time to produce a solution. As an example in the case we have 2 items this would take 4 operations, if we increase to 3 items it would take us 8 operations. Such an algorithm is said to have O(2ⁿ) time complexity.

An example of an exponential algorithmic problem is the N-Queens ii problem. The time complexity for an algorithm to solve this problem is O(n!). So 3 items is 6 operations, 4 items is 24 operations. These are algorithms which a computer would struggle to solve, in a sensible time, as n gets larger.

Within the realm of these exponential algorithms exist problems which we can solve in O(n!) time but we can validate the solution in polynomial time. So even if n is exceptionally large, given a solution, we are able to validate the correctness relatively quickly.

P vs NP

This class of algorithms forms the basis for one of the millennium problems, known as P vs NP. The problem asks if there's a relationship between the complexity of validating the solution and complexity in solving the problem. If P = NP then problems that can be verified in polynomial time can also be solvable in polynomial time. However P ≠ NP implies that some problems are inherently harder to solve than they are to verify.

There are a few problems which have no existing polynomial solution, which upon finding one will determine that P = NP. Problems such as the traveling salesman problem (TSP), The boolean satisfiability problem and the vertex cover problem Proving that there exists a polynomial solution to these problems will net you $1 million.

In Practice

Solving these problems have practical applications. Solving TSP would provide us optimal solutions for delivery routing and vertex cover has an application in DNA sequencing. So how do we produce solutions in these areas when attempting to find the best solution can take a computer as long as the lifetime of the universe.

We tend to rely on algorithms that are fast on average, these algorithms may involve backtracking with a large amount of pruning; this approach is used in chess. There are also approximation algorithms or heuristic based approaches such as simulated annealing.

Trade Offs

Understanding time and space allows us to make trade offs between strategies. Certain algorithms can provide us an efficient approach to solving technical problems. There is a limit to how much we can do with algorithms and sometimes even problems that sound simple on the surface could have a $1 million bounty standing for 25 years, without you realising it.

A modern laptop can run ~3.8 billion cycles per second. The cycle is determined by oscillation frequency of the electrical signal that hits the CPU. Contemporary CPUs manage synchronisation using all sorts of error correction tricks.

In mechanical systems, such as those used in medical equipment and robotics, the binary numbers that we are most familiar with can cause errors if they're read during state transition.

Decimal and Binary

We are most familiar with decimals, this is a base 10 counting notation where each position in the number represents a different power of ten. E.g. 10, 100, 1000.

The computer relies on binary as this takes advantage of the fundamental on/off state within an electronic circuit. Binary is base 2, so each position represents a power of 2. E.g. 2, 4, 8, 16.

Reading States

Binary numbers can cause errors if they're read during transitions. The more positions that require toggling, while switching between numbers, the higher the chance we introduce errors into the system. This is shown clearly as we transition between the numbers 3 and 4. Which requires changing three bit positions. 011 -> 100.

If these bits aren't switched instantly we can read any of the following numbers 1, 2, 5, 6 or 7 instead of 3 or 4. Not great if you're working with a critical system and need precision.

Grey Code

To get around this we use an alternative ordering of the binary system in which successive numbers are separated by a single bit. Incrementing a number only relies on switching one position and removes the chance of reading the wrong number during state transitions.

This ordering is called Gray code, and an animation of the bit positions, for an incrementing number, is shown below:

The Application

In addition to reducing read errors, relying on only a single toggle to move up the number scale consumes less energy than traditional binary due the fewer toggled bits.

Some systems require testing every position of multiple switches or toggles. Gray code can improve the efficiency of these tests. If we had to iterate through all 16 combinations of 4 switches. Using ordinary binary would need to flip 1, 2, 1, and then 3 toggles as we move from numbers 1 to 4, while gray code allows us to only ever need to flip a single toggle to eventually test all switch combinations.

One of the most common uses of gray code is in rotary encoders, also known as knobs. These convert angular position to an analog or digital signal. If we had to rely on a normal binary scale, when rotating the knob, it could end up sending the intermediary numbers between each angle, which would make it pretty useless.

While exploring an interesting game engine which compiles python code to WASM; I thought, there's no better way to have fun than to write a chess engine. This was the start of a one month long project which led me to create my own chess AI.

Chess programming is a topic that has been written about extensively, it has been a proving ground for some of the first AI researchers and even today it is still used as a benchmark for techniques in applied research.

This article is the first part in a series of three in which I attempt to distill some insight into the application of algorithms in software, namely chess programming. In the hopes that it may inspire how you approach solving similar problems in the future.

Bit Operations

If you've ever done some leetcoding or any other live algorithm style interview prep in software engineering you might have come across the odd question on bit operations and wondered if you'll ever need to actually do these in your day to day job. I'm not here to answer that, but I am here to show you how it applies to chess programming.

Firstly what are bit operations:

a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor.

Wikipedia

Essentially bitwise operations are physical operations that are embedded into the processor, they consist of your logical AND, OR, XOR and bit shifts. The mathematical operations that you're familiar with (such as Add, Subtract etc.) are all built upon bitwise operations.

Here's an example of a NOT operation:

NOT 0111  (decimal 7)
  = 1000  (decimal 8)

And an example of an AND operation:

    1010 (decimal 5)
AND 1100 (decimal 12)
  = 1000 (decimal 8)

We can see these operations supported in python:

>>> 0b1100 & 0b1010
8
>>> bin(0b1100 & 0b1010)
'0b1000'

There's two ways we can shift bits. (Left and right) Here's an example in python:

>>> # Left
>>> bin(0b0010 << 1)
'0b100'

>>> # Right
>>> bin(0b0010 >> 1)
'0b1'

Explaining how the processor does addition is out of scope of this blog post, but put together some of these bit operators and you've got yourself a function that can do addition.

Bitboards

Back to the chess:

We are doing all of this essentially to get as close to the processor as possible, since we want the most performance out of a computer as we can by avoiding any unnecessary operations.

In chess programming we will use a single number to keep track of all the positions of pieces on the board. This is what we call a "bitboard". We will have a few bitboards to maintain the game's state. The first one will be 'board' which tracks all the pieces. At the start of the game this number will be: 0xFFFF00000000FFFF. Which is hexadecimal for 18446462598732906495. If we print the binary form of this number and format it over 8 rows we get the following:

 Bitboard:

8  1 1 1 1 1 1 1 1
7  1 1 1 1 1 1 1 1
6  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
2  1 1 1 1 1 1 1 1
1  1 1 1 1 1 1 1 1
   a b c d e f g h

There are a few other bitboards to track during a game of chess. There will be 2 boards for each colour (white and black). And there will be a bitboard for each type (6). Which gives us a total of 9 bitboards, or 9 numbers to cover the entire game state of chess. Here's two more examples of bitboards, one for pawns and one for white pieces:

>>> pawns = 0x00FF00000000FF00
>>> white = 0x000000000000FFFF

Now we can uses these three numbers to give us the answer to some questions for example; Where are all the white pawns?

>>> board & pawns & white
65280

 Bitboard (65280):

8  0 0 0 0 0 0 0 0
7  0 0 0 0 0 0 0 0
6  0 0 0 0 0 0 0 0
5  0 0 0 0 0 0 0 0
4  0 0 0 0 0 0 0 0
3  0 0 0 0 0 0 0 0
2  1 1 1 1 1 1 1 1
1  0 0 0 0 0 0 0 0
   a b c d e f g h

During a game of chess you'll use these to calculate which pieces are under attack. (e.g. given: knightsmove & theirpieces the result will be 0 if there's no piece under threat). We can also use these bitboards workout where the valid moves are with moves & ~board. (Moves and not board).

A chess AI that's looking 4 moves ahead will have ~5mil positions to consider, so having these operations done on a low level can help boost the performance of the software. The more you squeeze out of performance the more accurate your chess AI will be, because this improves it's ability to look into the future.

Beyond Chess

In summary learning about how bitboards are applied to chess programming has allowed me to understand how bit operations can be applied practically in software. Before I dived into learning how chess is programmed I had only imagined keeping track of the board state using several objects and an array, however I now see there's more than one way to crack an egg; the board state egg.

I hope the article helps to providing insight into practical applications of bit operators and leaves them to be considered as valuable for solving technical problems or at least reminds software engineers that we have them in our toolbelt.

Further Reading

• Stockfish
• Chess Programming

Foolscap was my answer to losing all my notes and forgetting the exact file I saved it.

Was it on Desktop or next to the project?

Thus I decided to write an application that took care of the saving and finding of my notes.

Unordered Lists

One thing I have taken for granted is the ordering of my files in any file system. I only realised how important it was after unordered dictionaries in python allocated my notes random positions on the list.

The random ordering meant if I have note "M" in mind, it could appear anywhere on the list. So my eyes would track down n positions in the list to find "M". An O(n) operation for my eyes.

After growing tired (a whole day of O(n) eye operations), I wrote the rule to provide me the list in alphabetical order. This was great my brain automatically switched to doing a binary search for note "M". O(log n)

Ordered Lists

Now that finding note "M" was optimised for my eyes, my finger had to press the down key until my cursor was on the note of choice. This wasn't good enough, I was referring to note "M" several times a day and the other notes I'd reference once a month were adding computation time to my finger.

This is where I introduced two of the most powerful rules of Foolscap. Since I tracked the number of views, and time it was last viewed or modified I could implement the following ordering:

1: LastView/Modified/RecentlyCreated
2: MostViewed
3: 2ndMostViewed
4: 3rdMostViewed
5: A
6: Z

This was neat!

I had significantly cut down the amount of time it took for me to get to the notes I was using most frequently.

Search Lists

Searching needed a slightly different ordering since applying the rules above to your search results will likely be meaningless. The meaningless will come from your inability to predict what will appear in the list to begin with.

Python has a neat method for it's strings.

note_title.startswith("text")

Which I used as the initial search feature. A search by the prefix of my note title. To me this made sense since my notes are titled by their subject matter, e.g. "linux", "elastic".

The iteration to this search functionality was to include the conditional:

if "text" in note_title:

I still wanted to provide the user with the result of the initial prefix search as the first result in the list.

This is when I fathomed this solution:

search = [title for title, _ in notes.items()
          if query in title]

# Sort by the position the query appears in the title
return sorted(search, key=lambda title: title.index(query))

Pretty neat!