Poor AI for 2048 written in Haskell

I'm learning Haskell and thought it would be fun to write an AI for the game 2048 in Haskell.

In my implementation I got rid of the randomized aspects of the game.

This makes the program deterministic (or pure). However, I don't think it performs very well. It uses a very simple algorithm:

Recurse into all possible moves with depth x and return the number of empty tiles of the result. The move that results in the highest number of empty tiles is seen as the best move.

I use a 16-length List to represent the board. I am afraid that the many list operations make my program very slow, and wonder if there are better ways to solve this.

The code:

```
{--

Plays and solves the game 2048

--}
import Data.Time
import Control.Monad

emptyGrid :: [Int]
emptyGrid = [ 0 | _ String
gridToString [] = ""
gridToString xs = show (take 4 xs) ++ "\n" ++ gridToString (drop 4 xs)

printGrid :: [Int] -> IO()
printGrid xs = putStrLn $ gridToString xs

-- Skip n empty tiles before inserting
addTile :: Int -> [Int] -> [Int]
addTile 0 (0:grid) = 2 : grid
addTile n [] = []
addTile n (0:grid) = (0 : addTile (n-1) grid)
addTile n (cell:grid) = cell : addTile n grid

-- Insert multiple tiles at once
addTiles :: [Int] -> [Int] -> [Int]
addTiles [] grid = grid
addTiles (n:ns) grid = addTiles ns (addTile n grid)

-- For one row of the grid, push the non-empty tiles together
-- e.g. [0,2,0,2] becomes [2,2,0,0]
moveRow :: [Int] -> [Int]
moveRow [] = []
moveRow (0:xs) = moveRow xs ++ [0]
moveRow (x:xs) = x : moveRow xs

-- For one row of the grid, do the merge (cells of same value merge)
-- e.g. [2,2,4,4] becomes [4,8,0,0]
-- [2,4,2,2] becomes [2,4,4,0]

mergeRow :: [Int] -> [Int]
mergeRow [] = []
mergeRow (a:[]) = [a]
mergeRow (a:b:xs)
| a == b = (a + b) : (mergeRow xs) ++ [0]
| otherwise = a : mergeRow (b:xs)

-- Ro

First of all - way to go! Type signatures, pattern matching, monads - you're clearly on the right track.

Some general tips:

-
Don't reinvent the wheel!

When you encounter a function that looks like this:

secondFromTuple :: (a,a) -> a
secondFromTuple (x,y)       = y

your first thought should be: "wait, that's a really simple and usefuly function. I wonder if it's already in the standard library?". Well, let's search Hoogle for the type signature (a,a)->a: http://www.haskell.org/hoogle/?hoogle=%28a%2Ca%29-%3Ea

The first result is: snd :: (a, b) -> b, which is actually the right function. snd is even more general than secondFromTuple - the latter won't work on (0,"zero"), for example, because it's type is (Int,String) and secondFromTuple only work on homogenous tuples.

Another example: maximum is a standard library function that behave just like maxInList. Notice that maxInList [] will result in a pattern match failure while maximum [] will result in an empty list exception.

Now let's take a look at maxTuple. It takes a list of tuples and return the second item of the tuple with the highest first item. Can we replace it with a standard library function?

Well, the Data.List module contains maximumBy :: (a -> a -> Ordering) -> [a] -> a. The By family of functions - sortBy,nubBy - are variation of standard function like maximum,sort and nub, which compares items using an external comparison function. Usually, and easy way to create one is with the comparing function from Data.Ord. For example, comparing fst is a function that gets 2 tuples and compares them by the first element. So maximumBy (comparing fst) will return the tuple with the highest first item, and snd will return its second item.

So we can rewrite maxTuple as maxTuple xs = snd $ maximumBy (comparing fst), or in pointfree style - maxTuple = snd . maximumBy (comparing fst).

There's one small issue here: One, we don't know how maximumBy resolves ties - if it's an issue, you can modify the solution a little, maybe use sortBy or write a different comparison function.

-
If you need to fail - fail

maxTuple [] returns -1, and that's not a good idea. maxTuple [(0,-1)] returns -1 as well - how can you tell if it's a valid result?

If a function encounters an invalid state - you need to report an error. There are several ways to do it - I'll mention two:

-
Throw an error: maxTuple [] = error "maxTuple: empty list". It's the simplest way to do it, and in a small-scale project it's probably the best. The downside is that error-handling is an IO operation, so this error can't be handled in pure code.

-
The Maybe monad:

maxTuple :: [(Int,Int)] -> Maybe Int
maxTuple [] = Nothing
maxTuple xs = Just $ snd $ maximumBy (comparing fst)

This is the safer way to do it. A failure results in Nothing. The caller can then deal with this Nothing instead of simply crashing the program. The downside is that now you need to examine the value of maxTuple before using it, which complicates the code. Data.Maybe and Control.Monad can help with this task.

You can read more about proper Haskell error handling in this great article.

-
Use data instead of hardcoded values

Instead of representing directions with 0-3, you can use data:

data Direction = Left | Right | Up | Down
                 deriving (Show)

Now move is more readable:

move :: Direction -> [Int] -> [Int]
...
move Left grid  = ...
move Right grid = ...
move Down grid  = ...
move Up grid    = ...

Also, since there's no 5th direction, move 4 results in a pattern match failure. In the new version, there is no such danger.

Plus, deriving (Show) means we can use show on Direction value - so we get moveToString for free: show Left returns "Left", show Down returns "Down" and so on.

That's it for now. Good luck!

StackExchange Code Review Q#46493, answer score: 7