3 ms·
That's awesome. I'm looking at the source code but I can't seem to grasp it. What's a simple explanation of how it works?
by andyhmltn 13y ago
That's awesome. I'm looking at the source code but I can't seem to grasp it. What's a simple explanation of how it works?
- rcoh 13y agoFrom github: The algorithm is iterative deepening depth first alpha-beta search. The evaluation function tries to minimize the number of tiles on the grid while keeping same/similar tiles in line with each other. This basically means he's running an optimized version of minimax -- essentially, depth first search of game states looking for states that minimize tiles and keep them in line. At each step, he looks several steps into the future, assigns them each a numerical score, then picks the move that leads to the best outcome. Iterative deepening means that he evaluates all 1 move options, then all two move options, then all 3 moves options and so on. It increases the chances of finding a good move within a time constraint. Alpha beta is a "lossless" optimization that allows you to more aggressively prune the tree when you're searching.
- shmageggy 13y agoSorry, the code is a little unkempt. The basic idea is minimax search. Googling that will get you started, but basically the algorithm plays out the game and keeps a score of the position after every move. Then it just makes the move that leads to the best score. The "score" here is basically a count of how many free squares there are (with a little extra to keep things aligned if possible). One major thing with these search algorithms is that the game tree grows exponentially as you move forward. To combat that, implemented alpha-beta pruning and a heuristic to only search the nastier computer moves rather than all of the possibilities.
- andyhmltn 13y agoAwesome, thanks for that! I was going to try when I saw the thread earlier but couldn't figure out how.