Generating a Random Combination

Recently I've had my mind on lottery drawing, and I suddenly thought of a way to generate a random combination that is better than how I used to do it.

Here's the basic problem. Given the set of numbers (0, 1, ... n-1), we want to generate a random subset of k elements of this set of n. The random generator function that I can use is Random.nextInt(n), which returns a number between 0 and n-1. Now, if we have already generated some of the numbers, (c[0], c[1], ..., c[i-1]), then how do we generate the next one?

The way I traditionally do it is that I keep generating a random number between 0 and n-1 until I get one which is different from the ones I already have:

List<Integer> numbers=new ArrayList<Integer>();
while (numbers.size()<k) {
    int next=rnd.nextInt(n);
    if (!numbers.contains(next))
        numbers.add(next);
}

I've kept wondering if there if a way to do it that doesn't involve an unbounded loop, and there is. Think of how lottery numbers are drawn. Once a number is selected, it is discarded from the set of possible numbers, and the next one is then chosen uniformly from the rest. We can do something quite similar in code!

Once again, suppose that we have already generated i numbers, and we're looking for the (i+1)-th one. There are (n-i) candidates left to choose from, the only problem is that they're not the numbers from 0 to n-i-1 (which is the interval in which we can generate one of (n-i) numbers). But we can map these two sets! Let me demonstrate on an example. Consider the numbers between 0 and 9, and suppose we have already chosen 3, 4, and 7. Here's our problem:

The numbers we need to choose from:	0 1 2     5 6   8 9
The numbers we can generate from:	0 1 2 3 4 5 6

Notice that we can collapse the first row, giving us a mapping from the 7 numbers between 0 and 6 to the 7 numbers between 0 and 9 but excluding the ones we've already chosen. The question is: if we generate one in the former set, how can we get the actual number it corresponds to? Here's how:

List<Integer> numbers=new ArrayList<Integer>();
for (int i=0; i<k; i++) {
    int next=rnd.nextInt(n-i);
    int nextIndex;
    for (nextIndex=0; nextIndex<i && numbers.get(nextIndex)<=next; nextIndex++)
        next++;
    numbers.add(nextIndex, next);
}

Note that now we maintain the list of selected numbers in ascending order. What we basically do is shift our generated number to the right (increment it) as many times as we need to account for the 'empty slots'. For example, suppose that in the scenario depicted above, we get the random number 3. Since the first number already selected (which is 3) is <= the new number, we increment it to get 4. The next number already selected (4) is once again <= our number, so we increment it again, and get 5. The next number in the list is 7, so we don't increment any more. We've found the number among the remaining ones which corresponds to the generated number 3 (or, to put it in another way, the fourth one among the remaining candidates): 5. We similarly need two increments if we start from the number 4. If the generator gives us 5, then after two increments, we find that the next already chosen number, 7, causes us to increment a third time, giving us 8. And so on.

As a nice side-effect, we can notice that the number of times we needed to increment gives us the index where we have to insert the new number to keep the list sorted (since it is equal to how many numbers we already have which are less than this new one).

I like this algorithm much more than the original one. We can give an upper limit to its execution time, so we don't run into problems even when k is close to n. I'm pretty sure that I'm not the first one to think of this way of generating combinations, but I wonder how come I've never seen this method before.

P.S. There's another, quite pretty approach on Wikipedia. That one is similarly easy to implement, has bound run-time, and I've also not heard of that one before.

Synchronization Strangeness

I've encountered quite a head-scratcher; it took me about an hour to finally realize what was going on.

I'm using a background thread which communicates with the main thread using a SynchronousQueue. For those of you who don't know this class, it can be used to establish rendez-vous points between two threads. One thread calls queue.put(obj), the other one calls queue.take(), and both of these calls block waiting for one another. When the two threads meet up at these calls, an object is transferred from one to the other, and then both functions return.

Now, I had a class in which I create a thread in the static initializer; this thread will be the receiver. Also, it just happens that the first queue.put call took place before the static initializer finished. Basically, I had something like this:

public class Sync {
    private static final SynchronousQueue queue=new SynchronousQueue();
    private static final Thread thread;
    static {
        thread=new Thread("Background") {
            {
                setDaemon(true);
            }

            @Override
            public void run() {
                try {
                    queue.take();
                } catch (InterruptedException e) {
                }
            }
           
        };
        thread.start();
        try {
            queue.put(5);
        } catch (InterruptedException e) {}    }
    public static void main(String[] args) {
    }
}

What happened when I ran the program is that both the take and the put functions blocked, the SynchronousQueue just didn't seem to work. I jumped into JConsole and it showed that the main thread was waiting inside the put function, and the background thread was at the take function, but its state was RUNNABLE, and the stack trace consisted of a single frame: "Sync$1.run(Sync.java:13)" (the stack trace of the main thread went down quite some way into the put function, ending up at "sun.misc.Unsafe.park(Native Method)").

So if the background thread was RUNNABLE, why was it just standing there? And where exactly was it standing? According to the stack trace, it didn't enter the take function at all.

Finally I realized. It wasn't the take method that was blocking the background thread, it was the access to the queue object. The queue object is a static field of the class, and the class itself needs to be initialized for other threads to access it. (Other than the thread which is performing the initialization itself, that is.) So the access to the field was blocked while the JVM was waiting for the initialization of the class to finish. But it wouldn't finish, since the initialization was blocked on the put function. It was a deadlock involving class initialization.

Class initialization is tricky business, mainly because in general it 'just works', and thus the programmers aren't completely aware of its intricacies. When one tries to be clever, it is not that difficult stumble into weird bugs.

GameCracker - 7. Consistency

I have these giant data structures stored on the disk; I certainly want to make sure that it's safe. In case of a crash, power outage, or some similar catastrophe, it is possible that GameCracker shuts down at a point when the stored data is in an inconsistent state. In order to avoid that, I have created a consistent storage library.

My goal is similar to some aspects of databases, namely I want that the single operation I defined - the expansion of a move - either finish completely or not at all. Note that I have to ensure this requirement across multiple data files. In this entry, I describe how I do it, first from the point of view of GameCracker itself, and then discuss the implementation.

First, a manager instance has to be created, and through it can all the different data files be opened. The main program can read and write these files using familiar interfaces. I have two kinds: a sequential store, which can just write different kinds of data in a row without the ability to read anything back or to set position; and a random access file which can be read and written in a random access manner.

The program has to signal consistent states by calling a commit function on the manager. The guarantee of the system is that whenever it restarts, the files will reflect one of these states, even if some writes followed the last commit during the last execution. A final important operation is what I call sync; this causes the system to immediately update the files so that they reflect the last commit. Note that the system must ensure consistency even if the sync operation itself is interrupted.

Now on to the inner workings. All the files have a corresponding in-memory data structure which stores all modifications since the last sync, and also mark the last commit state. Write operations update these data structures instead of the files themselves, and reads ensure that they return the latest data, either from the file or from the in-memory structure. For sequential files, all I have is a byte array accumulating writes which have been performed since the last sync, with a pointer marking the position where the latest commit was performed. Upon a new commit, I move this pointer to the end of the array, and upon a sync, all the data before the pointer is written to the file and removed from the store.

For random access files, I have two maps, storing the bytes written to various positions, one corresponding to the latest commit, the other storing the uncommitted writes. All new writes are translated to adding elements to this second map. A commit operation comprises moving the contents of the second map to the first, committed one. Syncing flushes the changes stored in the committed map to the disk. Reads have to check first the uncommitted map, then the committed map for any updates before turning to the file on the disk.

Thinking that even for random access files, it will be common that data is appended to the end, I have also given them an 'append buffer', which is very similar to the data structure corresponding to the sequential files. This buffer complements the maps, providing an efficient method to administer writes which append to the file. (At least I hope. I haven't actually carried out any performance tests.)

The actual files are only updated by the sync operation, and otherwise reflect the state of the commit just preceding the latest sync. So the only time when the files can become inconsistent is when the sync is interrupted. When that happens, it is detected upon the next startup, and the files are fixed. Here's how.

The sync operation queries the data describing the changes since the previous sync up to the latest commit from every file structure belonging to the manager. I call these chunks of information commit data. (It is a bit confusing, but in my head I consider the sync operation as a commit from the point of view of the actual files.) This commit data is not immediately applied to the files themselves, but first they are written to a commit file. I make sure that the commit file is entirely written to disk before going ahead and performing the file updates. After all the updates are complete and safe on the hard drive, I delete the commit file.

If the program is interrupted during the sensitive time of updating the data files, the commit file doesn't get deleted; this is how the problem is detected when the program starts the next time. In this case, I perform restoration as part of the initialization of the library, before anything else. I read the contents of the commit file, and with all the commit data in hand, I virtually redo the sync operation, fixing the state of the files. When that is done, I delete the commit file, and now the program is ready to start.

Now, if the sync operation is interrupted not during the file updates but during the creation of the commit file, then the restoration will find an incomplete, incorrect commit file. In this case, this commit is deleted and abandoned. The actual data files are in a consistent state, since the last sync operation did not finish writing the commit file, it didn't get to the part where it even touched the data files themselves.

That's about all I wanted to say about this. The system of course doesn't protect from disk corruption or from outside modification (or deletion) of the data files, but that wasn't my goal. Now I can be safe that even if the program is interrupted during a file update, the graph and all related data structure will be fixed, and the results of all the work cannot get lost so easily by an accidental reboot or the free space running out or something.

I must say, I'm quite proud of how this system works.

GameCracker - 6. Persistence

Due to the time and storage demand of the task at hand, it is obviously not viable to store the graph in memory. So I use the hard drive.

For some reason, I decided that I would store the graph in a series of files whose size is about 2 gigabytes. Each node has a unique 64-bit identifier. The top half of the ID is the index of the file containing the node, and the bottom half is the position within the file. This ID can be used to reference nodes, which is necessary to implement edges and category chains.

Apart from the graph files, I have a descriptor in which I store some global info like the game in question, the current graph file and its length, and the number of normal and transformation nodes. For convenience, I have a separate file which just lists all the node IDs. The ID file is not useful for normal operation but it helps when I want to traverse the graph for example for testing purposes.

The final file required by my program stores the category heads. This is a file-based mapping from category to node ID. The category chains are implemented by having each node store the ID of the next node in the chain.

Now I shall describe how exactly I store the nodes. The first byte contains a flag which marks the type of the node as either normal or transformation, the result of the node, and the player to move. Then there is a block of parent IDs. I mentioned that I need to store the parents of each node in order to properly update the results of the nodes. However, unlike the number of children (which is just the number of legal moves in the state), the number of parents cannot be known in advance, the list of parents must be allowed to grow indefinitely. So I allocate blocks of IDs, mark the empty spaces with an invalid ID, and when a new parent is added when only a single slot is left, then I allocate a new block at the end of the file, and write the ID (the file and position) of this block into the last slot. This creates a linked list of parent ID blocks, which does the job I need. So after the first byte, I have this first parent ID block. Then I have 8 bytes for a single node ID; I call this the referenced node. For normal nodes, I use this for the category chains, I write here the next node in the current chain. For transformation nodes, as they can have only a single children, I store it here. Note that transformation nodes need not be included in category chains, since if a new state is related to a state in a transformation node, then it must be related to the normal node to which the transformation node points, and this normal node will reside in a chain, so it can be found for the new state. Then, if I want to minimize the number of nodes, I can check the parents of this normal node for a transformation node which will be exactly what is needed, so I can still avoid creating multiple identical transformation nodes.

Okey, so after the referenced node, a transformation node has the transformation written into it, and that's all. A normal node has the number of moves (or equivalently, the number of child nodes), and then the IDs of the child nodes, initially containing invalid IDs until the corresponding move is expanded. For this to work, I need that the state always generates its possible moves in the same order so that I don't need to store the move itself, its index will suffice. Finally, the state itself is written to the normal node.

That's about all. This structure allows relatively straightforward implementation of everything I need. Let me just describe in terms of the stored format how I do expansion.

When the graph is requested to expand a certain child of a node, I first check if this child is not yet expanded. If the corresponding child node already exists in the graph, then this expansion request is an error. Then I read the state from the node, perform the move on it, so I obtain the state of the child node. I compute the category of the child state, and traverse the category chain, reading the state from each node in the chain to check for relations. If one is found, and it is an identical state, then this will be the child node itself. If it is a state related through a non-identity transformation, then I check the parent nodes for a transformation node with the same transformation; if one is found, then this will be the child node itself, otherwise a new transformation node is created, its child is set to the node found by the category search, and used as the child node. Finally if no related state is found, then a new normal node is created, inserted into the category chain, and used as the child node.

Either way, the child node is properly connected to the parent. Establishing this connection, and also establishing the connection between a new transformation node and its child, entails an update of the results, at least if the result of the child node is not unknown.

Also, whenever a new node is created, the corresponding node counter in the descriptor is incremented, and the new node is added to the ID list file. I might have missed something, but certainly not a lot. Except for the category head store itself, which I will get back to later.

GameCracker - 5. Categories

I have described why it is bad if we don't realize that a new state is the same or (symmetrically) equivalent to one that is already in the graph. I need all the help I can get when it comes to reducing the number of nodes. However, even if I do the best job possible, then - for complex games like chess - I still need an enormous number of different states to prove any interesting results. So searching the graph to see if a new state is a duplicate can be a serious issue. In particular, traversing the graph is out of the question.

My solution is the concept of categories. A category is basically a hash: a number that I assign to the states and I require that for symmetrical states, the category be the same. Then when a new state is about to be added as a result of an expansion, I query the category of this new state, and with this in my hand, I only need to check the nodes for which the category is the same (since, by definition, states with a different category cannot be related).

To implement this, I have included links in nodes which point to the next node of the same category. So for each category, I have a linked list, which I call a category chain, containing the relevant nodes. When searching for a related state, I just walk through the chain for the appropriate category, and if I don't find a match, then I can safely say that this state is new. The structure storing the category chains is a mapping from the category to the first node of the chain; this I call category heads.

Since adding new states to the graph is the elementary operation of the program, I need the search to be quick, I need the category chains to be short. This means that the categories need to be good hashes, with few duplicates, many different values for different states. On the other hand, if there are too many categories, then storing and accessing the heads quickly can also be an issue. Finally, if symmetrical equivalences are possible, then the creation of the category number itself can be difficult as well; extracting the most information possible into the value while making sure that all the transformed versions of this state produce the same category.

I will probably come back to some of these issues later, but for now, I have introduced the concept of categories, quite an important component of the program, and there are a couple more significant things I want to cover before delving into details.

GameCracker - 4. Results

I've described the state graph of a game, and how results of certain states can be proven. I've also talked a little bit about how I store only a small portion of the entire state graph, as small as necessary for my purposes. From now on, when I say 'graph', I will mean the data structure of my program, consisting of normal and transformation nodes, and (usually) having a whole lot of edges that do not connect to anything. I call these edges 'unexpanded moves', for some reason.

There's an important aspect of the graph that I need to mention. In order to facilitate proofs, I attach to each node a result field, which indicates the most information that we currently know about the result of the state. In the early days of development, this field had four possible values: Unknown, WhiteWins, BlackWins, and Draw. Then I realized that by adding two more, I can further reduce the size of my graph. These additional values are WhiteWontWin (meaning that the actual result will be either Draw or BlackWins) and BlackWontWin.

In order to see how these values help, imagine that we are in a state 'A' where White is to move, and there is still a possibility that at least one of White's moves will lead to her winning the match. Let's call one of these moves (and also the state that this move leads to) 'P' for 'possibly good'. Now, if we find out that a move leads to a state in which the result is WhiteWontWin (let's call this move and state 'BD' for 'BlackWins or Draw'), then it is greatly beneficial to postpone the examination of this move and first consider 'P', which still might lead to a WhiteWins state. Here's why. If the actual result of this state 'A' is WhiteWins, then we will need to find a move which leads to a WhiteWins state; the 'BD' move is obviously not the correct one, and we won't need the actual result of this move for our proof, so calculating it is a waste of time, building this part of the graph is unnecessary. On the other hand, if the actual result of the state 'A' is not WhiteWins, then to prove it, we will need to prove that none of the moves can bring victory to White, and this includes finding out more about 'P'. So we will need to work with 'P', and there is a possibility that we won't need to work with 'BD', and this latter fact we wouldn't know if there weren't a WhiteWontWin state, if BD were still Unknown.

Proving something about P will be necessary for proving anything about A. However, trying to proving something more about BD might be a waste of time.

Now, to the main point of this entry. The graph object provides a single important operation (other than being able to more around in it). Given a node and a move from this node that isn't connected to anything yet, this operation connects this 'unexpanded' node; I call this operation 'expand'. Two very important operations need to be performed during expansion. The first is the update of the results of any nodes for which this new connection allows us to prove something more than we could before. It is of utmost importance that the result value of every single node is always up-to-date and is the most concrete possible. The second task is to try and find an existing node which is equivalent to the new state, so that we won't have multiple instances of the same subgraph. I'll come back to this latter issue, because in this entry, we're talking about results.

So how to update the results during expansion? There are two cases when we obtain additional information. One is when we add a new node to the graph which contains an end state. (In end states, we know the result by definition: it is the result of the match.) The other is when a connection is made to an existing node in which we have a non-Unknown result. Both cases might provide some information on the result of the current node, the one which is being expanded, so we update its result. A result update consists of a recalculation of the result, and - if the new result is different from our previous knowledge - a recursive update of all the parents of this node (for this reason it is important to store references to the parent nodes). Recalculation is performed along the lines described in the second entry of this series, but of course extended for the two additional -WontWin possibilities. I think it is not too interesting an algorithm to describe here; I basically drew a big table with all the possibilities regarding the results we can find among the next-states, and see what we could say. I needed to be careful so that I don't accidentally label a state with a result which is too weak (like say that it is Unknown when WhiteWontWin can be proven, or say that it is WhiteWontWin when Draw can be proven etc.). Now this algorithm is in place, and I don't need to worry about it, I just need to choose the next state and move to expand, in a way which preferably results in the smallest number of expansions.

That's all for this entry. Next time I talk about the other aspect of expansion, the search for equivalent states. The reason this will be an issue is of course the humongous number of nodes in the graph.

GameCracker - 3. Graphs

The data structure that I use is (a subset of) the state graph of the game. The state graph is a useful model of the game in its entirety.

Imagine that we use dots to represent states of the game; we call these the nodes of the graph. They don't have to be dots, they could be small drawings of the current board for easy visualization. Then from each of these nodes, we have arrows (or edges in graph terms) going out and pointing to different nodes. These represent the possible moves in the state corresponding to the node. It can be useful to put some textual representation of the move onto the arrow as a label just so we can easily find our way. Then we can imagine that actual matches are just a path in this graph, starting from the root node, which denotes the initial position, and moving along the edges which correspond to the moves that the players actually make. We can also think of this the other way around: if we start from the initial position and move along the edges until we reach a node which has no outgoing arrows, no legal moves, then the path we take defines a valid match that could possibly happen between two players.

Just so I can talk about stuff, let me define a couple of notions. I call a state S2 a child of another state S1, if there is an edge leading from node S1 to S2, or (in different words) if there is a move in S1 which results in S2. Appropriately, I call S1 the parent of S2, because you can get to S2 from S1 with a move. Finally, I will use the term leaf to refer to nodes which have no children, these are the end positions of the game.

Now I think is time for an illustration.

 

It is a very-very small part of the state graph of tic-tac-toe. In the actual graph, the root node has nine children, each of these nine children have eight children of their own, which means that if I wanted to draw the entire graph but only up to two moves, that would mean 1+9+9*8=82 nodes, so now you can probably forgive me for only drawing 9 of them, it was not only laziness.

My main point with this is that state graphs are huge. Even in a game as simple and limited as tic-tac-toe, the number of nodes is enormous. The graph, up to 5 moves (which is the length of the shortest possible match) contains 18730 nodes. If we consider chess, or some other, more interesting game, the size of the state graph is astronomical.

My program works by building up a part of this graph. It will never need the entirety of it due to how results are proven, which I described in my previous entry. As an example, suppose that chess can be won by White after the first move e2-e4. In this case, all the other 19 moves that White could start with are totally uninteresting and there is no need to consider them. This makes huge parts of the state graph irrelevant that we do not need to build up, because they are not needed for the proof of White's win in the initial position.

Another thing that I mentioned previously is that I definitely want to avoid doing the same work multiple times. In terms of the graph, this means checking if a new state that we come across is equivalent to one which we have already encountered and added to the graph. If it is, we can just draw the arrow to this existing state and not have to create two instances of everything beneath it. Example incoming!

Nothing complicated is happening. This does mean that nodes can have multiple parents, but administering this is a small price to pay.

I have described a different kind of equivalence, where two states are not the same, but are symmetrical, and thus we still don't need to examine both of them. These I handle differently, since just plainly connecting them would violate what the arrows mean. In order to note that this move leads to a state that is related an existing one through some transformation, I use a different kind of node, which I call transformation node (and, in contrast, I call normal nodes ... normal nodes). The semantics of edges leaving a transformation nodes are different, they do not model moves, they model the transformation. So each transformation node has a single arrow leaving it, and this arrow points to the other, symmetrical state. I also store the exact transformation in the node. Example to the rescue!

What I have drawn here is the same subgraph of the tic-tac-toe graph as in the first illustration, but using transformation nodes. Due to the fact that I have included only ten states in the first place, we cannot see any great benefits at first glance (we still have ten nodes), but note that originally there were seven nodes which required further work, now there are only three. Once we have added a transformation node, we basically don't have to worry about it as an individual state, only the normal node that it references. Of course when we move around in the graph, we need to take special care around transformation nodes, they will not need any extra effort to prove beyond what is needed for the corresponding normal node.

So this is the basic structure. Tune in for the next time when I describe how the result of the individual nodes are created in a way that also provides all the aspects of provability that I talked about in the previous entry.