<p>I have an enumeration scheme, but it requires an array of integers. If you can compress an array of integers to a single Q value (and back) then this might work.</p>

<p>First comes N, number of pieces on the board.</p>

<p>Then comes the array of ceil(N/2) items, the X pieces. Every number is the count of empty valid spaces from the previous X piece (or board start). IMPORTANT: space is not valid if it would result in game end. This is where 5 in a row end rule helps us reduce the domain.</p>

<p>Then comes the array of floor(N/2) items, the O pieces. Same logic applies as for the X array.</p>

<p>So for this board and 3 piece rule:</p>

<pre><code>XX.
X.O
..O
</code></pre>

<p>we have the following array:</p>

<p>N: 5<br>
X: 0 (from board start), 0 (from previous X), 0 (top right corner is invalid for X because it would end the game)<br>
O: 2 (from board start, minus all preceding X), 2 (from previous O)</p>

<p>and that's the array [5, 0, 0, 0, 2, 2]. Given this array we can recreate the board above. Occurrence of small numbers is more probable than that of big numbers. In regular game with 19x19 board the pieces will group together for the most part, so there will be a lot of zeros, ones, twos, delimited with occasional "big" number for the next line.</p>

<p>You now have to compress this array using the fact that small numbers occur more than the big ones. General purpose compression algorithm may help, but some <a href="https://arxiv.org/abs/1209.2137" rel="nofollow noreferrer">specialized</a> may help more.</p>

<p>I don't know anything about q-learning, but all this here requires that q-value can have variable size. If you have to have constant size for q-value then that size would have to account for worst possible board, and that size may be so big, that it defeats the purpose of having this enumeration/compression in the first place.</p>

<p>We use left-to-right and top-to-bottom method to enumerate pieces, but we could also use some spiraling method that may yield even better small-to-big numbers ratio. We just have to pick the best starting point for the spiral center. But this may complicate the algorithm and waste more CPU time in the end.</p>

<p>Also, we don't really need the first number in the array, N. Length of the array gives this information.</p>
The huge amount of states in q-learning calculation
<p>I implemented a 3x3 OX game by q-learning ( it works perfectly in AI v.s AI and AI v.s Human), but I can't go one step further to 4x4 OX game since it will eat up all my PC memory and crash.</p>

<p>Here is my current problem:
<a href="https://stackoverflow.com/questions/56231392/access-violation-in-huge-array">Access violation in huge array?</a></p>

<p>In my understanding, a 3x3 OX game has a total 3(space, white, black) ^ 9 = 19683 possible states. ( same pattern different angle still count )</p>

<p>For a 4x4 OX game, the total state will be 3 ^ 16 = 43,046,721</p>

<p>For a regular go game, 15x15 board, the total state will be 3 ^ 225 ~ 2.5 x 10^107 </p>

<p>Q1. I want to know my calculation is correct or not. ( for 4x4 OX game, I need a 3^16 array ? )</p>

<p>Q2. Since I need to calculate each Q value ( for each state, each action), I need such a large number of array, is it expected? any way to avoid it?</p>