<br><br><div class="gmail_quote">On Tue, Jul 3, 2012 at 3:08 PM, Miheer Dewaskar <span dir="ltr"><<a href="mailto:miheer.dew@gmail.com" target="_blank">miheer.dew@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <<a href="mailto:python.list@tim.thechases.com">python.list@tim.thechases.com</a>> wrote:<br>
</div>I want it to be a generic Game solver.So the number of states depends<br>
on the game.<br></blockquote><div><br>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.<br>
 </div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
For a simple tic-tac-toe the upper bound is 3^9 states.But for more<br>
complex games it could be much larger.<br>
I would like to assume that the number of states can grow arbitrarily large.<br>
<div class="im"><br></div>
For example in the tic-tac-toe game the states can be a 3x3 box of integers<br>
<br>
 0 -> unoccupied<br>
 1 -> x<br>
 2-> o<br>
<br>
(  (2,0,1),                 o   -   x<br>
   (1,1,0),         ->     x  x   -<br>
   (2,0,0) )                o  -    -<br></blockquote><div><br>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:<br>
<a href="http://en.wikipedia.org/wiki/Zobrist_hashing">http://en.wikipedia.org/wiki/Zobrist_hashing</a><br><br></div></div>