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.
2011. június 20., hétfő
2011. február 13., vasárnap
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.
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.
2010. december 17., péntek
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.
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.
2010. december 1., szerda
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.
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.
2010. november 30., kedd
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.
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.
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. |
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.
2010. november 23., kedd
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.
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.
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.
2010. november 20., szombat
GameCracker - 2. From simple to not so much
The little pseudo-code I gave in the previous entry is a pretty straightforward algorithm to determine the result of a game state. Nevertheless, that is not quite how I do it. It actually had never occured to me to implement the program this way, and now that I have thought about the reasons, I can give you two.
First of all, it is not sufficient for me that my program tells me the result of a state: I need it to be able to prove what it claims. By this I mean that taking on the role of the player to move in that state, the program must be able to achieve the claimed result against any opponent, against any sequence of moves; and on the other hand, it must be able to prove that a better result can always be prevented by the opponent. This is a pretty abstract formulation, so let me be more concrete. Suppose that we are in a state where it is White's turn to move. If the program says that White will win, proving this means providing a move, and (recursively) proving that the state after the move is also a win for White. To prove a draw result, it has to be able to indicate a move, proving that the state after the move is a draw, and also proving that none of White's moves will bring her victory. Finally, Black's win can be proven by showing that the state after every single one of White's moves is a loss for her.
Maybe I'm talking a bit too much about the concept of proving a result, but I'll just describe it from another aspect. Suppose that the program has solved the initial state of a game. If it turns out to be a win for White, the fact that my program can prove this claim means that by playing White, it can always win, against anyone, no matter what. In case of a draw, my program playing White can always achieve at least draw (so it will never lose), but this alone isn't enough, it needs to be shown that White has no winning move. Proving this means that the program has to also be able to achieve at least a draw when playing Black. Finally, if chess is actually winnable by Black, then of course my program must be able to win with the black pieces. And one last thing: when the program is actually playing one of these games, I want it to be able to give the correct moves in a very short time, basically using some look-up method, and not by performing a search like chess engines do. This would not be possible using the simple algorithm.
The second reason against it is that there are a lot of possibilities in a game. And I mean lot. I did say that I disregard any actual time and storage requirements, but still, there is one significant way of reducing the size of the work needed to prove results that I won't ignore. And it is to avoid calculating the result of a state multiple times.
Let us consider chess. Suppose that, after ten years of work, the program has finally obtained the result of the state after moves 1. e2-e4, e7-e6; 2. d2-d3, d7-d5. Suppose also that later the program finds itself at a point where it needs the result of the state after moves 1. e2-e4, d7-d5; 2. d2-d3, e7-e6. This is the exact same state as the previous one, but the naive little algorithm doesn't know that, and spends another ten years wth this state. I definitely want to avoid this. Now let me go one step further. There are also states that are, although different, similar enough so that the proof the program finds for the result of one is applicable to the other. I call this relationship either symmetry or equivalence. Reversi is an excellent example. In the starting position, White has four possible moves, but the resulting positions are symmetrical, basically the same. You just have to apply a transformation to the board (a rotation or a reflection) to get one from the other, and the proof for one is applicable to the other by applying the same transformation to the moves themselves.
So these were my two needs: the ability to prove claims about results of game states, and the ability to avoid computation of equivalent states. Next time, I'll describe how I've built GameCracker with these requirements in mind.
First of all, it is not sufficient for me that my program tells me the result of a state: I need it to be able to prove what it claims. By this I mean that taking on the role of the player to move in that state, the program must be able to achieve the claimed result against any opponent, against any sequence of moves; and on the other hand, it must be able to prove that a better result can always be prevented by the opponent. This is a pretty abstract formulation, so let me be more concrete. Suppose that we are in a state where it is White's turn to move. If the program says that White will win, proving this means providing a move, and (recursively) proving that the state after the move is also a win for White. To prove a draw result, it has to be able to indicate a move, proving that the state after the move is a draw, and also proving that none of White's moves will bring her victory. Finally, Black's win can be proven by showing that the state after every single one of White's moves is a loss for her.
Maybe I'm talking a bit too much about the concept of proving a result, but I'll just describe it from another aspect. Suppose that the program has solved the initial state of a game. If it turns out to be a win for White, the fact that my program can prove this claim means that by playing White, it can always win, against anyone, no matter what. In case of a draw, my program playing White can always achieve at least draw (so it will never lose), but this alone isn't enough, it needs to be shown that White has no winning move. Proving this means that the program has to also be able to achieve at least a draw when playing Black. Finally, if chess is actually winnable by Black, then of course my program must be able to win with the black pieces. And one last thing: when the program is actually playing one of these games, I want it to be able to give the correct moves in a very short time, basically using some look-up method, and not by performing a search like chess engines do. This would not be possible using the simple algorithm.
The second reason against it is that there are a lot of possibilities in a game. And I mean lot. I did say that I disregard any actual time and storage requirements, but still, there is one significant way of reducing the size of the work needed to prove results that I won't ignore. And it is to avoid calculating the result of a state multiple times.
Let us consider chess. Suppose that, after ten years of work, the program has finally obtained the result of the state after moves 1. e2-e4, e7-e6; 2. d2-d3, d7-d5. Suppose also that later the program finds itself at a point where it needs the result of the state after moves 1. e2-e4, d7-d5; 2. d2-d3, e7-e6. This is the exact same state as the previous one, but the naive little algorithm doesn't know that, and spends another ten years wth this state. I definitely want to avoid this. Now let me go one step further. There are also states that are, although different, similar enough so that the proof the program finds for the result of one is applicable to the other. I call this relationship either symmetry or equivalence. Reversi is an excellent example. In the starting position, White has four possible moves, but the resulting positions are symmetrical, basically the same. You just have to apply a transformation to the board (a rotation or a reflection) to get one from the other, and the proof for one is applicable to the other by applying the same transformation to the moves themselves.
So these were my two needs: the ability to prove claims about results of game states, and the ability to avoid computation of equivalent states. Next time, I'll describe how I've built GameCracker with these requirements in mind.
Feliratkozás:
Bejegyzések (Atom)