The 1.1 release of Haskell Spider Solitaire has been posted to the usual location (check the links to the right).
The major change is switching the representation of the tableau. All the manipulation of the tableau occurs at the bottom of the board as the human player sees it. Previously, the data representation matched the screen presentation, and that meant manipulating the tails of each column (which are just lists). Following a suggestion by chessguy (thanks, if you're reading this) that has been reversed. So the bottom of each column as seen by the users is at the head of each column list.
So the display of the board is slightly more complicated, but the internal mechanics of moving cards is simpler, and some helper functions have been eliminated.
So the next task is to start exploring the move tree for a particular game. As part of that, I think we'll want to somehow create a hashtable for each board position encountered so far during a game. to prevent repeated positions. I suppose I could assign a number to each unique card, flatten the tableau and stock, and calcuate a hash based on that.
While there are something on the order of 108! divided by 2^56 possible starting positions, and approximately that many possible board positions, you can only see a small fraction of those starting from a particular board position. I also don't know just how big a move tree is for a typical game either. A winning game can easily run 500 moves deep. And it is common to have 3 or 4 possible moves from a given position. But there are a lot of very quick dead-ends, and the deepest games are the winning ones... of which there may only be a low number of total solutions, and a low number of paths to each solution.
I'm sure a mathematician could give accurate answers to at least some of these questions. Since I am not one, I'll turn to empiricism instead. This is where we generate thousands of games, and collect statistics.
Subscribe to:
Post Comments (Atom)
2 comments:
Regarding hash tables, you may want to take a page from the chess programming playbook (if you want to search for more info, look for the phrase 'transposition table').
In chess, what we do is to hash the entire board once. Then whenever we put a piece on the board or take one off, we modify the hash in a predictable way, such that 'put a white knight on e4' and 'take a white knight off e4' are inverse operations on the hash. This way you can simply modify the hash, rather than rebuilding it from scratch every time.
Good job with this, I'm watching with great interest.
A small clarification:
108! divided by 2^56 possible starting positions
By this I mean literally (108! / 2^56) possible starting positions.
I appreciate the pointer to 'transposition table' in chess programming. The interesting thing about Spider Solitare is that many of the moves are 'one-way'. Meaning that after that move is made, there is no way to get back to the previous board state.
Sure, there are pathological cases where you can move an 8 from one 9 to another 9, and back again. But just looking at the last few moves should prevent those sorts of repeats. So the pruning should be easy to handle.
I guess I need to start exploring the move tree in general to see how big it is first, and then think more about what we need to speed up analysis.
Post a Comment