2048 search

[MahmoudUthman]

Although not directly related to chess , but I think the techniques are the same .
I'm writing a solver for 2048 : http://gabrielecirulli.github.io/2048/ but I'm stuck on the search part , I think I can use an alpha beta variant with the maximizing side is the side paying the game with available moves set {left,right,up, down} ,and the minimizing side is the computer placing a tile at an empty square, will this work right ?

*a second choice is to generate moves at each depth for the human player with available moves = {left,right,up, down} union {every new tile position possible } , but the problem here is should I use a probability of something like history heuristic and then choosing the most promising path, or should I be pessimistic and choose the safest path and won't the branching factor be huge with no pruning possible?

if placing tiles was truly a random operation shouldn't I get similar results from both the history based and "optimistic" search ? since I won't lose instantly after making a move if I was searching a couple of plies ahead ?

*one more thing If I chose an optimistic search should I partly allow path with dead ends "losing" being possible or should I completely ignore such paths ?

[matthewlai]

Although not directly related to chess , but I think the techniques are the same .
I'm writing a solver for 2048 : http://gabrielecirulli.github.io/2048/ but I'm stuck on the search part , I think I can use an alpha beta variant with the maximizing side is the side paying the game with available moves set {left,right,up, down} ,and the minimizing side is the computer placing a tile at an empty square, will this work right ?

*a second choice is to generate moves at each depth for the human player with available moves = {left,right,up, down} union {every new tile position possible } , but the problem here is should I use a probability of something like history heuristic and then choosing the most promising path, or should I be pessimistic and choose the safest path and won't the branching factor be huge with no pruning possible?

if placing tiles was truly a random operation shouldn't I get similar results from both the history based and "optimistic" search ? since I won't lose instantly after making a move if I was searching a couple of plies ahead ?

*one more thing If I chose an optimistic search should I partly allow path with dead ends "losing" being possible or should I completely ignore such paths ?

The basic underlying assumption of alpha-beta is that it's a zero-sum game with 2 adversarial players. That's not the case here, so alpha-beta is not the right algorithm for this.

There is also a random element in the game (placing squares).

I'm not sure how I would approach this because even though the branching factor is low, the depth required to get to solution is extremely high.

Solving it using machine learning combined with something like Monte Carlo tree search would be pretty easy... probably.

[Ajedrecista]

Hello Mahmoud:

You can probably have a look to this page:

What is the optimal algorithm for the game 2048?

You can also learn strategies here:

2048

An Advanced Guide to 2048 – The slow crawl towards 16384
An Advanced Guide to 2048 – The slow crawl towards 16384 Part 2 – More Advanced Plays
An Advanced Guide to 2048 – The slow crawl towards 16384 Part 3 – Recovery plays and technical plays

Good luck!



Regards from Spain.

Ajedrecista.