search

nneonneo / 2048-ai

AI for the 2048 game
MIT License
1.09k stars 279 forks source link

Speedup #14

Closed m9710797 closed 9 years ago

m9710797 commented 10 years ago

Hi,

As already mentioned in an earlier email I've took your 2048-ai code and made it approx 1.5x faster (depending on exactly which compiler/machine you test on). I've now now split my work in many small patches. Hopefully these are easy enough to understand.

You probably don't won't to merge my branch as-is. E.g. the very first patch removes the random seed (so that I always get the same sequence of random number to be able to benchmark). You may or may not want the last 4 patches because they remove the .so / python functionality (see commit messages of the actual commits for lots more details). In general I tried to order the patches so that the more stable/useful patches are in front of the more experimental ones.

Wouter

PS: this is my first git pull request I'm sending. let me know if i did something wrong or in an unconventional way.

nneonneo commented 10 years ago

I've merged all the commits I'm willing to take. Experiments seem to show a decent 20-30% speedup for real games. Thank you for these patches!

m9710797 commented 10 years ago

Great. Although I'm slightly disappointed with the performance increase you see. I did a few experiments (all using the same sequence of random numbers, all measurements are +/-5s)

I didn't have time to test each individual patch in detail, but (surprisingly to me) patch d961ca314f7c Experiment: unroll move-loop in score_move_node seems to be responsible for the largest part of the remaining speed difference

I also noticed that some patches individually reduce performance, but in combination with others they do improve performance (e.g the patches that reduce the table sizes .. I guess these only start having a positive effect once the data starts fitting in the CPU cache(s)).

Anyway, 30% faster is also already a nice result. Thanks for merging my patches. In any case I had fun playing with your code.

Wouter

On Sun, Apr 13, 2014 at 2:22 AM, Robert Xiao notifications@github.comwrote:

I've merged all the commits I'm willing to take. Experiments seem to show a decent 20-30% speedup for real games. Thank you for these patches!

— Reply to this email directly or view it on GitHubhttps://github.com/nneonneo/2048-ai/pull/14#issuecomment-40295903 .

mhriemers commented 10 years ago

It has become slower for me...

Game over. Final score 20964; Highest tile 2048; Time taken 96 seconds! Game over. Final score 20240; Highest tile 2048; Time taken 98 seconds! Game over. Final score 20284; Highest tile 2048; Time taken 93 seconds!

Before it only took like 40 seconds.

nneonneo commented 10 years ago

@ipsq: And if you revert to the previous code, build a new DLL, and try the same test, is it slower or faster?

I'll be very interested if these changes caused a regression, since I don't see that myself.