** Next:** State encoding TD-Gammon
** Up:** TD-Gammon
** Previous:** TD-Gammon

##

MDPs with a very large number of
states

What happens when the number of states is too large to
enumerate?
For example: the game of backgammon.

Board description: there
are 24 positions on the board.

Pieces: each player has 15
pieces.

The goal: to bring your pieces to your side of the
board, and then remove them.

Game play: In each turn a player
throws two dice, and moves his pieces accordingly.

Interaction:
- 1.
- If a white piece is the only one in its position, and a black piece reaches that position,
the white piece is removed, and needs to start from the beginning.
- 2.
- If two or more white pieces are in the same position, then a black piece can not "land" there.

End of game: The one who removed all his pieces out of the board
first wins the game.
Lets try to estimate the number of states in backgammon:
Descrption of a state: For every position of 24 + 2, remember the
number of pieces of each color which are located there. Number of
states for one player's pieces:
.

Total number of states
.

** Next:** State encoding TD-Gammon
** Up:** TD-Gammon
** Previous:** TD-Gammon
*Yishay Mansour*

*2000-01-17*