OkonomiDev
Thursday, November 21, 2002
      ( 9:01 AM ) Matt  

MySQL


MySQL is an open source database licensed under the GPL. You can freely distribute MySQL with your product as long as it is distributed under an Open Source Initiative, OSI, license. Basicly, that means it's free as long as your product is free. I just might use the MIT License for the distribution of Okonominet. It basically says, do whatever you want with this software.


Anyway, I am thinking about using MySQL for okonominet. I'm not sure how much information I'll put in the database though. It would be nice to be able to store every board position which has been explored. A flat representation would use 2 bits per intersection (white, black, empty, or ko). A 19x19 board would thus take about 90 bytes of space. If we want to make the representation flexible, and support up to 25x25 boards this might increase to about 156 bytes. Each game is about 150 moves long, and after the first few moves all games are unique. Only the first few board positions could be shared between games. Thus, each game (assuming a 19x19 board) would take about 13.5kB. One thousand games seems like a reasonable number of games to expect a client to store. This would take up 13.5 megabytes. That's looking a little large


For a comparison, the games could be stored in SGF format where each move takes 6 to 12 bytes. This is an order of magnitude smaller than storing each state individually. Why would we want to store the entire state of the board anyway? Well, it would make searching for information relating to a particular board state much more efficient. Let's say there are n games averaging m moves per game. Finding a particular board state in a database with every board state stored can be done in O(lg(n*m)) time. If the board state must be derived from only the move information, it could be done in O(n*m) time. For large databases this would be unacceptable. It would be nice to have Okonomigo clients query other clients for information about a particular board state. This may be useful for Game Exploring as described on November 12, 2002


Let me propose some table definitions for such a database, and you can let me know what you think about it.



BoardState(UID, state)

Move(UID, x, y, color, initialStateID, finalStateID)

Node(UID, boardStateID)

Comment(UID, nodeID, type, valueID)

TextComment(UID, text)

GameTree(UID, move, lastMove)


To give you an idea of how these tables might be used, here are some example queries


Select all the text comments for a particular board state:

select text from TextComment, Comment, Node, BoardState where TextComment.UID = Comment.valueID and Comment.type = 'T' and Comment.nodeID = Node.UID and Node.boardStateID = BoardState.UID and BoardState.state = desired_board_state;


Select all the moves for black following a particular board state:

select x, y from Move, BoardState where Move.color = 'B' and Move.initialStateID = BoardState.UID and BoardState.state = desired_board_state;


There will have to be additional tables for additional game information. There could be a table mapping comments to the source of the comment, or that information could be added to the comment table. Much more information could be added to this database.

# -




Comments: Post a Comment
archives:


Dreams I have...

Powered by Blogger
Feel free to e-mail me.

free hit counter