optimal win/tie percentage against random player

user_14722475 0
Viewed 148

I'm made my own version of Tic-Tac-Toe in R based on specific hardcoded custom rules. After some optimization I am now unable to improve the play. I benchmarked the bot against a random player in the following ways:

  1. The bot must not lose a single game
  2. The bot starts 50% of all simulated games
  3. The opponent plays by randomly choosing any open square on it's turn

When benchmarked in 100,000 games my bot wins 94.95% of the time (meaning there are 5053 tie games). Breaking it down in games where it starts the win rate is 99.49% and when it goes second it's 90.42%.

I believe that for starting the game I have reached the optimum achievable (winning 191 out of 192 games). However, I am unsure about the case when going second. The question is: What is the best any bot can achieve given the three conditions outlined above? A found a couple of papers that show that with a lot of training algorithms achieve win rates in the high eighties, so clearly this works well--just not clear if it could be improved.

mathematical-optimization tic-tac-toe
2 Answers

Tic tac toe is a really simple game which produces a limited amount of possible gamestates. Therefore there is no need to hardcode anything, you can use a minimax (or preferably negamax) algorithm to go through all possible moves until the game ends in either a win/draw/loss. This would make sure that your bot always plays the optimal move and finds the win when such appears.

Your question is hard to answer on a site for coding. Since your opponent plays random moves I assume you need to ask a mathematician for the probability of winning a game vs such player (try here).

However, if your code is truly based on the rules you specify (and your bot plays perfectly) then the results you are getting from playing even more games would converge to the answer to your question.

user_120530790

For closure, I believe I got the answer in a different forum:

With the restriction I have given in the OP, the optimal winrate for the bot going first is 191 out of 192 games or 99.479% and for the random player going first it is 866 out of 945 games or 91.640%. Overall that means the optimal winrate should be 115589/120960 or 95.5597%.

user_147224750
Related