{"action":"created","issue":{"url":"https://api.github.com/repos/nneonneo/2048-ai/issues/27","labels_url":"https://api.github.com/repos/nneonneo/2048-ai/issues/27/labels{/name}","comments_url":"https://api.github.com/repos/nneonneo/2048-ai/issues/27/comments","events_url":"https://api.github.com/repos/nneonneo/2048-ai/issues/27/events","html_url":"https://github.com/nneonneo/2048-ai/pull/27","id":35202876,"number":27,"title":"Improved algorithm reaching 32k tile","user":{"login":"xificurk","id":117465,"avatar_url":"https://avatars.githubusercontent.com/u/117465?v=3","gravatar_id":"","url":"https://api.github.com/users/xificurk","html_url":"https://github.com/xificurk","followers_url":"https://api.github.com/users/xificurk/followers","following_url":"https://api.github.com/users/xificurk/following{/other_user}","gists_url":"https://api.github.com/users/xificurk/gists{/gist_id}","starred_url":"https://api.github.com/users/xificurk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/xificurk/subscriptions","organizations_url":"https://api.github.com/users/xificurk/orgs","repos_url":"https://api.github.com/users/xificurk/repos","events_url":"https://api.github.com/users/xificurk/events{/privacy}","received_events_url":"https://api.github.com/users/xificurk/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":14,"created_at":"2014-06-07T07:15:36Z","updated_at":"2015-05-22T23:29:45Z","closed_at":"2014-07-05T21:17:08Z","pull_request":{"url":"https://api.github.com/repos/nneonneo/2048-ai/pulls/27","html_url":"https://github.com/nneonneo/2048-ai/pull/27","diff_url":"https://github.com/nneonneo/2048-ai/pull/27.diff","patch_url":"https://github.com/nneonneo/2048-ai/pull/27.patch"},"body":"This PR improves the algorithm, so that it consistently reaches 32k tile. Here (https://www.dropbox.com/s/9463l6ztznj3zy0/2048.png) is a \"Game over\" screenshot of one of the best games I've seen it play.\r\n\r\nFirst there are couple of minor code tweaks. I have also moved caching and search termination code to `score_tilechoose_node` method. Imho, it makes more sense to use it after player's deterministic move, instead of after random computer move, although the benchmarking I tried did not show significant improvements. The two most important commits are **new heuristic scoring** and **adaptive search depth limit**.\r\n\r\n**New heuristic scoring**\r\n\r\nIt uses a combination of three factors - number of empty tiles, number of available merge moves and monotonicity of the row/column.\r\nAn empty tile is in fact as important as the ability to create it by merging tiles of the same value.\r\nThe monotonicity of the row/column enforces generally good position for building up higher and higher tiles. Look at the code for more details, it's pretty self-explanatory. The calculation uses third powers of tile values, so that higher tiles get more severe penalty if they are moved in the middle of the board.\r\n\r\n**Adaptive search depth limit**\r\n\r\nThis gives a huge speed boost, especially early in the game. The idea is that you need to search the game tree really deep only if the board gets complicated. A good measure of the board complexity is the number of distinct tiles. With this patch AI alternates between extremely fast segments (right after it builds a new highest tile) and slow segments (right before it builds a new highest tile).\r\nI've measured a time it took to get to a certain tile for the original algorithm and the new one, here is how much time this patch saves:\r\n 2k: 50%\r\n 4k: 45%\r\n 8k: 30%\r\n16k:  5%\r\nAs you can see, the time to reach winning 2k tile was cut in half and it stays faster roughly up to a point when it builds 16k tile.\r\n\r\n**Benchmark results**\r\n\r\n(for final results see the last post)\r\n\r\nThere is ceratinly a room for tweaking the code, but I doubt it will be possible to get another significant improvement while keeping the computational cost at a sane level."},"comment":{"url":"https://api.github.com/repos/nneonneo/2048-ai/issues/comments/104801326","html_url":"https://github.com/nneonneo/2048-ai/pull/27#issuecomment-104801326","issue_url":"https://api.github.com/repos/nneonneo/2048-ai/issues/27","id":104801326,"user":{"login":"nneonneo","id":75449,"avatar_url":"https://avatars.githubusercontent.com/u/75449?v=3","gravatar_id":"","url":"https://api.github.com/users/nneonneo","html_url":"https://github.com/nneonneo","followers_url":"https://api.github.com/users/nneonneo/followers","following_url":"https://api.github.com/users/nneonneo/following{/other_user}","gists_url":"https://api.github.com/users/nneonneo/gists{/gist_id}","starred_url":"https://api.github.com/users/nneonneo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nneonneo/subscriptions","organizations_url":"https://api.github.com/users/nneonneo/orgs","repos_url":"https://api.github.com/users/nneonneo/repos","events_url":"https://api.github.com/users/nneonneo/events{/privacy}","received_events_url":"https://api.github.com/users/nneonneo/received_events","type":"User","site_admin":false},"created_at":"2015-05-22T23:29:45Z","updated_at":"2015-05-22T23:29:45Z","body":"That's very impressive! Clearly the heuristics are very strong.\r\n\r\nHow well can it perform with deeper searching? If you make it work harder (maybe to 20 moves/sec) then can it get to 65536 sometimes?"}}