Best data structure for DFS on large graphs

[Dan Stromberg]

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>
> wrote:
> 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
> large.
>
> 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:
http://en.wikipedia.org/wiki/Zobrist_hashing
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120703/16ada623/attachment.html>