nneonneo / threes-ai Goto Github PK

AI for the game Threes!

Python 56.97% Shell 11.94% C 7.66% C++ 17.91% Batchfile 0.14% Makefile 0.55% M4 4.83%

threes-ai's Introduction

AI for the game Threes! by Sirvo LLC. You can get the game from here: http://asherv.com/threes/

Building this AI was the inspiration for my later 2048 AI, and some of the ideas from the 2048 AI have been backported to this AI as well.

While I have not formally benchmarked the performance of this AI (yet), I know that it has successfully attained the 6144 tile multiple times, which is the highest tile available in the game. (Higher tiles are possible but unlikely, due to heavy random effects). The top score (at time of writing) is 775,524 points:

This AI is a lot more experimental than its newer sibling 2048 AI because of the increased complexity of Threes! and because it has not received as much development time. Furthermore, Threes! is in general a bit of a moving target as the random tile generation algorithms are occasionally tweaked, necessitating changes in the AI.

Algorithm

The algorithm for this AI is already essentially detailed in this StackOverflow answer describing my 2048 AI. In essence, it implements a highly-optimized bruteforce search over the game tree (all possible moves, tile spawn values and tile values), using expectimax optimization to combine the results and find the "best" possible move.

This Threes AI is actually more sophisticated than the 2048 AI in a number of ways: most notably, it accounts for the "deck" of upcoming tiles (the well-documented process by which the random incoming tiles are selected), and it properly handles all the possible tile spawn locations based on the moves that are made. In short: this Threes AI correctly (to the best of my knowledge) emulates every detail of the Threes game as part of the expectimax optimization process.

Building

The easiest way to get the AI running is to clone one of the prebuilt/ branches corresponding to your OS and processor. These branches have pre-built binaries in the bin/ directory.

Note that the "default" Python on Windows is 32-bit, while the "default" Python on OS X and Linux is 64-bit. 32-bit builds are tagged i386 while 64-bit builds are tagged x86_64.

If you want to build it yourself from source (e.g. if you're making changes), follow the directions below.

Unix/Linux/OS X

Execute

./configure
make

in a terminal. Any relatively recent C++ compiler should be able to build the output.

Note that you don't do make install; this program is meant to be run from this directory.

Windows

You have a few options, depending on what you have installed.

Pure Cygwin: follow the Unix/Linux/OS X instructions above. The resulting DLL can only be used with Cygwin programs, so to run the browser control version, you must use the Cygwin Python (not the python.org Python). For step-by-step instructions, courtesy Tamas Szell (@matukaa), see this document.

Cygwin with MinGW: run

  CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make

in a MinGW or Cygwin shell to build. The resultant DLL can be used with non-Cygwin programs.

Visual Studio: open a Visual Studio command prompt, cd to the threes-ai directory, and run make-msvc.bat.

Running

Python prerequisites

You'll need Python 2.7, NumPy and PIL to run the Python programs.

Running the command-line version

Run bin/threes if you want to see the AI by itself in action.

Android assistant

There are some web-based versions of Threes, but I wanted to make the AI play against the real app. So, I built an "assistant" program for Android devices, called android_assistant.py, which communicates with the phone over ADB and makes moves completely automatically. It requires only USB ADB permissions (standard developer access), and does not require rooting or any other modification of the device or app. It uses the standard Android screencap utility to obtain the (visible) game state, computes the optimal move, then uses the Linux input event subsystem to generate swipe events.

To use android_assistant.py, you will need to configure the OCR subsystem for your device. You will also have to record swipe events for replay. Currently, two devices are configured: the LG Nexus 5 and the OnePlus One (corresponding to the phones I have tested this on). Patches are welcome to add more phones.

To configure the OCR system, you should add an entry in ocr/devices.py corresponding to your device. The model name can be obtained by simply running android_assistant.py while connected to the device (it should error out with the expected model name). Essentially, you will need to take a screenshot of the game and derive the position of the "upcoming tile" pane, as well as the position and spacing of the tile grid. (This part could probably use more automation and/or simplification!)

To record events, simply run python -m android.inputemu --record up down left right and execute the appropriate gesture on your phone when prompted.

Manual assistant

The manual assistant is a general-purpose Threes! assistant that works with any implementation of Threes!. You tell it the board and upcoming tile set, and the assistant calculates the best move.

Run manual_assistant.py to start the manual assistant.

Note that the manual assistant expects to see sequential moves. If you skip ahead (making moves without the assistant), quit the assistant by pressing Ctrl+C and start it again. Otherwise, you might receive an error message like "impossible situation" if you enter a board that is not sequential to the previous board.

Entering boards

When entering the next board, you can use spaces, newlines and/or commas to separate tiles. Read from left to right, then top to bottom. Enter a zero for empty spaces. Example input:

Using commas and newlines:

  96,2,3,0
  2,1,1,0
  2,1,0,0
  0,0,2,0

Using commas alone:
```
  96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
```

Using spaces:

You can also input a "delta" from the previous board. Specify row or column in which the new tile spawned, and the value of the tile that spawned (you can omit this if there was only one possible new tile last move, e.g. if it was red or blue). Also specify the move you made if it wasn't the move suggested by the AI.

Columns and rows are numbered left-to-right and top-to-bottom: column 1 is the left column and row 1 is the top row.

For example, if the board is swiped up, and goes from

then you'd send 2,3,up as the board (in the 2nd column, a 3 spawned). If the AI had recommended the up move then you could simply omit that and send 2,3. If the upcoming tile had been forecast as 3, you could omit the 3 and send just 2.

By entering deltas, you will save yourself a lot of time. In most cases, you only need to enter one number (the column/row that changed).

Entering tiles

When entering the upcoming tile, use one of the following formats:

a color: blue (1), red (2) or white (3+)
a number group: 1, 2, 3, 3+, 6+, or e.g. 24,48,96, 24 48 96
- 3+ means it could be a 3 or higher; use this with older Threes! that don't show a "plus" sign on bonus tiles
- 6+ means it is any bonus tile; use this if the upcoming tile is "+"
- 24,48,96 means it is one of those three; use this with newer Threes! that show you explicit options for the bonus tile value.

threes-ai's People

Contributors

Stargazers

Watchers

threes-ai's Issues

ADB shell object not initializing?

I'm using a Pixel 2 XL running Android 9, with ADB version 1.0.40 on macOS. The phone is in developer mode with USB debugging enabled and is seen by ADB:

$ adb devices
List of devices attached
XXXXXXXXXX124	device

I haven't set the OCR yet, because I don't know the specific name of the device yet (though I could guess). But it doesn't matter, because every time I try android_assistant.py I get this without the phone name:

$ python android_assistant.py 
Warning: timed out waiting for prompt!
Warning: unparsed prompt u''
Traceback (most recent call last):
  File "android_assistant.py", line 144, in <module>
    exit(main(sys.argv[1:]))
  File "android_assistant.py", line 118, in main
    shell = ADBShell()
  File "/Users/x/Documents/threes-ai/android/adb_shell.py", line 394, in __init__
    self.execute('COLUMNS=10000000')
  File "/Users/x/Documents/threes-ai/android/adb_shell.py", line 442, in execute
    collected = self._send_command(cmd)
  File "/Users/x/Documents/threes-ai/android/adb_shell.py", line 424, in _send_command
    raise IOError("timed out waiting for shell echo")
IOError: timed out waiting for shell echo

I get the same error (though a slightly different trace) when trying to record events:

$ python -m android.inputemu --record up down left right
Warning: timed out waiting for prompt!
Warning: unparsed prompt u''
Traceback (most recent call last):
  File "/Users/x/.pyenv/versions/2.7.14/lib/python2.7/runpy.py", line 174, in _run_module_as_main
    "__main__", fname, loader, pkg_name)
  File "/Users/x/.pyenv/versions/2.7.14/lib/python2.7/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/Users/x/Documents/threes-ai/android/inputemu.py", line 188, in <module>
    exit(main(sys.argv[1:]))
  File "/Users/x/Documents/threes-ai/android/inputemu.py", line 175, in main
    shell = ADBShell()
  File "android/adb_shell.py", line 394, in __init__
    self.execute('COLUMNS=10000000')
  File "android/adb_shell.py", line 442, in execute
    collected = self._send_command(cmd)
  File "android/adb_shell.py", line 424, in _send_command
    raise IOError("timed out waiting for shell echo")
IOError: timed out waiting for shell echo

A separate issue, but once I get that device name I'm not sure what the w, h and dx, dy OCR values are referring to. The annotated screenshot is my best guess. (Once I get it working I can do a pull request.)

Unable to run the manual assistant

I have been getting error and haven't been able to run this. Could you please write a step by step for python novices?

$ python manual_assistant.py
Traceback (most recent call last):
File "manual_assistant.py", line 9, in
from base_assistant import run_assistant, movenames
File "/Users/hamid/Desktop/threes-ai-prebuilt-linux-x86_64/base_assistant.py", line 6, in
from threes_ai_c import find_best_move, set_heurweights
File "/Users/hamid/Desktop/threes-ai-prebuilt-linux-x86_64/threes_ai_c.py", line 10, in
threes = ctypes.CDLL(dllfn)
File "/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/ctypes/init.py", line 365, in init
self._handle = _dlopen(self._name, mode)
OSError: dlopen(bin/threes.so, 6): no suitable image found. Did find:
bin/threes.so: unknown file type, first eight bytes: 0x7F 0x45 0x4C 0x46 0x02 0x01 0x01 0x00
/Users/hamid/Desktop/threes-ai-prebuilt-linux-x86_64/bin/threes.so: unknown file type, first eight bytes: 0x7F 0x45 0x4C 0x46 0x02 0x01 0x01 0x00

Moto g4 build prop error

Hi,

I have error with Moto G4 plus CM 14.1 (Android 7.1.1). When execute, the key ro.product.model doesnt exist. However, when use in terminal adb shell getprop, it exists

Make AI work on Linux/generic UNIX/Windows

Probably involves just importing the platdefs and autoconf stuff from 2048-AI...

Xbox One version bonus tile deck

Howdy,

I've been trying this AI out on the Xbox One version of Threes! and inevitably run into the situation where the bonus tile given by the game isn't expected by the AI, causing me to reset the board.

This is mostly just inconvenient, but I do wonder if the AI might not be able to predict as well given it's obviously not expecting these particular bonus tiles.

Example from the manual assistant:

Move number 31
Previous move: right ; tile: 2
[[  0   3   3  48]
 [  0   1   3  48]
 [  0   0   6 192]
 [  2   0   6 384]]
Current score: 9261
Next tile: set([4, 5, 6]) (deck=1:2, 2:2, 3:3)
*** Suggested move: down

Current board or difference from last board?
2,48
Didn't understand your input: New tile wasn't in previous tile set
Current board or difference from last board?

This is running on OSX if that matters. I had a peek at the C++ code but my C++-fu isn't as good as my Ruby or Perl-fu, so it wasn't clear to me how the bonus deck is constructed.

Let me know if you need any further information.

can't run the manual assistent

the error I am getting is:
Couldn't find threes library bin/threes.{so,dll,dylib}! Make sure to build it first.

The other guy closes his issue without saying anything about it.

Compiling Errors - array subscript is above array bounds

Output from ./configure (Bolding is my own emphasis:

ackis@ubuntu:~/threes-ai$ ./configure
checking for g++... g++
checking whether the C++ compiler works... yes
checking for C++ compiler default output file name... a.out
checking for suffix of executables...
checking whether we are cross compiling... no
checking for suffix of object files... o
checking whether we are using the GNU C++ compiler... yes
checking whether g++ accepts -g... yes
checking whether g++ supports C++11 features by default... no
checking whether g++ supports C++11 features with -std=gnu++11... yes
checking whether we are using the GNU C++ compiler... (cached) yes
checking whether g++ accepts -g... (cached) yes
checking for gcc... gcc
checking whether we are using the GNU C compiler... yes
checking whether gcc accepts -g... yes
checking for gcc option to accept ISO C89... none needed
checking how to run the C preprocessor... gcc -E
checking for gcc... (cached) gcc
checking whether we are using the GNU C compiler... (cached) yes
checking whether gcc accepts -g... (cached) yes
checking for gcc option to accept ISO C89... (cached) none needed
checking for a thread-safe mkdir -p... /bin/mkdir -p
checking how to run the C++ preprocessor... g++ -E
checking for grep that handles long lines and -e... /bin/grep
checking for egrep... /bin/grep -E
checking for ANSI C header files... yes
checking for sys/types.h... yes
checking for sys/stat.h... yes
checking for stdlib.h... yes
checking for string.h... yes
checking for memory.h... yes
checking for strings.h... yes
checking for inttypes.h... yes
checking for stdint.h... yes
checking for unistd.h... yes
checking fcntl.h usability... yes
checking fcntl.h presence... yes
checking for fcntl.h... yes
checking for stdint.h... (cached) yes
checking for stdlib.h... (cached) yes
checking for string.h... (cached) yes
checking sys/time.h usability... yes
checking sys/time.h presence... yes
checking for sys/time.h... yes
checking for unistd.h... (cached) yes
checking unordered_map usability... yes
checking unordered_map presence... no
**configure: WARNING: unordered_map: accepted by the compiler, rejected by the pre                                                                processor!
configure: WARNING: unordered_map: proceeding with the compiler's result**
checking for unordered_map... yes
checking tr1/unordered_map usability... yes
checking tr1/unordered_map presence... yes
checking for tr1/unordered_map... yes
checking for inline... inline
checking for uint16_t... yes
checking for uint64_t... yes
checking for gettimeofday... yes
checking for strchr... yes
checking for arc4random_uniform... no
checking for drand48... yes
configure: creating ./config.status
config.status: creating Makefile
config.status: creating config.h
config.status: config.h is unchanged

Output from make:

ackis@ubuntu:~/threes-ai$ make
g++  -g -O2 -std=gnu++11 -O3 -Wall -Wextra -fPIC -c -o bin/threes.o threes.cpp
threes.cpp: In function ‘void init_tables()’:
threes.cpp:182:31: warning: array subscript is above array bounds [-Warray-bound                                        s]
             line[j] = line[j+1];
                               ^
threes.cpp:182:31: warning: array subscript is above array bounds [-Warray-bound                                        s]
g++ -g -O2 -std=gnu++11 -O3 -Wall -Wextra -fPIC  bin/threes.o  -o bin/threes
g++ -g -O2 -std=gnu++11 -O3 -Wall -Wextra -fPIC -shared  bin/threes.o  -o bin/th                                        rees.so
rm bin/threes.o

ShellCommandException when trying to use android assistant

Hiya. Thanks for this, it looks brilliant! I'm having a problem getting the Android assistant to work. I've set up the ocr.py for my device (Samsung Galaxy S6 - I'll send a PR if I get it working) and recorded the swipe events as per the readme (python -m android.inputemu --record up down left right)but I get an error when trying to send the swipe command to the device. This is the stacktrace:

Move number 1
[[  0   0   0   3]
 [192   2   6   1]
 [  1   3   2   3]
 [  1   1   3   3]]
Current score: 2211
Next tile: [1] (deck=1:1, 2:3, 3:2)
Traceback (most recent call last):
  File "android_assistant.py", line 144, in <module>
    exit(main(sys.argv[1:]))
  File "android_assistant.py", line 140, in main
    run_assistant(assistant.gen_board_mem(), assistant.make_move, args.from_start)
  File "/threes/threes-ai/base_assistant.py", line 136, in run_assistant
    make_move_func(movenames[move])
  File "android_assistant.py", line 68, in make_move
    playback_gesture(self.shell, self.ident, move)
  File "/threes/threes-ai/android/inputemu.py", line 75, in playback_gesture
    _write_events(shell, pack)
  File "/threes/threes-ai/android/inputemu.py", line 44, in _write_events
    shell.execute("echo -ne '%s' > %s" % (s, dev))
  File "/threes/threes-ai/android/adb_shell.py", line 455, in execute
    raise ShellCommandException(self._encode_command(cmd), int(d['status']), ret.decode())
android.adb_shell.ShellCommandException: Command 'echo -ne '\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x39\x00\xd8\x1f\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x4a\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x45\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x35\x00\xb1\x09\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x36\x00\xc3\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x30\x00\x06\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03\x00\x31\x00\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00' > /dev/input/event1' returned non-zero exit status 1

If I set a debugger I see that the value of d is {'status': bytearray(b'1'), 'hash': bytearray(b'$'), 'user': bytearray(b'shell'), 'cwd': bytearray(b'/')}

I'm on Python 2.7.10. I know nothing about Android dev. Any clues on how to debug this would be appreciated.

Many thanks.

Support for calculating "threelock", "sixlock" and "twelvelock"

Hi,

This is more of a feature request, although it might actually require a totally different algorithm.

In the Xbox One version of the game there are three achievements that relate to getting the board into a special position, which is a "lock" position. For example, "Threelock" requires the board to be entirely locked (no moves available) with a 3 tile in every alternating square. "Sixlock" and "Twelvelock" are the same except with the 6 and 12 tiles respectively.

Example of a Sixlock: http://i.imgur.com/ka0OQWk.png

I was wondering if you might have some ideas on how to code the AI to do this?

Thanks for reading,

Tarragon

finding the prebuilt branches

terribly sorry to bother you with i guess dumb questions like this. How do I find the prebuilt branches?

Still unable to launch manual assistant

Still having trouble.

Ran into issues with not having numpy so tried to install it without sucess.
Used 2.7.9 which has pip bulit in, to try and resolve numpy issue, without success
Tried anaconda (2.7) which includes numpy and progress but produces error about not finding threes:

"Couldn't find threes library bin/threes.{so,dll,dylib}! Make sure to build it first."

Just trying to use your manual assistant. Again, no knowledge about python. Willing to pay you for your time.

Converting to a web based solver.

This is, as far as I'm aware the most consistent and effective solver to date - however it's limited to Android. Surely the core algorithms can be converted to produce a web-based solver similar to: http://rianhunter.github.io/threes-solver/ or a command line based solver like the now broken Threes Bot Assistant? I can't see myself ever getting more than 1536 without a solver and I play on the Xbox One version.

Thanks in advance.

some problem about threes-ai

I run web_assistant.py, An error has occurred : "key wasThrown error", I make change according this commit (nneonneo/2048-ai@35d8f9c), after that, run again. Another error occurre,


Traceback (most recent call last):
  File "web_assistant.py", line 250, in <module>
    exit(main(sys.argv[1:]))
  File "web_assistant.py", line 246, in main
    run_assistant(assistant.gen_board(), assistant.make_move, args.from_start)
  File "/Users/YDZ/Downloads/threes-ai-python/base_assistant.py", line 99, in run_assistant
    for newboard, tileset, skip_move in gen_board:
  File "web_assistant.py", line 160, in gen_board
    board = map(to_ind, board)
  File "web_assistant.py", line 18, in to_ind
    return {0:0, 1:1, 2:2, 3:3, 6:4, 12:5, 24:6, 48:7, 96:8, 192:9, 384:10, 768:11, 1536:12, 3072:13, 6144:14}[val]
KeyError: u'A'

I add some debug code. I print board:

# Convert board values to ranks
	    print "********** board = ",board
  	    for i in range(board.__len__()):
	       print board[i]


pages =  [{u'description': u'', u'title': u'Threes', u'url': u'http://play.threesgame.com/', u'webSocketDebuggerUrl': u'ws://localhost:9222/devtools/page/(B517596AB2C3CFFE3557CB4C6EE5C426)', u'faviconUrl': u'http://play.threesgame.com/favicon.ico', u'type': u'page', u'id': u'(B517596AB2C3CFFE3557CB4C6EE5C426)', u'devtoolsFrontendUrl': u'/devtools/inspector.html?ws=localhost:9222/devtools/page/(B517596AB2C3CFFE3557CB4C6EE5C426)'}]
********** board =  Array(16)
A
r
r
a
y
(
1
6
)

This means board do not read the numbers on the board from web ?

Updating the game rules

Hi, I was wondering how we determine the deck generation and tile placement rules from the game itself. Does it require that we decompile the APK? Has that work been documented anywhere?

Missing parentheses in call to print

Line 73 column 25 is being highlighted after F5 is pressed to run the manual_assistant.py program in the python 3.4.3 Shell. Please advise. Thanks