The Mathematics of 2048: Counting States by Exhaustive Enumeration • Hacker News Board

Re: The Mathematics of 2048: Counting States by Exhaustive Enumeration

#21

Post by jameshart » Mon, Dec 11, 2017, 1:45 PM UTC

raverbashing wrote: post #11

tomahunt wrote: post #6

Oh,I misread this title and thought it was going to be about maths in the year 2048.

And that they were counting (US) states by exaustive enumeration. Well, yeah, how are you going to count them?

Knowing that a bijection exists between states and stars on the US flag, first obtain a US flag. Observe that the stars in the top left corner fall in a rectangular n x m grid with stars located at every node, and also in the rows and columns in between, forming a smaller (n-1) x (m-1) rectangle, so the number of stars is nm + (n-1)(m-1). Then you can just count n and m - 6 and 5 respectively - and substitute to obtain 30+20=50 stars.

Re: The Mathematics of 2048: Counting States by Exhaustive Enumeration

#22

Post by ballenf » Mon, Dec 11, 2017, 2:49 PM UTC

maweki wrote: post #12

This 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.

I'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.

Re: The Mathematics of 2048: Counting States by Exhaustive Enumeration

#23

Post by [deleted] » Mon, Dec 11, 2017, 5:02 PM UTC

TimTheTinker wrote: post #8

scottmsul wrote: post #3

Would be interesting to see alpha zero trained on 2048, conv nets seem well suited for this kind of game.

Here’s a very simple but clever 2048 game playing AI: https://ronzil.github.io/2048-AI/

[deleted]

Re: The Mathematics of 2048: Counting States by Exhaustive Enumeration

#24

Post by jdleesmiller » Mon, Dec 11, 2017, 6:48 PM UTC

ballenf wrote: post #22

maweki wrote: post #12

This 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.

I'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.

(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.