There is a gambling game called blackjack, played with a 101-sided die (0-100)
A better rolls, and can choose to hit or stay, if the better hits then the dice is rolled again, if the better stays the score of the better is the sum of all the rolls the better has done. If the better hits, and the sum of the rolls that the better has done gets over 100 the better automatically loses. Once the better has stayed the host repeats this process, winning if he manages to stay on a value that is higher than the better, but is lower than 101, and losing if the host goes over 100.
There are 2 questions to this:
What is the optimal strategy for the better?
Given the optimal strategy of the better, what are the chances to win, i.e., what is the expected outcome?
I'm quite confused on how to even start with it, given that the potential game length can be infinite if a 0 is rolled repeatedly, the amount of possible combinations of the game is not computeable (brute force).
I assume the solution will have something to do with 101x101 matrix multiplication, but other than that I don't really have a clue where to even start.
What should you do if the total is currently $100$? Clearly stay, with payoff $100$.
What if it's $99$? Well, if you hit, you stay at $99$ with probability $1/101$, you reach $100$ with probability $1/101$, and you bust with probability $99/101$. The expected payoff satisfies $$ H_{99}=\frac{1}{101}\cdot100+\frac{1}{101}H_{99}, $$ or $H_{99}=1$; this is less than the payoff if you stay ($99$), so you should stay.
Continue in this way, working backward. You'll find that you should stay if the current total is $\ge T$ for some particular $T$, and hit for all lower totals, and you can calculate the expected payoff for each current total.