Thinking differently

Most chess engines seem to rely on a move generator that produces a list of moves. Then, it is possible to sort the moves so that the best candidates are searched first. However, move lists take memory space. That is a problem for my GPU move generator. There is 16 kB of shared memory for a thread group. If a thread group contains 256 threads, each thread has 64 bytes of memory. 32 bytes of it is reserved for the current positions, so only 32 bytes is left for moves. That is not enough for a move list. One has to think differently.

As mentioned in my previous posts, I implemented a traditional bitboard-based move generator that produces one move at a time on the GPU. Unfortunately, the performance is not so great. For comparison, I had a move generator that outputs a full move list at once. The former was four times slower than the latter. It seems that there are two reasons for that. First, the move generator is more complex, because it has to take the previous move as an input to regenerate the state of the move generator and to produce the next move. Second, it does unnecessary work, because one move needs only one destination square, although a bitboard representing all of them is generated for each move. I think it is time to revisit the design I had for the original CUDA chess move generator.

The basic idea is to have a few generic numbers represent the state of the move generator. For example: one for the source square (1-64), one for the direction (1-8) and one for the steps in that direction (1-7). Then the numbers are increased as the moves are produced. A similar idea was used in the early dedicated chess computers. And of course, one can use bit twiddling tricks to pack all the numbers in one integer. Tests are required to see how to implement the move generator most efficiently.


Refining the plan

During the last two weeks, I have been thinking about ways to utilize better the GPU in the move generator. There are two problems: divergence and insufficient processor utilization. These problems are opposite in a way. A large number of threads handling different positions produce divergent execution paths, but on the other hand it is difficult to get good processor utilization with a small number of threads. In addition, one has to take into account that more threads use more shared memory, at least in my current plan.

There are basically four kinds of more generators: sliding pieces, pawns, kings, and knights. It seems to me that trying to write a generic move generator for all pieces, in an attempt to avoid divergence, is wasting processor time. For example, knight move generator requires only a simple table look-up. Sliding pieces generator is a little more complicated, requiring masking blocked paths and outputting potentially several destination squares per direction. Pawn moves have different capture and moving directions, and one has to take into account double pawn moves, en passant and promotions. King move generator requires complicated handling of castling (e.g. the king cannot move over a square where it were in check). I have decided to split the move generator in four parts, so I can optimize each part separately. The problem then is that I need lots of positions, so that each move generator has something to do.

I will make an attempt to use 256 positions per thread group (256 threads also). Then there is a chance that there are enough threads for the full utilization of the processors. Each of the four move generators can use 64 threads to handle a different group of positions. Divergence is not a problem when the threads in the same move generator belong to the same wave (or warp in CUDA terminology). If one move generator runs out of work, the threads in the wave can help with another move generator. The worst case scenario is that there are 253 positions for one move generator and only one position for each of the other three generators. Then the three generators with only one position waste 63 threads each, while the one with the most threads must run four times, if the others finish too late to help it. I think this is quite rare, but I still have to think about something clever to avoid idle threads.

Shared memory usage will obviously be one on the major limiting factors. With 256 positions to store, we cannot afford 8 bitboards, because that would take 16 kB, which is all of our budget for the shared memory. I think the best solution would be using 4 bitboards only (in total 8 kB). As I explained in an earlier post, it is possible to pack the flag bits in the 4 bitboards. However, because the packing and unpacking is computationally expensive, I came up with a plan, where the flags bits are not stored in the positions. They have to be stored in the move data structures anyway, because one has to be able to undo a move and restore the flag bits. So why waste extra space elsewhere. The means that there always has to be a move associated with a position, but that is the case anyway, because we are generating one move at a time, and the move generator takes the previous move as an input parameter.

The rest of the shared memory can be used for storing move stacks and split points. There is no room for full move stacks, because one move takes 8 bytes and 256 moves take 2 kB. I plan to store only three last moves per position (in total 6 kB), and store the rest in the global memory. The three moves are stored in a ring buffer that act as a cache. I hope that latency of the the memory accesses can be hidden by the work that is done in the last 2 ply. I will try to implement this in the next few weeks.


Compute shader move generation progressing

I have written the basic move generation routines with DirectX 11 compute shaders now. I use bitboards and small look-up tables that contain moves for each piece-square pair and ray tables for sliding pieces. Those tables take about 6 kB. I initially put them in the shared memory, but then began to think, that since the tables are small, they could fit in the L1 cache which could be even faster. Tests proved that this was the case. Shared memory is slower than the cache, so I moved the tables to texture memory. This frees space in the shared memory that can be used for other purposes.

There is not enough space to store generated move lists for each position. It seems that I have to use over 32 bits per move, because there must be enough information to undo the move and account for special moves like promotion. Restoring the flags for a position takes 16 bits. Then source and destination squares take 6 bits each. Moving piece, captured piece, and promoted piece take 3 bits each. These are 37 bits already. I might as well reserve 64 bits per move, because 32 bits is the smallest natural element size on many GPU architectures. Then it is possible to include some extra information in the move data structures.

My idea is to store only the moves that are actually made. So the move generation must be able to produce only one move at a time, and deduce the next move to generate from the previous move. This requires some extra work per move compared to the generation of the whole move list at once. However, the extra work pays off, because the GPU can be better utilized. The move order must also be static. I think this is not a serious issue, because this approach is used near the leaf nodes. Higher in the tree we can use more sophisticated move ordering algorithms and global memory.

The shared memory will contain the move stacks and the current position for each group of thread working on the same position. In addition, there will be information about the split points. Split points mean points in the search tree, where the work is distributed between two or more groups of threads. It is not necessary to store the positions at the split points, but only the last move generated and search bounds. There will probably be a separate list of split points. An alternative is to interleave the split points in the move stacks. I will make more concrete plans, when I get the move generation part working fast enough.


Tests with compute shaders

I did some tests with compute shaders. I am pleasantly surprised that even with the very modest GPU of my laptop (AMD Radeon 7500G), it is possible to do over 60 billion SIMD operations in a second. That is more than most multicore CPUs can achieve even today. For example, eight cores running at 4 GHz, can only achieve 32 billion operations. It is true that on the CPU these can be 128-bit vector SSE operations, but the GPU can do similar operations as well.

I implemented the position packing and unpacking tests (see previous blog post) with a compute shader. The idea of packing was to fit all the information required for a chess position in 4 bitboards of 64 bits, when storing it in the global memory. The position is unpacked when it is needed in the computations. With flag bits (turn, castling rights, etc.) included, the GPU could do 178 million pack-unpack pairs in a second. Without flag bits (only pieces), the figure was 2,85 billion pack-unpack pairs. They take about 500 and 20 instructions, respectively. Let's say that an unpacked position takes 50 % more space. It means one extra global memory fetch for reading a position and another for writing it. Global memory accesses can take hundreds of clock cycles. So the packing might be useful or not, depending on the GPU.

I have also sketched a plan for shared memory usage. The idea is to keep everything in under the 16 kB limit. Look-up tables for move generation take 7 kB. Another 7 kB are reserved for move stacks. 1 kB is reserved for positions, which means that there are 16 positions per thread group. This means that there will be 4 threads working on one position. I think that with careful design, there is enough work for them.


New ideas

It has been a while since I wrote something about GPU chess. I still have not abandoned the idea of writing a GPU chess engine that could beat the CPU engines. With DirectX 11 and its compute shaders general purpose computation on the GPUs is brought one step closer to the wide audience. You do not need NVIDIA and CUDA anymore. Any modern graphics card will do. I am eager to try how the compute shaders could be used for chess algorithms.

Recently, I did some "bit twiddling" and found a more compact way to store chess positions. 128 bits is a natural alignment boundary on many GPU architectures, because four 32-bit floating point numbers fit in it. When computing graphics, those four floats represent x-, y-, z-, and w-coordinates in a homogenous coordinate system or red, green, blue, and alpha channels in the screen buffer. We may pack a chess position neatly in two of these 128-bit vectors. I will explain how.

We start with seven bitboards (64 bits each). These are pawns, knights, bishops, rooks, queens, kings, and white pieces. In addition, we have a few bits for other stuff, such as the turn bit, castling rights, en passant square, and 50-move rule counter. It is a commonly used trick in chess engines to pack queens into bitboards for bishops and rooks by bitwise OR, so that we end up with two bitboards instead of three, namely bishop-queens and rook-queens. Queens can be found by using bitwise AND between the two bitboards. This arrangement makes sense also from the move generation point of view, because queens move like bishops ans rooks. However, this is just an additional benefit. The packing trick works for any other set of bitboards as long as they contain disjoint sets of bits. We might as well have pawn-kings and pawn-knights for additional packing. We still have five bitboards and flag bits. Packing these already packed bitboards together with the same technique is not possible, because the bitsets are no longer disjoint.

However, if we start with packing three bitboards together, a more compact representation is possible. Let the six bitboards representing the pieces have names p, N, B, R, Q, K. Then let's make three new bitboards s = p | N | B, t = B | Q | R, and u = R | K | p (here "|" means bitwise OR). Now it is possible to find the original bitboards by just using bitwise operations. For example, p = s & u or Q = t & ~s & ~u (here "~" means bitwise NOT and "&" is bitwise AND). We have effectively packed six bitboards into three. Then there is the bitboard for white pieces. We cannot pack it, because it is not disjoint of the others. And finally we have the flags, which is kind of annoying, since the data would otherwise fit in exactly four bitboards.

Packing additional data into the packed bitboards in still possible. Imagine three circles, all intersecting each other. Each of these circles represent one of the aforementioned bitboards, s, t, and u. The intersection area between any two of the circles represent bitboard for a piece that they have in common. The areas of the circles left after cutting off of the intersections areas represent the bitboards for the other three pieces. In the center, there is a seventh area that is the intersection of all the three circles. That is always empty if the bitboards are defined as above. However, we can utilize this intersection area by using it to store the additional data. It is a bit tricky, but possible. We need to make sure that the bits are disjoint sets. First, notice that there are at most 32 pieces on the board. That leaves at least 32 empty squares. We can use those for storing data and keep the disjointness condition. The challenge is that the empty squares may change. Finding out which squares are empty is easy: ~(s | t | u). We can use for example the lowest 32 of those bits. Bit by bit we construct a 64-bit bitboard that contains the flag bits and then bitwise OR it with each of the three bitboards. These are the final three bitboards, and with the bitboard for white pieces, we have exactly four bitboards or 256 bits or 32 bytes for one chess position. Unpacking progresses in a reversed order, first finding out the flag bits by bitwise ANDing all the bitboards, then extracting the flags, etc.

I have tested the validity of this approach on the CPU, and the tests work fine in the sense that all the valid information about a chess positions is packed into 256 bits, and unpacked without errors. A few years old 3.2 GHz processor could pack and unpack about 10M positions per second in one thread. Most of the time was consumed in packing the flag bits into the empty squares, as explained above. Without the flags, the packing and unpacking was five times faster. On the GPU, I would consider packing all the data that goes to the global memory, or that is transferred between the GPU and the CPU. In move generation and local computations, I would use unpacked positions.

This packing thing was just one idea. I am still trying to find a good scheme for going through search trees.


Solving chess - facts and fiction

Because it is summer, I decided to take a vacation and spend some time with topics not directly related to my GPU chess project. One of the interesting topics I have been thinking is solving chess. I know it is not realistic with the current level of technology, but with future technologies, it might be possible. At least we can speculate what it would take to do that.

FICTION 1:Solving chess requires an evaluation function. It does not. Many people familiar with computer chess programs know that the computer uses a rough estimation of the value of the positions in its calculations, such as "white is up 0.11 pawns". This evaluation is not always accurate and one may thus suspect the accuracy of the solution if a computer is to solve chess. But the point is that, conceptually, every variation is calculated to the very end, meaning either a checkmate or a draw by one of the rules. Thus, there are only three evaluations: win for white, draw, or win for black. None of these involve any heuristics. They are the true values of the position. Another way to think about this is imagining a checkmate search that begins from the initial positions and tries to find a checkmate for white in any number of moves. It would take a very long time, but eventually, it would announce that there is a forced checkmate in X moves or that there is none. No evaluation required here.

FACT 1: Chess is solvable. Currently, this is merely a theoretical concept, because we lack computing power and memory. But it is fairly easy to show that there is a finite number of chess games, which ultimately can be enumerated and the best play for both sides can be found. First, there is a strict upper bound for moves that a game can last. The 50-move rule dictates that every 50th move, one side has to either move a pawn or make a capture. These are irreversible moves. This implies that, if the game does not end in another way, eventually the pawns cannot move or they promote to pieces, and all the pieces will be captured. Then there is no way to avoid a draw by the 50-move rule. Second, there is a finite number of moves in each position. There are only so many pieces that can move to so many squares. These two facts prove that there is a limited number of games. In his seminal paper "Programming a Computer for Playing Chess", Claude E. Shannon estimated the number of all games to be around 10120 (Philosophical Magazine, Ser. 7, Vol. 41, No. 314, March 1950).

In fact, the number of legal chess positions is much smaller. Shannon estimated this to be around 1043. This estimate was rough and ignored promotions. Currently, the best proven upper bound is around 1046.7. It seems that better than enumerating all the games is listing all the positions and finding if they are winning or not. This can be done by a technique called retrograde analysis which is widely used for generating endgame tablebases. Given the types of pieces on the board, it is possible to list all the checkmates. Then working the moves backwards, all the positions from which the checkmate positions can be achieved with one move are listed and marked as wins in 1 ply for the checkmating side. Then all the positions (where it is the defender's turn) from which one can reach only positions previously listed as wins in 1 ply are marked as wins in 2 plies. And the process is repeated until all the positions have be examined. This is a simplified explanation of the process, but you probably get the idea. This has been done for all the material combinations with 7 pieces or less (see e.g. Lomonosov Endgame Tablebases).

FICTION 2: Chess can be solved with current hardware. There have been hoaxes that claim that they have nearly solved chess. They are either good natured, such as the April Fool's joke by ChessBase, or exploit people's good faith to collect money, such as the infamous Nikola Chess. It is very common to be confused with big numbers that are given with the exponent notation. For example, 1047 and 1053 seem to be quite close to each other. But their ratio is 1 to 1 000 000. Not exactly close. While modern GPU's can perform as much as 1012-1013 operations per second, this is lightyears away from what is required. Imagine we had money to buy a million GPU's with 1013 flops capacity. That yields 1019 flops in total. Assume we had an extremely powerful algorithm for retrograde analysis, taking only 10 operations per position. This means, we can handle 1018 positions per second. Assume we had enough memory for all the position we need. How long it would take to go through all the chess positions? About 1 600 000 000 000 000 000 000 years. The universe estimated to be about 13 000 000 000 years old. Can you count the zeros?

FACT 2: It is difficult to solve chess even in the near future. For years, the so-called Moore's law was true: the computing power doubles every 18 months. Currently, as the fastest CPUs are running at 4 GHz, we seem to have hit the ceiling. While I was studying physics at a university in the beginning of the millennium, a professor said that he expected the upper limit to be around 10 Ghz. Above that, the transistors must be so small that the quantum phenomena begin to interfere with the computing. In nanometer scale, tunneling of the electrons happens with high enough probablity to make the processing unreliable. Speed of light is another issue. Information cannot travel faster than light, so the devices must be small to make them fast. Light propagates a meter in about 3.3 nanoseconds. This will become an issue if we need lots of memory, that cannot be located on the same chip as the processor. Clever computer architecture might alleviate this, but not too much. And the real problem that seems to limit the performance is the heat. Processors produce a lot of it. The more there are transistors, the more heat is emitted and the better cooling is required.

However, let us assume for a moment that Moore's law still worked. With increasing trend towards more parallel machines, we might have some overtime. Or perhaps a quantum computer is invented. One never knows. Currently, world's most powerful supercomputers achieve 1016 flops. Let us assume here the more realistic 100 operations per position. This means 1014 positions per second. Let us assume we could run the retrograde algorithm on the supercomputer for four months, i.e. 10 million seconds. Then, we can examine 1021 positions. Now, increase the computing power by using the Moore's law. When do we reach the 1046.7 positions? Simple math reveals: after 85 of the 18 months periods or 127.5 years or around year 2141. Not in our life time.

IN CONCLUSION: Heuristic approaches to chess will rule for years to come. Developing chess algorithms that use heuristic evaluation functions is still meaningful. Future chess engines will have deeper searches, more accurate evaluation, and perhaps we will see the rise of GPU chess. I want to be part of that.


Hashing schemes

Eventually, I will have to implement a transposition table for the chess engine. That requires accessing global memory during the search. This, however, should not be a problem if I do not use the transposition table at the leaf nodes or in the queiscence search. Transpositions occur most often at the deepest branches. However, the subtrees are smallest near the leaf nodes. Most benefit comes from nodes that are roots of larger subtrees. And fortunately, testing the transposition entries is always cheaper than move generation which involves global memory writes.

I have been thinking about the best way to implement hashing. Many chess engines use Zobrist keys for hashing. They require serializing the bitboards and using a table of random values for each piece and position. Although simple and effective, I do not like this approach, because it requires lookup tables (about 6 kb), which I have tried to eliminate. I would like to find an alternative hashing scheme. It does not matter if the hashing function is more complicated as far as it does not consume the precious memory.

The good thing about Zobrist keys is that each square and each piece has an equal contribution to the final hash value and positions are spread uniformly in the hash table. I would like to achieve similar results with less random numbers which could be hard coded as constants in the hashing function. I could interleave the hash key calculation with the global memory writes, so I would get the keys for free.