Monday, November 10, 2008

Wow... (update on Zilch research)

I grossly underestimated the size of the game space. I was thinking it'd be in the billions. It turns out to be about 64 trillion states. Searching the space will require some memoization to speed up the time (because the expected value nodes are 55,987 branches wide) , but I can't memoize the entire space unless I had an exabyte of RAM available (need someone to get on that real quick :D). I'll use some strategies to reduce the size of the space, and maybe a caching strategy to only memoize the states that are needed at the moment. More updates as I progress tomorrow. I need my sleep.

4 comments:

Leadhyena Inrandomtan said...

At least the search space is smaller than Checkers, and that has been solved. LOL

ThetaPhi said...

I'm surprised the game space is finite ^^

I'm in the preparation stages to write an EV function (expected value) which should take as parameters the game state and a decision (which dice to score and whether to bank or to roll) and returns the expected score.

The first problem that comes to mind is that in case all dice get scored, you enter a new iteration with all six dice. In theory you could enter infinite recursions, but thankfully the probability of multiple free rolls converges towards zero fast. Now I have to come up with a series that models this...

Bartolomew said...

Hi, i hope you are still working on the project. I'm still very excited about the outcomes.

As for the "free roll" problem I think you could just start with scoring free rolls with 0 points and see what expected score (lets call it s) you get out of 6 dice without taking free rolls (e.g. forfeiting instead of making a free roll). Also note the expected probability p for scoring a free roll. Then you have a formula like this for the expected free roll score (or effective expected score with 6 dice) x:

x = SUM(n=0..inf)(p^n) * s

I'm sure I'm missing something here, as it seems so simple right now.

I use "expected" instead of "average" as i assume an "intelligent" choice of dice to score. A problem i see there is that deciding what is "intelligent" depends on what your expected score with a free roll is. So maybe for choosing scoring options you'd have to assume some number for x first and revisit that later.

Albert said...

So I was playing Zilch and came across your blog yesterday. I thought you were going to do math in your next post, not more programming? :)

I'm wondering where you came up with the 64 trillion game states.

Like ThetaPi and Bartolomew, I also approached this problem by formulating the Expected Score. My analysis only depends on number of dice, not game state. (Rationale: if you are rolling 6 dice, the score you expect to get is the same regardless of your previous score). My equations are complete, but I stopped short of computing actual values due to a small problem... see my article.

I don't have a blog, and since I wanted LaTeX to make my equations anyway, I wrote up a whole document at http://zalbee.intricus.net/zilch.pdf