5 ms·
The Mathematics of 2048: Counting States by Exhaustive Enumeration
- bhouston 9y agoNeat. Seems a lot harder than the work I did to enumerate towers of Hanoi back in 2004: https://www.cs.carleton.ca/sites/default/files/tr/TR-04-10.pdf https://www.cs.carleton.ca/sites/default/files/tr/TR-04-10.p...
- MaxBarraclough 9y agoThat URL spooks Firefox - invalid HTTPS cert. Warning-free URL: https://service.scs.carleton.ca/sites/default/files/tr/TR-04-10.pdf https://service.scs.carleton.ca/sites/default/files/tr/TR-04...
- scottmsul 9y agoWould be interesting to see alpha zero trained on 2048, conv nets seem well suited for this kind of game.
- nocoder 9y agoThis is likely to be a piece of cake for alpha zero given the number of states are lot less than Go.
- Hextinium 9y agoI would like to see how high it could get to, how much higher than 2048 could it go?
- nocoder 9y agoI assume you are talking about the highest tile value, I think in 4x4 game the highest possible tile value should be 2^16 or 2^(16+1) I got this from here - https://puzzling.stackexchange.com/questions/48/what-is-the-largest-tile-possible-in-2048 https://puzzling.stackexchange.com/questions/48/what-is-the-...
- TimTheTinker 9y agoHere’s a very simple but clever 2048 game playing AI: https://ronzil.github.io/2048-AI/ https://ronzil.github.io/2048-AI/
- deleted 9y ago[deleted]
- tomahunt 9y agoOh,I misread this title and thought it was going to be about maths in the year 2048.
- Al-Khwarizmi 9y agoMe too. I kind of expected a dystopian article where people in 2048 are so badly educated that the most advanced math they can do is count U.S. states one by one! Kind of disappointed it's not that, to be honest :)
- tomahunt 9y agoI was expecting a maths where quantum computation had taken over analytic number theory and theorems could be proved using brute force enumeration.Or something
- Filligree 9y agoQuantum computers can't do that. Not even in principle. :p
- whatshisface 9y agoIf you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once (The subtitle of Aaronson's blog.) https://www.scottaaronson.com/blog/ https://www.scottaaronson.com/blog/
- shaunxcode 9y agoYeah sorry working on that one now. Stay tuned though!
- tomahunt 9y agoI don't think it needs to be changed. It's actually really interesting to wonder what Mathematics is going to be like in 2048.
- maweki 9y agoThis is neat. I wonder whether there is a faster approach using binary decision diagrams or a variant thereof. If the state transition were represented by a binary function, BDDs could allow for counting states without actually enumerating. The question would be, how to actually find all the fixed points of that function.
- ballenf 9y agoI'd also think that working backwards from all possible winning states would offer some insight and potential for speed. At the expense of being somewhat more difficult (at first glance anyway) to ascertain validity of the predecessor state.
- jdleesmiller 9y ago(Author here.) That would indeed be interesting, thanks --- I don't think it's trivial to generate all of the possible predecessor states, but it seems like it should be possible. One to think about.
- Setepenre 9y agoWhats the network/gra[h library you used to draw those nice diagrams ?
- jdleesmiller 9y agoMost of them are done with the `dot` tool from https://www.graphviz.org/ https://www.graphviz.org/ . A ruby script generates the dot file, e.g. https://github.com/jdleesmiller/jdleesmiller.github.io/blob/master/assets/2048/enumeration_2x2_grouped.dot https://github.com/jdleesmiller/jdleesmiller.github.io/blob/..., and then dot generates the SVG.