Drew Wutka
dbatech at wolfwares.com
Wed Oct 27 23:28:56 CDT 2004
Pretty simple on situation one. First, look at how many peices there are. 32. But, if you look the number of duplicate peices, you need to track the 'location' of 2 of each color of rooks, bishops, knights. Then you have to track 8 of each color for pawns. So the trick is to turn it into a comparable string, versus a ton of numbers. Tackle the kings and queens first. Each peice will represent one character in the string (first four characters, 4 bytes total). A byte represents overkill, because it can be 0 to 255, but we need to differentiate these four peices. So each character would represent it's peices position on the board. Now take the 2 rooks, knights, and bishops for each color. We can cheat. Let's just take the two black rooks. Let's say one is in square 10 and the other is in square 16. What we do, is we take the one in the 'lowest' position, and set it to the first 'character', and the one in the larger position will be the second character. Can't use one byte, because it takes 6 bits to represent 0 to 63. However we can always guarantee that 2 black rooks, in the same positions, will have the same characters in the same spots in the string, by setting them according to their 'position' on the board. Now for the pawns. This one is pretty easy. Take 8 characters each, but instead of marking individual positions, mark positions taken. 8 characters, or 8 bytes, represents 64 bits. Just turn on the bits within the total 64 bits, that represent spaces that have white pawns. This would ensure that pawns in the same position would have the same 'characters' represented in your string. So, all together, we have 4 bytes for kings and queens, 2 bytes each for knights, rooks, and bishops (total of 12 bytes), and 64 bits for each pawn color, a total of 16 characters. What you end up with is 32 characters. Every 'setting' of the board would be represented by those 32 characters. So if there are two times where someone is in the same position as another game, the strings will match. To determine the moves made, simply put a Game ID, and a Move Number field in. It wouldn't be that difficult to whip up some code to determine what was moved between the two strings. If you index the string field, you can immediately determine what other games had the peices in the same position, by doing a simple query based on that particular string. Drew -----Original Message----- From: dba-tech-bounces at databaseadvisors.com [mailto:dba-tech-bounces at databaseadvisors.com]On Behalf Of Arthur Fuller Sent: Wednesday, October 27, 2004 12:10 PM To: Discussion of Hardware and Software issues Subject: [dba-Tech] Questions about 2 Unusual Databases From time to time I ponder the following two databases, trying to come up with the optimal design in terms of both space and performance. This is strictly a question of personal interest, and I have no commercial interest in either solution. I simply find them interesting problems, and I thought I'd trot them out in search of feedback from my colleagues here. 1. A database that records chess games. It strikes me that perhaps the most compact way to store a game is by using the modern notation for the moves themselves. But in addition to recording the sequence of moves, the database would also be expected to record situations and be able to compare them. I.e. given two sequences, A and B, that both result in exactly the same position of pieces, irrespective of the number of moves it took to get there, the database should be able to detect this as quickly as possible. For example.... aha! This is exactly the same position that Bobby Fischer faced in year 19xx, when playing somebody at some tournament, but they got here in 11 moves and the current players got here in 13 moves. (The idea behind this requirement is that certain positions have known solutions, i.e. paths to checkmate.) 2. A music database that records (let's keep it simple in version 1) melodies and single-line compositions (i.e. ignoring instrumentation, harmony, counterpoint, etc.). The idea here would be to compare any two rows and determine whether they are identical. For example, George Harrison v. the Ronnettes, for "My Sweet Lord" and "He's So Fine" respectively. Ideally, this database should also be able to see past the selected key (in the musical sense), and also the tempo (piece A is identical to piece B but played twice as fast). Perhaps version 2 could also detect that melody A is identical to B except that it is inverted (upside down) or perhaps retrograde (backwards) or even retrograde inverted. Ok, database designers. There you have the specs. Any brilliant ideas out there for solutions? A. P.S. Although these are in fact strictly database issues, I am not going to cross-post to the AccessD and SQL lists because they are so obviously unrelated to the immediate problems most of us have when posting there. _______________________________________________ dba-Tech mailing list dba-Tech at databaseadvisors.com http://databaseadvisors.com/mailman/listinfo/dba-tech Website: http://www.databaseadvisors.com