Skip to content

Instantly share code, notes, and snippets.

@melix
Last active July 7, 2021 07:37
Show Gist options
  • Save melix/9619800 to your computer and use it in GitHub Desktop.
Save melix/9619800 to your computer and use it in GitHub Desktop.
An automated solver for 2048

Automated solver for 2048

This is a script which runs a "bot" that tries to solve the incredibly addictive 2048 game. It makes use of Groovy and browser automation with Geb.

How to

  • First step, if you don’t have it, you need to install Groovy.

  • Second step is to install the Google Chrome WebDriver (just unzip the appropriate file to a local directory)

  • Next, edit the script to set the path to the Chrome Driver

  • then execute the script: groovy solver2048.groovy

After a few seconds, you should see a browser opening, and the bot trying to solve the puzzle. If it fails, it will automatically retry after 5 seconds. The script outputs some statistics, if you fancy updating the strategy !

Have fun!

@Grapes([
@Grab("org.gebish:geb-core:0.9.2"),
@Grab("org.seleniumhq.selenium:selenium-chrome-driver:2.33.0"),
@Grab("org.seleniumhq.selenium:selenium-support:2.31.0")
])
import geb.Browser
import groovy.transform.EqualsAndHashCode
import groovy.transform.InheritConstructors
import org.openqa.selenium.chrome.ChromeDriver
import groovy.transform.CompileStatic
import groovy.transform.Field
import groovy.transform.Immutable
import groovy.transform.ToString
import java.util.concurrent.Executors
System.setProperty("webdriver.chrome.driver", "/home/cchampeau/TOOLS/chromedriver");
@Field Browser browser
@Field int trials = 0
@Field int success = 0
@Field List<Integer> scores = []
// to reduce computation time
@Field final int gridSize = 4
@Field final int squareGridSize = gridSize*gridSize
void restart() {
if (trials) {
scores << (browser.js.'window.score' as Integer)
println "Success / Trials: $success / $trials"
println "Success rate: ${100*((double)success/(double)trials)}%"
println "Average score: ${(((int)scores.sum())/trials)} ($scores)"
}
browser.js.exec 'document.getElementsByClassName(\'retry-button\')[0].click();'
trials++
}
@CompileStatic
@ToString
class Tuple<T,U> {
T left
U right
Tuple(final T left, final U right) {
this.left = left
this.right = right
}
}
@CompileStatic
@InheritConstructors
class ScoreAndLine extends Tuple<Double, int[]> {}
@CompileStatic
class ScoreAndGrid extends Tuple<Double, int[][]> {
final int freeCells
final boolean win
ScoreAndGrid(double score, int[][] grid) {
super(score, grid)
boolean hasGoal = false
int sum = 0;
for (int i=0; i<grid.length; i++) {
int[] row = grid[i];
for (int j=0;j<row.length;j++) {
if (row[j]==0) {
sum++
} else if (row[j]==2048) {
hasGoal = true
}
}
}
freeCells = sum
win = hasGoal
}
}
@CompileStatic
@InheritConstructors
class IndexAndRow extends Tuple<Integer, Integer> {}
@CompileStatic
@InheritConstructors
class ScoreAndGridCouple extends Tuple<ScoreAndGrid, ScoreAndGrid> {}
@CompileStatic
@InheritConstructors
class ScoreAndDirection extends Tuple<Double, Integer> implements Comparable<ScoreAndDirection> {
@Override
int compareTo(final ScoreAndDirection o) {
o.left <=> ((double)left)
}
}
// given a row, computes the score of a single line merge
@CompileStatic
ScoreAndLine move(int[] source) {
int len = source.length
int[] res = new int[len]
int idx = 0
for (int i=0;i< len;i++) {
if (source[i]!=0) {
res[idx++] = source[i];
}
}
int start = 0
int next = 0
double score = 0d
while (start < len) {
def ps = next>gridSize-1?0:res[next]
def pv = next>gridSize-2?0:res[next + 1]
if (ps == pv) {
res[start] = 2 * ps
score += 4*ps*ps
next++
} else {
res[start] = ps
}
next++
start++
}
boolean noChange = Arrays.equals(source, res)
new ScoreAndLine(noChange?-1d:score, (int[])res)
}
// adjusts the score for a full grid. A move where nothing changed is considered a bad move
// while a move which triggered lots of merges gains bonus
@CompileStatic
ScoreAndGrid computeGridScore(ScoreAndLine[] scoreAndLines, ScoreAndGrid grid) {
int[][] src = grid.right
int noChange = 0
// a grid without changes counts as bad move (-1)
double score = 0.0d
int len = src.length
int[][] lines = new int[len][]
for (int i = 0; i < len; i++) {
ScoreAndLine line = scoreAndLines[i]
double lineScore = line.left
if (lineScore==-1d) {
noChange++
} else {
score += lineScore.doubleValue()
}
lines[i] = line.right;
}
def result
if (noChange==len) {
result = new ScoreAndGrid(-1d, lines)
} else {
result = new ScoreAndGrid(score, lines)
// if a move frees up a lot of space, it is in general better
// because free space gives us ability to make the fusions easier
score = Math.pow(score, Math.sqrt(1+result.freeCells))
result.left = score
}
result
}
@CompileStatic
int[] reverse(int[] arr) {
int len = arr.length
int[] result = new int[len]
for (int i=0; i< len;i++) {
result[len-i-1] = arr[i]
}
result
}
@CompileStatic
int[][] transpose(int[][] grid) {
int len = gridSize
int[][] res = new int[len][]
for (int i=0; i<len;i++) {
res[i] = new int[len]
for (int j=0; j<len;j++) {
res[i][j] = grid[j][i];
}
}
res
}
// computes the score of a move on a full grid
@CompileStatic
ScoreAndGridCouple leftRightScore(int[][] src) {
ScoreAndLine[] left = new ScoreAndLine[src.length]
for (int i = 0; i < src.length; i++) {
left[i] = move(src[i]);
}
ScoreAndLine[] right = new ScoreAndLine[src.length]
for (int i = 0; i < src.length; i++) {
def item = move(reverse(src[i]))
item.right = reverse((int[])item.right) // cast shouldn't be necessary...
right[i] = item;
}
// adjust
def grid = new ScoreAndGrid(0, src)
ScoreAndGridCouple result = new ScoreAndGridCouple(computeGridScore(left, grid), computeGridScore(right, grid))
result
}
// when the real game occurs, a new random tile is added
// this tries to emulate this behavior in order to improve
// accuracy of predictions. We can't explore the full tree
// so we only choose *one* random cell.
@CompileStatic
IndexAndRow chooseRandomCell(int[][] grid) {
int len = gridSize
List<IndexAndRow> emptyCells = []
for (int i=0; i<len;i++) {
for (int j=0; j<len;j++) {
if (grid[i][j]==0) {
emptyCells.add new IndexAndRow(i, j)
}
}
}
if (!emptyCells.empty) {
Collections.shuffle(emptyCells)
return emptyCells[0]
}
return null
}
// This is used to tweak the score in case further moves will later
// allow us to merge with a higher score.
// Of course, since we don't know which tiles will appear after each move
// the deeper we go, the lower the score is because the prediction becomes
// unreliable
@CompileStatic
double childScore(ScoreAndGrid child, int depth, int maxDepth) {
double subScore = child.left.doubleValue()
int[][] grid = child.right
if (child.win) {
// seriously boost
// but pay care because it's an estimate!
return Math.pow(subScore,1+depth)
}
// the idea for the sqrt here is that if there are less free cells, there's a higher probability that the
// prediction is correct
double estimate = estimateScore(grid, depth - 1, maxDepth)
if (estimate<0d) {
// ass-saving: avoid taking bad decisions if we detect a dead end
return subScore/Math.pow(2d,1+depth)
}
double score = (subScore + estimate)/ Math.sqrt(1 + child.freeCells)
score
}
@CompileStatic
double estimateScore(int[][] grid, int depth, int maxDepth) {
double score = 0d
if (depth > 0) {
IndexAndRow indexAndRow = chooseRandomCell(grid)
int index = indexAndRow.left
int row = indexAndRow.right
grid[index][row] = 2;
double score2 = 0.9d*recurseEstimate(grid, depth, maxDepth)
grid[index][row] = 4;
double score4 = 0.1d*recurseEstimate(grid, depth, maxDepth)
score = (score2 + score4)*0.5d
}
score
}
@CompileStatic
private double recurseEstimate(int[][] grid, int depth, int maxDepth) {
ScoreAndGridCouple leftright = leftRightScore(grid)
ScoreAndGridCouple updown = leftRightScore(transpose(grid))
ScoreAndGrid left = leftright.left
ScoreAndGrid right = leftright.right
ScoreAndGrid up = updown.left
ScoreAndGrid down = updown.right
double leftScore = left.left.doubleValue()
double rightScore = right.left.doubleValue()
double upScore = up.left.doubleValue()
double downScore = down.left.doubleValue()
double score = 0d
if (leftScore==-1d && rightScore==-1d && upScore==-1d && downScore==-1d) {
return -1d;
}
if (leftScore >=0d) {
score += childScore(left, depth, maxDepth)
}
if (rightScore >=0d) {
score += childScore(right, depth, maxDepth)
}
if (upScore >= 0d) {
score += childScore(up, depth, maxDepth)
}
if (downScore >=0d) {
score += childScore(down, depth, maxDepth)
}
score
}
@CompileStatic
def nextMove(List<List<Integer>> orig) {
int[][] grid = orig as int[][]
def root = new ScoreAndGrid(0, grid)
if (root.win) {
return true
}
// adaptative depth exploration. It is more important to take care when there's no a lot of free space
int depth = 1 + 2*((int)Math.sqrt(0.5d*(squareGridSize-root.freeCells)))
//println "Depth $depth"
ScoreAndGridCouple leftright = leftRightScore(grid)
ScoreAndGridCouple updown = leftRightScore(transpose(grid))
ScoreAndGrid leftScoreAndGrid = leftright.left
ScoreAndGrid rightScoreAndGrid = leftright.right
ScoreAndGrid upScoreAndGrid = updown.left
ScoreAndGrid downScoreAndGrid = updown.right
if (leftScoreAndGrid.left==-1d && rightScoreAndGrid.left==-1d && upScoreAndGrid.left==-1d && downScoreAndGrid.left == -1d) {
sleep(5000)
// game over !
restart()
} else {
double left = leftScoreAndGrid.left>=0d?leftScoreAndGrid.left + estimateScore(leftScoreAndGrid.right, depth, depth):-1d
double right = rightScoreAndGrid.left>=0d?rightScoreAndGrid.left + estimateScore(rightScoreAndGrid.right, depth, depth):-1d
double up = upScoreAndGrid.left>=0d?upScoreAndGrid.left + estimateScore(upScoreAndGrid.right, depth, depth):-1d
double down = downScoreAndGrid.left>=0d?downScoreAndGrid.left + estimateScore(downScoreAndGrid.right, depth, depth):-1d
//println "Score for (left, right, up, down) : ($left,$right,$up,$down)"
def solutions = [
new ScoreAndDirection(left, 37),
new ScoreAndDirection(up, 38),
new ScoreAndDirection(right, 39),
new ScoreAndDirection(down, 40)]
Collections.shuffle(solutions)
Collections.sort(solutions)
int keycode = (int) solutions[0].right
browser.js.exec keycode, '''
var keyEvent = document.createEvent("Events");
var keyCode = arguments[0];
keyEvent.initEvent("keydown", true, true);
keyEvent.keyCode = keyCode;
keyEvent.which = keyCode;
document.dispatchEvent(keyEvent);'''
}
return false
}
browser = new Browser(driver: new ChromeDriver())
browser.with {
go "http://gabrielecirulli.github.io/2048/"
js.exec '''(function() {
GameManager.prototype.export = function() {
window.grid = Array(this.grid.size);
window.score = this.score;
for (var i = 0; i < this.grid.size; i++) {
window.grid[i] = new Array(this.grid.size);
}
this.grid.eachCell(function(x,y,z) {
window.grid[y][x] = z==null||z==undefined?0:z.value;
});
};
GameManager.prototype.oldSetup = GameManager.prototype.setup;
GameManager.prototype.setup = function() {
this.oldSetup();
this.export();
};
GameManager.prototype.origActuate = GameManager.prototype.actuate;
GameManager.prototype.actuate = function() {
this.export();
this.origActuate();
}
})();
'''
restart()
while (true) {
sleep(80)
if (nextMove(js.'window.grid')) {
gameWin()
}
}
}
private void gameWin() {
success++
sleep(5000)
restart()
}
@mjpnumber1
Copy link

hi, When i'm run this script, this error is shown in the google chrome : You are using an unsupported command-line flag: --ignore-certificate-errors.

please edit script.
thanks...

@JacobAae
Copy link

I think the website has been updated, throwing a javascript exception on the key-input, but if you overwrite the javascript function that causes problems, the script works again. You can do so, by inserting in line 377

KeyboardInputManager.prototype.targetIsInput = function (event) { return false; };

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment