Use only one lookup table?

[osuushi]

Seems to me that cache misses are a potential bottleneck with these lookup tables. You should be able to do a single lookup table, and then do a fairly simple transform on the input before the lookup (and the reverse transform on the result). Much of that single table should then fit in L1, which would plausibly more than make up for the extra time taken to transform the input and output.

[nneonneo]

This is an interesting idea. If you are able, could you submit a PR and some timing numbers? I would be very curious to see what could be gained.

I believe the only transforms needed would be transposing the board (rows <-> columns) and flipping the board (left <-> right, up <-> down).

[sicking]

I've reimplemented the AI here in rust. It's available here:

https://github.com/sicking/2048-deepsearch

I ended up using two tables. One to "sliding" left and one for "sliding" right. Sliding up and down has implemented by transposing the board, sliding left/right, and then transposing again.

This results in 1/5th as much memory used, while only requiring one extra transpose operation when sliding up/down. I.e. only one half extra transpose operation per tested move on average.

The other thing that should definitely be done is remove the table used for game-scoring, i.e. score_table. Game-scoring is only done once per move and so is not a performance-sensitive operation. Using a table for game-scoring requires more code and increases risk of cache misses, while not improving performance.