3 ms·

Author here! It was such a power trip and blissful experience to discover the game on HN, think about a strategy, implement a solution, write a blog post (than

Author here! It was such a power trip and blissful experience to discover the game on HN, think about a strategy, implement a solution, write a blog post (thanks again to orlp for his comment here that pointed out a mistake), email igpay (the author of the game), fork the repo, implement the algorithm in C# for Unity (it was my first time using those technologies but ChatGPT was quite helpful), get it merged and finally make it to the front page of HN where all of this started. Thank you guys, this is why the Internet exists!

jb1991 2y ago
The dynamic programming approach to solving tic-tac-toe is an implementation of reinforcement learning, is it not? I was surprised to see your post not mention reinforcement learning anywhere, despite that this solution appears in textbooks on reinforcement learning that use dynamic programming to solve tic-tac-toe.
- sdwr 2y ago
  I don't think so. Reinforcement learning is about teaching by pairing correct actions with rewards, like giving a dog a treat for doing a trick. Dynamic programming is a recursive algorithm that caches partial results (from the bottom up). Apples and oranges
  - lrschaeffer 2y ago
    I'm no expert, but there are approaches to reinforcement learning where you build a table of the expected payoff for each scenario, and these can recursively reference other entries in the table. Take a look at Q-learning, for example.
  - jb1991 2y ago
    Dynamic programming is one of the most widely-used algorithms in reinforcement learning and in fact the tic-tac-toe example using dynamic programming is a classic demo in reinforcement learning classes or textbooks.
- deleted 2y ago
  [deleted]
yshui 2y ago
Congrats! :) BTW, instead of max(min()) when I wrote mine I used this equality: V'(s) = 1 - V(swap_players(s)), where swap_players(s) switches X and O pieces. And I only need to do max(). Don't know if that would make your program simpler.

jb1991 2y ago

The dynamic programming approach to solving tic-tac-toe is an implementation of reinforcement learning, is it not? I was surprised to see your post not mention reinforcement learning anywhere, despite that this solution appears in textbooks on reinforcement learning that use dynamic programming to solve tic-tac-toe.

sdwr 2y ago
I don't think so. Reinforcement learning is about teaching by pairing correct actions with rewards, like giving a dog a treat for doing a trick. Dynamic programming is a recursive algorithm that caches partial results (from the bottom up). Apples and oranges
- lrschaeffer 2y ago
  I'm no expert, but there are approaches to reinforcement learning where you build a table of the expected payoff for each scenario, and these can recursively reference other entries in the table. Take a look at Q-learning, for example.
- jb1991 2y ago
  Dynamic programming is one of the most widely-used algorithms in reinforcement learning and in fact the tic-tac-toe example using dynamic programming is a classic demo in reinforcement learning classes or textbooks.
deleted 2y ago
[deleted]

yshui 2y ago

Congrats! :) BTW, instead of max(min()) when I wrote mine I used this equality: V'(s) = 1 - V(swap_players(s)), where swap_players(s) switches X and O pieces. And I only need to do max(). Don't know if that would make your program simpler.