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.
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
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.
Re:Solving Probabilistic Tic-Tac-Toe
by lrschaeffer on Friday June 14, 2024 @10:57AM
(#40681511)
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.
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.
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!