7 ms·

The Mathematics of 2048: Optimal Play with Markov Decision Processes (2018)

209 points by duck 5y ago

fogof 5y ago
As the article itself notes, previous thread: https://news.ycombinator.com/item?id=16790338 https://news.ycombinator.com/item?id=16790338
- dang 5y ago
  Thanks! Macroexpanded: The Mathematics of 2048: Optimal Play with Markov Decision Processes - https://news.ycombinator.com/item?id=16790338 https://news.ycombinator.com/item?id=16790338 - April 2018 (43 comments)
graycat 5y ago
Here are some references for Markov decision theory, stochastic optimal control, stochastic dynamic programming: Dimitri P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models. George L. Nemhauser, Dynamic Programming. Stuart E. Dreyfus and Averill M. Law, The Art and Theory of Dynamic Programming. E. B. Dynkin and A. A. Yushkevich, Controlled Markov Processes. Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control. There is more from R. T. Rockafellar and R. J.-B. Wets. And of course we should mention R. Bellman. IIRC, Dreyfus was a Bellman student, and Dynkin's dissertation advisors were Gelfand and Kolmogorov.
- toxik 5y ago
  Where is Sutton and Barto?
- jdleesmiller 5y ago
  (Author of the article here.) Thanks, I can vouch for the Bertsekas book. I'd also recommend: Russell, Stuart, and Peter Norvig. "Artificial intelligence: a modern approach." (2002). Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018. (As another commenter just pointed out.) They have a great example with a recycling robot.
  - graycat 5y ago
    I might have mentioned that for your example, we can have good confidence in the Markov assumption -- we just say we need to trust the random number generator. In real world practice, i.e., where we don't get to drive the stochastic part of the problem with our own random number generator, the Markov assumption (past and future conditionally independent given the present) can be, commonly is, difficult to justify. But, then in just the theory, every stochastic process is Markov -- just let the state be the history -- I intend this as a joke, but actually, technically in the math, it is true. If we DO make the state the history and have a problem in continuous time, then, at least in theory, we are conditioning on uncountably infinitely many random variables, and just defining how to do that is a bit interesting. Then for our decisions. policy, we can encounter the problem of measurable selection, also a bit interesting and surprising. I.e., dynamic programming in continuous time gets us into measure theory, the Radon-Nikodym theorem, etc. Stochastic dynamic programming, when find a good application and can build a good solution, i.e., keep the computational demands within the super computer range, can seem really smart, of course is not prescient but first cut, intuitively, can seem to be. Your solution likely also seems prescient. More applications would be nice. Here is a potential, potentially large, collection of new applications: Develop a spreadsheet, for an example, for, say, budgeting for the next 5 years. To have a simple description, have one column for each month, for a initial column and then one more for the end of each of the 60 months, and have one row for each variable. Some of the spreadsheet cells might have random quantities (have them all independent, to keep the Markov assumption easy to justify), and some of the cells might be empty and available for decisions. Now, presto, bingo, whether we knew or intended it or not, we now have formulated a problem in discrete time stochastic dynamic programming, and since in practice problem formulation is a common obstacle, we have maybe made some progress. In principle at this point the software for a solution is well defined. And since long ago people wrote general purpose stochastic dynamic programming software, the software we would need is in a sense actually simple (if we don't care about execution time). Now just feed this problem into a suitably large computer and get the resulting decisions and the expected earnings, we wanted to maximize, at the end of the 5 years. If make the software more complicated, then can put in some ideas to make the computations faster by some factors of 10.
  - graycat 5y ago
- abecedarius 5y ago
  Thanks. I noticed Bellman's book in a local bookstore; what do you think of it as an intro?
  - graycat 5y ago
    An intro? Nemhauser and Dreyfus and Law are intended as intros and are quite well written. Bellman, who likely should be named the father of dynamic programming, is the oldest book on my list and is not intended as an intro. But if can get Bellman for less than $10, maybe for the price of a Big Mac, then eat a lighter lunch and get the book. Bellman's book likely covers the Hamilton–Jacobi–Bellman equation, not so easy to understand via the other intros. Not really a biggie but worth knowing, a big part of this subject in computation is the value function, and at least Bertsekas used neural nets as a means to have an efficient approximation. So more recent treatments may include this idea. Dynamic programing is one of the leading examples of "the curse of dimensionality". The field has not been still; e.g., multivariate splines have been an idea for handling the value function in computation. Of course can have software go through the motions of stochastic dynamic programming when the Markov assumption is not satisfied; the software won't object. But when the assumption does old, and the rest of the effort has good quality, can argue that the work provides an optimal solution, the best possible, of course, in expected value, for any means of handling the data. In short, we have what is called "the principal of optimality". The continuous time case, with all the math details filled in, is more difficult; so for an intro, stay with discrete time. There has been a lot of attention to this subject in the ORFE (Operations Research and Financial Engineering) department at Princeton. Long the chair was E. Çinlar. The best course I took in school was from a Çinlar student. Of course, if expect artificial intelligence to be really smart, then as a special case it should be able to be as good as stochastic optimal control. And apparently now some of reinforcement learning is using the core idea of stochastic dynamic programming. But without the Markov assumption, might count that application as a heuristic with no more than weak claims about optimality. I spent a lot of time in the field. Eventually I concluded that generally in the US economy a lot of knowledge of stochastic optimal control and a dime wouldn't cover a 10 cent cup of coffee. Would have a lot better chance buying a house and supporting a family getting paid to develop Web sites, e.g., to sell, say, used math books, including Bellman's. Maybe there have been and are some niche applications (maybe somewhere in US national security), but that niche is likely much sharper than any razor. There is something of an organizational problem for a math guy getting hired to apply stochastic optimal control: The person hiring you, your hiring manager, will likely know much less about the math than the math guy, likely know nothing about the math. So this manager will be very reluctant to allocate much of his (her) budget and risk his job to support work he doesn't understand and, that, indeed, might justify the C-level suits promoting the math guy over his manager. Due to such issues, the math guy with an application potentially valuable in the economy could be better off doing a corresponding startup. Else, to avoid scaring hiring managers, he might be better off omitting such math from his resume. So, for getting hired as an employee, a lot of math background on a resume can be from useless down to, say, a felony conviction. A recipe for rabbit stew starts out "First catch a rabbit.". A recipe for applied math might start, "First find an application." Can't argue that some topic in math will be useless forever outside of math and in the economy, but forever is a long time. As it is, it can appear that some math papers and books, including what looks like applied math, are written before seeing any rabbits. Yet, the best of pure/applied math is in some senses super terrific stuff, way up there with the best of Bach and Beethoven, etc., and at times there are good applications. E.g., there is some pure and applied math at the core of my startup; the pure math provides some special support, a version of optimality, for the whole effort. Just what that pure math says is terrific, gives a solid guarantee where intuitively we have only confusion, is so good it's tough to believe, but still it's true. The applied math is original with me, powerful for my startup but no biggie as research. Good luck.
deepsun 5y ago
So it's not clear from the paper -- what is the optimal strategy for 2x2, 3x3, 4x4@64?
- yobbo 5y ago
  It would be encoded in a lookup-table that is populated by an iterating algorithm. The size of this lookup-table corresponds to the state space, hence it can't be too big.
- thom 5y ago
  This is an understudied area, for me. Yes we can come up with mathematically optimal ways of solving a problem, but it's much harder to come up with the mathematically optimal way of teaching a _human_ to solve that problem. Obviously there's a lot of work in 'explainability' in machine learning models but that doesn't really get there. I often find myself going back to Eurisko as a fascinating example of the road not taken (or perhaps, the road taken to its logical end and abandoned) in machine learning. You had this system that instead of learning opaque weights in a network, learned heuristics that were fairly explainable. In some ways that's a much more useful companion than a model that's strictly superior in its decisions. I find this regularly in chess - you can prep with Stockfish and you know you're probably memorising the best line, and you can follow the sidelines to find very concretely _why_ that's the case, but it still feels like an inefficient way of learning. It always feels like a machine that yielded up fewer, more abstract principles would be helping me more. I recently thought about this for solving Rubik's cubes. I don't really want the fastest way to solve it, ideally I'd have a way that simultaneously optimises the number of heuristics (if you have such and such a colour here and here, do this, if this face is all white, do that etc) and the number of total actions. That seems like a tractable problem for a computer to brute force for you even without smarts. I face this in my work constantly: you can come up with the most amazing model based on the most cutting edge architecture, and you can trust its predictions above any others. But then you've got to explain to a football coach why _they_ should trust it, and once that trust is built, distil it into few enough rules that they can train a team to reflect its expertise. Sorry for the ramble!
  - jdleesmiller 5y ago
deleted 5y ago
[deleted]
bcunning 5y ago
I’d be much more interested in an analysis of Threes!
- scott_s 5y ago
  Three is an ever-green game. It requires more strategy and planning than 2048. I still play it, over five years since I bought it. Easily worth the $6 to purchase.
  - bcunning 5y ago
    It really is. I’ve played for years. I came so close to beating it last year, I needed a break after that.
  - filoeleven 5y ago
    If either of you (or others who like Threes) have an iOS device, check out SPL-T. It’s similarly engaging, and completely deterministic. Which means you have no one to blame but yourself for losing. Someone who’s really into math might be able to solve it and play forever. https://simogo.com/work/spl-t/ https://simogo.com/work/spl-t/
- glial 5y ago
  I've wanted to do this for Threes for years! Alas, I'm not aware of any API that makes it easy to do this programmatically.
  - duskwuff 5y ago
    There is a web version at http://play.threesgame.com/ http://play.threesgame.com/ -- I wonder if you could hook into this? It seems a little buggy, though.
- floatingatoll 5y ago
  It's not unlike a Rubiks Cube!
terabytest 5y ago
I’m the original creator of 2048. I’m always so humbled when I see that it’s still something people talk about, especially (as is the case with this article) in such an advanced way as to completely go over my head!
- AlphaWeaver 5y ago
  At this exact moment you have 2048 HN Karma.
  - nafey 5y ago
    Let me upvote
  - uuddlrlr 5y ago
    Quick we need 3 downvotes to restore balance
    - dilippkumar 5y ago
      2052 karma right now. I don't have the heart to downvote them back into 2048.
      - eutectic 5y ago
        4096, here we come!
- Jerrrry 5y ago
  No exaggeration, your game has saved many a sanity, wasted hours, and has been enjoyed by millions. You may die but your game will forever be burned into the corneas of the common. Good shit!
  - monkeybutton 5y ago
    A mainstay of commuters worldwide.
  - 5y ago
spankalee 5y ago
Figuring a truly global optimal strategy for each potential game state is a nice way to teach about MDS, but somehow less interesting to me than figuring out a strategy that's optimal within some constraint - like a small model size or being describable to humans.
jvanderbot 5y ago
I'm always happy to see dynamic programming's cooler nephew MDP show up at parties. After a few drinks, he pulls out the POMDP dance and goes home with everyone's spouse / funding.

209 points by duck 5y ago

As the article itself notes, previous thread: https://news.ycombinator.com/item?id=16790338 https://news.ycombinator.com/item?id=16790338

dang 5y ago
Thanks! Macroexpanded: The Mathematics of 2048: Optimal Play with Markov Decision Processes - https://news.ycombinator.com/item?id=16790338 https://news.ycombinator.com/item?id=16790338 - April 2018 (43 comments)

graycat 5y ago

Here are some references for Markov decision theory, stochastic optimal control, stochastic dynamic programming: Dimitri P. Bertsekas, Dynamic Programming: Deterministic and Stochastic Models. George L. Nemhauser, Dynamic Programming. Stuart E. Dreyfus and Averill M. Law, The Art and Theory of Dynamic Programming. E. B. Dynkin and A. A. Yushkevich, Controlled Markov Processes. Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control. There is more from R. T. Rockafellar and R. J.-B. Wets. And of course we should mention R. Bellman. IIRC, Dreyfus was a Bellman student, and Dynkin's dissertation advisors were Gelfand and Kolmogorov.

toxik 5y ago
Where is Sutton and Barto?
jdleesmiller 5y ago
(Author of the article here.) Thanks, I can vouch for the Bertsekas book. I'd also recommend: Russell, Stuart, and Peter Norvig. "Artificial intelligence: a modern approach." (2002). Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018. (As another commenter just pointed out.) They have a great example with a recycling robot.
- graycat 5y ago
  I might have mentioned that for your example, we can have good confidence in the Markov assumption -- we just say we need to trust the random number generator. In real world practice, i.e., where we don't get to drive the stochastic part of the problem with our own random number generator, the Markov assumption (past and future conditionally independent given the present) can be, commonly is, difficult to justify. But, then in just the theory, every stochastic process is Markov -- just let the state be the history -- I intend this as a joke, but actually, technically in the math, it is true. If we DO make the state the history and have a problem in continuous time, then, at least in theory, we are conditioning on uncountably infinitely many random variables, and just defining how to do that is a bit interesting. Then for our decisions. policy, we can encounter the problem of measurable selection, also a bit interesting and surprising. I.e., dynamic programming in continuous time gets us into measure theory, the Radon-Nikodym theorem, etc. Stochastic dynamic programming, when find a good application and can build a good solution, i.e., keep the computational demands within the super computer range, can seem really smart, of course is not prescient but first cut, intuitively, can seem to be. Your solution likely also seems prescient. More applications would be nice. Here is a potential, potentially large, collection of new applications: Develop a spreadsheet, for an example, for, say, budgeting for the next 5 years. To have a simple description, have one column for each month, for a initial column and then one more for the end of each of the 60 months, and have one row for each variable. Some of the spreadsheet cells might have random quantities (have them all independent, to keep the Markov assumption easy to justify), and some of the cells might be empty and available for decisions. Now, presto, bingo, whether we knew or intended it or not, we now have formulated a problem in discrete time stochastic dynamic programming, and since in practice problem formulation is a common obstacle, we have maybe made some progress. In principle at this point the software for a solution is well defined. And since long ago people wrote general purpose stochastic dynamic programming software, the software we would need is in a sense actually simple (if we don't care about execution time). Now just feed this problem into a suitably large computer and get the resulting decisions and the expected earnings, we wanted to maximize, at the end of the 5 years. If make the software more complicated, then can put in some ideas to make the computations faster by some factors of 10.
- graycat 5y ago
abecedarius 5y ago
Thanks. I noticed Bellman's book in a local bookstore; what do you think of it as an intro?
- graycat 5y ago
  An intro? Nemhauser and Dreyfus and Law are intended as intros and are quite well written. Bellman, who likely should be named the father of dynamic programming, is the oldest book on my list and is not intended as an intro. But if can get Bellman for less than $10, maybe for the price of a Big Mac, then eat a lighter lunch and get the book. Bellman's book likely covers the Hamilton–Jacobi–Bellman equation, not so easy to understand via the other intros. Not really a biggie but worth knowing, a big part of this subject in computation is the value function, and at least Bertsekas used neural nets as a means to have an efficient approximation. So more recent treatments may include this idea. Dynamic programing is one of the leading examples of "the curse of dimensionality". The field has not been still; e.g., multivariate splines have been an idea for handling the value function in computation. Of course can have software go through the motions of stochastic dynamic programming when the Markov assumption is not satisfied; the software won't object. But when the assumption does old, and the rest of the effort has good quality, can argue that the work provides an optimal solution, the best possible, of course, in expected value, for any means of handling the data. In short, we have what is called "the principal of optimality". The continuous time case, with all the math details filled in, is more difficult; so for an intro, stay with discrete time. There has been a lot of attention to this subject in the ORFE (Operations Research and Financial Engineering) department at Princeton. Long the chair was E. Çinlar. The best course I took in school was from a Çinlar student. Of course, if expect artificial intelligence to be really smart, then as a special case it should be able to be as good as stochastic optimal control. And apparently now some of reinforcement learning is using the core idea of stochastic dynamic programming. But without the Markov assumption, might count that application as a heuristic with no more than weak claims about optimality. I spent a lot of time in the field. Eventually I concluded that generally in the US economy a lot of knowledge of stochastic optimal control and a dime wouldn't cover a 10 cent cup of coffee. Would have a lot better chance buying a house and supporting a family getting paid to develop Web sites, e.g., to sell, say, used math books, including Bellman's. Maybe there have been and are some niche applications (maybe somewhere in US national security), but that niche is likely much sharper than any razor. There is something of an organizational problem for a math guy getting hired to apply stochastic optimal control: The person hiring you, your hiring manager, will likely know much less about the math than the math guy, likely know nothing about the math. So this manager will be very reluctant to allocate much of his (her) budget and risk his job to support work he doesn't understand and, that, indeed, might justify the C-level suits promoting the math guy over his manager. Due to such issues, the math guy with an application potentially valuable in the economy could be better off doing a corresponding startup. Else, to avoid scaring hiring managers, he might be better off omitting such math from his resume. So, for getting hired as an employee, a lot of math background on a resume can be from useless down to, say, a felony conviction. A recipe for rabbit stew starts out "First catch a rabbit.". A recipe for applied math might start, "First find an application." Can't argue that some topic in math will be useless forever outside of math and in the economy, but forever is a long time. As it is, it can appear that some math papers and books, including what looks like applied math, are written before seeing any rabbits. Yet, the best of pure/applied math is in some senses super terrific stuff, way up there with the best of Bach and Beethoven, etc., and at times there are good applications. E.g., there is some pure and applied math at the core of my startup; the pure math provides some special support, a version of optimality, for the whole effort. Just what that pure math says is terrific, gives a solid guarantee where intuitively we have only confusion, is so good it's tough to believe, but still it's true. The applied math is original with me, powerful for my startup but no biggie as research. Good luck.

deepsun 5y ago

So it's not clear from the paper -- what is the optimal strategy for 2x2, 3x3, 4x4@64?

yobbo 5y ago
It would be encoded in a lookup-table that is populated by an iterating algorithm. The size of this lookup-table corresponds to the state space, hence it can't be too big.
thom 5y ago
This is an understudied area, for me. Yes we can come up with mathematically optimal ways of solving a problem, but it's much harder to come up with the mathematically optimal way of teaching a _human_ to solve that problem. Obviously there's a lot of work in 'explainability' in machine learning models but that doesn't really get there. I often find myself going back to Eurisko as a fascinating example of the road not taken (or perhaps, the road taken to its logical end and abandoned) in machine learning. You had this system that instead of learning opaque weights in a network, learned heuristics that were fairly explainable. In some ways that's a much more useful companion than a model that's strictly superior in its decisions. I find this regularly in chess - you can prep with Stockfish and you know you're probably memorising the best line, and you can follow the sidelines to find very concretely _why_ that's the case, but it still feels like an inefficient way of learning. It always feels like a machine that yielded up fewer, more abstract principles would be helping me more. I recently thought about this for solving Rubik's cubes. I don't really want the fastest way to solve it, ideally I'd have a way that simultaneously optimises the number of heuristics (if you have such and such a colour here and here, do this, if this face is all white, do that etc) and the number of total actions. That seems like a tractable problem for a computer to brute force for you even without smarts. I face this in my work constantly: you can come up with the most amazing model based on the most cutting edge architecture, and you can trust its predictions above any others. But then you've got to explain to a football coach why _they_ should trust it, and once that trust is built, distil it into few enough rules that they can train a team to reflect its expertise. Sorry for the ramble!
- jdleesmiller 5y ago

deleted 5y ago

[deleted]

bcunning 5y ago

I’d be much more interested in an analysis of Threes!

scott_s 5y ago
Three is an ever-green game. It requires more strategy and planning than 2048. I still play it, over five years since I bought it. Easily worth the $6 to purchase.
- bcunning 5y ago
  It really is. I’ve played for years. I came so close to beating it last year, I needed a break after that.
- filoeleven 5y ago
  If either of you (or others who like Threes) have an iOS device, check out SPL-T. It’s similarly engaging, and completely deterministic. Which means you have no one to blame but yourself for losing. Someone who’s really into math might be able to solve it and play forever. https://simogo.com/work/spl-t/ https://simogo.com/work/spl-t/
glial 5y ago
I've wanted to do this for Threes for years! Alas, I'm not aware of any API that makes it easy to do this programmatically.
- duskwuff 5y ago
  There is a web version at http://play.threesgame.com/ http://play.threesgame.com/ -- I wonder if you could hook into this? It seems a little buggy, though.
floatingatoll 5y ago
It's not unlike a Rubiks Cube!

terabytest 5y ago

I’m the original creator of 2048. I’m always so humbled when I see that it’s still something people talk about, especially (as is the case with this article) in such an advanced way as to completely go over my head!

AlphaWeaver 5y ago
At this exact moment you have 2048 HN Karma.
- nafey 5y ago
  Let me upvote
- uuddlrlr 5y ago
  Quick we need 3 downvotes to restore balance
  - dilippkumar 5y ago
    2052 karma right now. I don't have the heart to downvote them back into 2048.
    - eutectic 5y ago
      4096, here we come!
Jerrrry 5y ago
No exaggeration, your game has saved many a sanity, wasted hours, and has been enjoyed by millions. You may die but your game will forever be burned into the corneas of the common. Good shit!
- monkeybutton 5y ago
  A mainstay of commuters worldwide.
- 5y ago

spankalee 5y ago

Figuring a truly global optimal strategy for each potential game state is a nice way to teach about MDS, but somehow less interesting to me than figuring out a strategy that's optimal within some constraint - like a small model size or being describable to humans.

jvanderbot 5y ago

I'm always happy to see dynamic programming's cooler nephew MDP show up at parties. After a few drinks, he pulls out the POMDP dance and goes home with everyone's spouse / funding.