Share optimization ideas with you

[kcwu]

Sorry this is not a real issue. There is no forum for this project, I don't know better way to talk to you ;)

FYI, I wrote 2048 ai last year, too. https://github.com/kcwu/2048-c I used many similar ideas and borrowed some from you, so I'd like to share back to you.

Before @xificurk's improvement, if patched my program with your original eval function, my program can get better score than your original program. So I think you may be interested in how do I handle search details and optimizations (ignore my eval. xificurk's is better). I have noted the difference in the README file. The major ones you could reuse are:

• helper minimax search (only consider tile-2) to avoid dead. It can search 20+ steps ahead.
• Faster bit operations.
• Cache: use more than one hash table. Fixed size hash table to avoid allocation. Also take 'depth' into consideration.
• Use 64 bits for score calculation. (32 bits are not enough and may loss some precision)

[nneonneo]

This sounds great! It seems like we can get a lot from merging some of these ideas.

• Minimax sounds like a good idea. I don't know why you'd consider only tile 2 though - seems like the odds of dying to bad 4 placement are also problematic (and usually the cause of game-over situations).
• Faster bit operations sound like a good idea. What are some examples here?

• 34 takes depth into account when caching positions. What do you mean by using more than one hash table? What would other hash tables store?

• Due to the probability limit (CPROB_THRESH_LIMIT), I don't know if we gain much from using double. I wonder what the speed penalty is there.

Is it possible for you to submit a pull request for any of these items?

[VrIgHtEr]

If compiled for 64-bit it shouldn't make a difference in a modern processor, although the cache would obviously grow larger, so there would be more memory overhead.

But thinking about it, converting to double would make sense. An ieee754 float has a 23 bit mantissa. And heuristic scores are usually over a million. 2^20 = 1048576, therefore you need more than 20 bits just to represent the integral part of the heuristic, which doesn't leave much for the fractional part at all.

[kcwu]

• Only tile-2 in additional search: this is because the possibility of tile-2 is far larger than tile-4. For example, 0.9²⁰=0.1215 > 0.1. That means even the possibility of consecutive 20 tile-2 is still higher than one tile-4. Only consider tile-2 makes the helper search faster.
• bit operations: you can try https://github.com/kcwu/2048-c/blob/master/micro_optimize.cc transpose5() used only 12 operations. And count_blank3() is faster than your count_blank1().
• Yes, depth should be taken into account as #34.
• Regarding to multiple hash tables, they are
  • cache1[]: a normal one in normal search . used where like yours.
  • local_cache1[]: like cache1, but only cached the search path. It cannot cover more than cache1, but it is very lightweight and high hit-rate.
  • cache2[]: a hash table for my extra minimax search.
  • cache3[]: I have another search extension in eval_reliable(), which is slow and need cache to optimization.
• Board score almost used up all mantissa bits. There is not much rooms for calculating the average score of random drops accurately. (You need several bits to *0.9, to += tens scores, to / num_open.) If taken all these into consideration, even 32 bits may not enough. Needless to say 23 bits.

[VrIgHtEr]

Yes 20 2-tiles have a better chance of being spawned than 1 4-tile.

However consider this: very late in the game when quite often there is only 1 empty tile on the board, on the first level of searching the probabilities will be as follows

(0.9 * maximize(2-tile) + 0.1 * maximize(4-tile)) / (1 empty tile)

which would mean that in the 1st ply of searching you eliminated an entire tree branch that could have a significant effect on the score... and all this in the endgame, where it's needed the most.

[kcwu]

My extra 2-tiles search just provided as short-cut: if dead in few moves, don't try this move. Otherwise,still keep original search.

You can see my root_search_move() for the detail. Yes, this short-cut is only for root move and is not related to score calculation. https://github.com/kcwu/2048-c/blob/master/bot.cc#L537

[VrIgHtEr]

But doesn't expectimax already do that? If a tree branch results in a dead position, there aren't any others beneath it, and it negatively affects the score.

You said that if you patched your program with @nneonneo's original eval function yours scored better. I'm curious, have you tried your program with the @xificurk's heuristic? If so what were the results?

[xificurk]

FYI, when tuning up the heuristic, I also tried versions that used double, but it did not bring any improvement and run a bit slower.

[jtrinklein]

just a thought, gitter is a great way to communicate within a repository.

:pencil2: also it is free

[judge2020]

If this isn't already implimented, how about an option to calculate deeper or more moves into the future? it should default to the current setting but someone on a powerful computer can raise it to raise their chances of a larger end title/score

[VrIgHtEr]

The program is single threaded. And since single threaded performance isn't really improving much (newer developments focus on more cores and better power efficiency) it wouldn't do much good. Furthermore, the program looks fewer moves ahead when there are few distinct tiles on the board. This was done to get it to run at an acceptable speed, since the expectimax algorithm cannot be optimized like minimax. and combinatorial explosion happens really fast.

Also, the program doesn't evaluate the entire branch if its probability is low enough (eg. getting 4 consecutive 4 tiles) so increasing the number of moves to look ahead by too much wouldn't do much as most of the tree will be pruned due to the low probabilities before reaching that depth. Again... combinatorial explosion happens really fast.

[Eppie]

I have a version in which I have implemented pthreads and uses up to 4 cores. I can make a pull request if anyone's interested.