next up previous
Next: methods of encoding Up: TD-Gammon Previous: MDP description

   
"Encoding" Functions $F:S\rightarrow\Re$

One way to implement F is by using a table. This enables us to implement any function F. The drawback in this approach is that the space needed is proportional to the number of states. Since, in backgammon, the number of states is very large ( $\cong 10^{20}$), using a table is impractical. We will implement F in way which does not enable any mapping $S\rightarrow\Re$. First, we choose a mapping $H:S\rightarrow U$, which for each state s maps a vector $\overrightarrow{u}$, which will "represent" it. Choosing such appropriate mapping h determines the performance of the algorithm. For example:
1.
TD-Gammon - $\overrightarrow{u}$ is a vector with 198 slots.
2.
21 (blackjack) - u is the sum of cards.
From here on, we exchange s with $\overrightarrow{u}=H(s)$, and perform the calculations on the vector $\overrightarrow{u}$. In the game of 21 there were few such vectors $\overrightarrow{u}$, and we could build a table for all of them. It is not the case for backgammon.

 

Yishay Mansour
2000-01-17