Optimize Algorithm For Shut in Box Game This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices. Each round, the player rolls the 2 dices and their sum is S. After that, there are two options. The first option is to find the tile equal to S. If it is unflipped, you can flip it so that the tile becomes flipped up. The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:
If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it or be equivalent to it, the player loses.
The problem is to simulate the game 100,000 times and improve the win percentage.
My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.
Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?
 A: There is a table given here which indicates the optimal play given the current board state:
http://www.durangobill.com/ShutTheBoxExtra/STB2DICE.txt
Also this question has been answered here:
https://boardgames.stackexchange.com/questions/35476/whats-the-strategy-for-shut-the-box
A: You can use dynamic programming to find the optimal strategy. 
Go through the positions of the game, starting with the ones that are closest to the end of the game. For each state, compute the probability of winning. This is done by computing, for each die roll, the options you have available to you, selecting the one which gives you the best chance of winning (which you have already computed), and then summing up the win-probabilities of your best option times the probability of that die roll. You should also write down what that those best options were in each case. At the end, you will have the probability of winning from each position, and the optimal strategy in each position.
There are only $2^9$ positions, so I think this is computationally feasible. 
