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: $\cong 2.5 \times 10 ^{10}$.
Total number of states $\cong 10^{20}$.