Best data structure for DFS on large graphs
drsalists at gmail.com
Tue Jul 3 18:19:26 CEST 2012
On Tue, Jul 3, 2012 at 3:08 PM, Miheer Dewaskar <miheer.dew at gmail.com>wrote:
> On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list at tim.thechases.com>
> I want it to be a generic Game solver.So the number of states depends
> on the game.
Keep in mind that it would probably be a generic game solver for games that
have simple board evaluation functions. For something like Go, despite its
simple rules, much more is required.
> For a simple tic-tac-toe the upper bound is 3^9 states.But for more
> complex games it could be much larger.
> I would like to assume that the number of states can grow arbitrarily
> For example in the tic-tac-toe game the states can be a 3x3 box of integers
> 0 -> unoccupied
> 1 -> x
> 2-> o
> ( (2,0,1), o - x
> (1,1,0), -> x x -
> (2,0,0) ) o - -
For just saving game board states to avoid re-traversal, I'd think a set
(if you require no ancillary information) or dict (if you do) would be
appropriate. But perhaps consider Zobrist hashing:
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list