Please start any new threads on our new
site at https://forums.sqlteam.com. We've got lots of great SQL Server
experts to answer whatever question you can come up with.
| Author |
Topic |
|
aiken
Aged Yak Warrior
525 Posts |
 Posted - 2002-08-25 : 00:54:28
|
| Mostly for the fun of it, I've decided to implement a game of chess in SQL, with an ASP frontend. The ASP frontend will strictly be UI; proposed moves will be sent in to a stored procedure, which will check the validity of the move, deal with any game state changes (check/checkmate/stalemate), update the board, and return the completed board to the ASP application.Of course, the whole point of the exercise is to sharpen my SQL skills and come up with an elegant solution. I think I have the whole thing, except for board management. I've got a couple of possible alternatives, and I'd love feedback from the knowledgeable types here about which is the "best" solution (in this case, "best" is defined as manageable, error-resistant, and high-performance, like most SQL projects).Option 1 (a couple of freeware ASP chess implementations use this): The board is stored as a delimited varchar field of 64 entries. For instance, a sample row of 8 might be "-1,-1,1,-1,4,-1,-1,10", which would translate to "blank, blank, white pawn, blank, white bishop, blank, blank, black rook". Moves parse this field, edit it as necessary, and update the field. This seems pretty unweildy to me.Option 2: The board is implemented as a table with 65 columns; an index into a game, and then 64 tinyints, each one representing one square on the board. This is similar to option 1, but does away with parsing and creating delimited strings, and using GetRows it would be amenable to being manipulated as an array in ASP.Option 3: Each game creates a "game_pieces" table with the 32 starting pieces and their x,y coordinates. The "board" table is a join table of the game and piece ID's. IE, "game_pieces" gets 32 entries at the start (8 pawns for each side, plus the other 8 pieces), each with their coordinates. During the game, pieces coordinates are changed; if a piece is taken, it's deleted from the table. If a piece is promoted, its "piece_type" field gets updated to something else. Option 4: Every possible chess scenario is pre-generated into one very large table, so when you move a piece you just update the bigint "board_layout" field of the game. That's a joke!Option 3 seems like the most normalized, SQL-ish approach. What do other people think? Or is there another, better approach that I'm not thinking of?Cheers-b |
|
|
r937
Posting Yak Master
112 Posts |
Posted - 2002-08-25 : 09:21:22
|
| very cool idea, using sqlthe normalization police will surely come after me, but option 2 is fine, and it has game history built in, toohow many times have we built a person table with two lines for address? bzzzt, not normalizedhow many times have we built a person table with two fields for first name, last name? bzzzt, not normalizedhow many times have we built a person table with two fields for height and weight? bzzzt, not normalized (they are different only in unit of measure)normal or not normal is in the eye of the beholder -- if you fully normalize, everything ends up in two-column tables (pk and one other column)the 64 squares are as different as addressline1, addressline2, or first name, last name, or height and weightthe only other table design that comes to mind at the moment is the one which tracks moves --1. e4 e52. Nf3 Ng6etc.but this is awkward because you have to re-create the latest position right from the opening move every timerudyhttp://rudy.ca/Edited by - r937 on 08/25/2002 09:22:46 |
 |
|
|
aiken
Aged Yak Warrior
525 Posts |
Posted - 2002-08-25 : 12:39:30
|
| I'm not so sure... my problem with option 2 isn't dogmatic normalization, but the logistics of determining whether, say, the king is in check.Imagine a situation where a white rook is at a1, and the black king is at h1, with no pieces between them.In option 2, to test whether the rook has the king in check, I think you'd have to use dynamic SQL. If a1 is "field1" and h1 is "field57", you'd have to check field9, field17, field25, field33, field41, field49, and field57. Of course, if the scenario shifts to a2 and h2, all of those field names are off by one. The only way I can think of making that work is with dynamic SQL, which is ugly.I'm leaning towards option 3. That same scenario works much more elegantly; to determine if the king is in check, you use a table variable and add to it every square that any white piece threatens. If the king's coordinates are in that table, he's in check. It's easy to see if the king can move out of check by testing every square the king could move to against that table. However, I'm not sure how to detect whether a piece could be moved to block the check without doing this whole test for every possible move of every piece.I think the key thing here is having the coordinates be information in the table, rather than part of the schema. Operations on the coordiantes are a lot easier that way.I'm still not convinced that I've got the best board representation schema, though... any thoughts on that?Cheers-b |
|
|
|
Lavos
Posting Yak Master
200 Posts |
Posted - 2002-08-25 : 13:37:01
|
| I actually don't remember how most implementations implement the board, but I do know of at least one that implements it by having a linked list of all the pieces with their current position. Others also implement the board by using a multidimensional array.From either standpoint your schema will work, though I think the table of pieces that store their position is much better as far as sql is concerned. You would probably either do a crapload of typing, or coming up with procedures that wrote the dynamic sql to go with option b. (as you've already foreseen.) (You could use option a and use a view with a sequence table joined to it to expose it as option b, then you can have the best of both worlds.) Persnoally, I'd go with the pieces table.Here's another idea (that I'm sure I ripped off of someone else, but I can't remember where. Most likely from the gnu chess source.) Pre generate every move by every piece type for every position. The real problem is finding blocked paths, which can be done by including a sequence and route column and returning the squares the piece can move to for each route where the sequence numbers are less than or equal to the minimum sequence number of an occupied square on that route. Your move tests, check conditions, finding pieces that can move to a square, it can all be done by joining if you take this path.Of course, pawns are going to be a problem implementing since they move differently when capturing and moving, and white and black pawns move differently from each other also. I haven't worked it out, but I think it'll require more than a few case statements (that's not even counting en passant!)Anyway, I think it's a great idea for a side project that I'm going to steal :) Though ironically I'm going to use it to gain some asp skills, LOL.----------------------"O Theos mou! Echo ten labrida en te mou kephale!" |
|
|
|
aiken
Aged Yak Warrior
525 Posts |
Posted - 2002-08-25 : 20:45:56
|
| Pawn movement shouldn't be an issue; either define the possible moves relative to the each side of the board (pawns would be the only piece affected by this, as everyone else can move symmetrically), or have a multiplier for "forward" which is -1 for black. Pawn captures may take a special case (only legal to move to the square if it is occupied). En passant is definitely nastier, as it involves removing a piece without actually occupying its square.I like the pre-generating idea, with the route and sequence. Makes a lot of sense, and you're right that it makes move validation a case of joins, except for pawn captures, en passant, and castling. There's also the "can't do a move that would put you in check," but if threre's a general "Is user in check?" function/procedure, the trick would just be updating a temporary table with the proposed move once it's validated, and then test if it resulted in a "check" situation; if so, discard the temp table and return an invalid move status code.Thanks for your help here; definitely helped clarify it in my mind.Cheers-bEdited by - aiken on 08/25/2002 20:47:12 |
|
|
|
|
|
|
|
|
Fun & Games: Chess. Schemas, etc?