AI for Ghosts in Pacman - Microbyte

AI for Ghosts in Pacman - Microbyte

Understanding Pac-Man Ghost Behavior
http://www.quora.com/What-is-the-algorithm-used-by-the-chasing-monsters-in-Pac-Man

A* is really easy to implement
Use Manhattan Distance as your heuristic - this is insanely easy to implement, and leads to very efficient searches
Look at http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html for more information (the entire series is really interesting)
http://home.comcast.net/~jpittman2/pacman/pacmandossier.html

Read full article from AI for Ghosts in Pacman - Microbyte

Tic Tac Toe: Understanding The Minimax Algorithm

Tic Tac Toe: Understanding The Minimax Algorithm
If the game is over, return the score from X's perspective.
Otherwise get a list of new game states for every possible move
Create a scores list
For each of these states add the minimax result of that state to the scores list
If it's X's turn, return the maximum score from the scores list
If it's O's turn, return the minimum score from the scores list
You'll notice that this algorithm is recursive, it flips back and forth between the players until a final score is found.

Fighting the Good Fight: Depth
The key improvement to this algorithm, such that, no matter the board arrangement, the perfect player will play perfectly unto its demise, is to take the "depth" or number of turns till the end of the game into account. Basically the perfect player should play perfectly, but prolong the game as much as possible.

In order to achieve this we will subtract the depth, that is the number of turns, or recursions, from the end game score, the more turns the lower the score, the fewer turns the higher the score.
https://github.com/jasonrobertfox/tictactoe

def score(game, depth)
    if game.win?(@player)
        return 10 - depth
    elsif game.win?(@opponent)
        return depth - 10
    else
        return 0
    end
end

https://www3.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html
1.2  Simplest Strategy – Heuristic Preferences via Table Lookup

Minimax with Alpha-beta Pruning
Alpha-beta pruning seeks to reduce the number of nodes that needs to be evaluated in the search tree by the minimax algorithm

http://www.codebytes.in/2014/08/minimax-algorithm-tic-tac-toe-ai-in.html

    public List<Point> getAvailableStates() {
        availablePoints = new ArrayList<>();
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    availablePoints.add(new Point(i, j));
                }
            }
        }
        return availablePoints;
    }

    public void placeAMove(Point point, int player) {
        board[point.x][point.y] = player;   //player = 1 for X, 2 for O
    }

        while (!b.isGameOver()) {
            System.out.println("Your move: ");
            Point userMove = new Point(b.scan.nextInt(), b.scan.nextInt());

            b.placeAMove(userMove, 2); //2 for O and O is the user
            b.displayBoard();
            if (b.isGameOver()) {
                break;
            } 
            b.callMinimax(0, 1);
            for (PointsAndScores pas : b.rootsChildrenScores) {
                System.out.println("Point: " + pas.point + " Score: " + pas.score);
            }
            b.placeAMove(b.returnBestMove(), 1);
            b.displayBoard();
        }

    public int minimax(int depth, int turn) {

        if (hasXWon()) return +1;
        if (hasOWon()) return -1;

        List<Point> pointsAvailable = getAvailableStates();
        if (pointsAvailable.isEmpty()) return 0; 

        List<Integer> scores = new ArrayList<>(); 

        for (int i = 0; i < pointsAvailable.size(); ++i) {
            Point point = pointsAvailable.get(i);  

            if (turn == 1) { //X's turn select the highest from below minimax() call
                placeAMove(point, 1); 
                int currentScore = minimax(depth + 1, 2);
                scores.add(currentScore);

                if (depth == 0) 
                    rootsChildrenScores.add(new PointsAndScores(currentScore, point));
                
            } else if (turn == 2) {//O's turn select the lowest from below minimax() call
                placeAMove(point, 2); 
                scores.add(minimax(depth + 1, 1));
            }
            board[point.x][point.y] = 0; //Reset this point
        }
        return turn == 1 ? returnMax(scores) : returnMin(scores);
    }

http://www.flyingmachinestudios.com/programming/minimax/

http://www.coderslexicon.com/a-beginner-tic-tac-toe-class-for-java/
https://sites.google.com/site/arjunwebworld/Home/programming/tic-tac-toe-game
Always occupy center.
Check if you can win.
Check if you need to block.
Always occupy middle space.
Occupy any free space.
http://algojava.blogspot.com/2012/05/tic-tac-toe-game-swingjava.html
Read full article from Tic Tac Toe: Understanding The Minimax Algorithm

HackerRank: N Puzzle

HackerRank: N Puzzle

N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to N. Your task is to reposition the tiles to their proper order.

N-Puzzle is a classic 1 player game that teaches the basics of heuristics in arriving at solutions in Artificial Intelligence.

The final configuration of an 8 - puzzle will look like

0 1 2
3 4 5
6 7 8

A* algorithm talks about a cost function and a heuristic.

cost = heuristic_cost + #of steps taken to reach the current state.

the tiles are numbered. For a given unsolved 8 - puzzle configuration say

0 3 8
4 1 7
2 6 5

We use 2 heuristics for every state and at every iteration

1 such heuristic is

h1 => The number of misplaced tiles.

In the above example, the number of misplaced tiles are 8

2nd heuristic we use is

h2 => The manahattan distance between a tile's original position to its current position.

In the above example, the manhattan distance for all tiles are as follows

ab => where a is the manhattan distance of tile b.

h2 = 23 + 28 + 14 + 11 + 27 + 42 + 16 + 15

h2 = 14

Given 2 heuristics, it is always advised to use the maximum as the maximum never underestimates the cost to reach the required end state ( initial configuration of 8 Puzzle )

If it took 10 moves to reach the current state as shown above, then the cost function of a given state of N - puzzle

is given as

cost = max( h1, h2 ) + 10

cost = max( 14, 8 ) + 10 = 24

We can then implement a priority queue and record each of possible moves from a given initial state of the board and then pop the state with the lowest cost function. This procedure is guaranteed to give us a solution.

airbnb面试题汇总

九宫格，一共8个方块，从1-8，一个方块空出来，然后打乱之后通过SLIDE还原，这个题要推广到N宫格，先实现这个游戏，然后对于一个任意的BOARD，要你把他解出来

def dis(x, y):  # A* evaluation func
    return (x - 2) ** 2 + (y - 2) ** 2


def play(board):
    m, n = len(board), len(board[0])
    x, y = 0, 0
    for i in xrange(m):
        for j in xrange(n):
            if board[i][j] == '0':
                x, y = i, j
    board_key = ''.join(''.join(row) for row in board)
    heap = [(dis(x, y), x, y, board_key)]
    visited = set()

    while heap:
        _, x, y, cur = heapq.heappop(heap)
        if cur in visited:
            continue
        visited.add(cur)
        if cur == "123456780":
            return True
        for dx, dy in zip((1, -1, 0, 0), (0, 0, 1, -1)):
            new_x, new_y = x + dx, y + dy
            if 0 <= new_x < m and 0 <= new_y < n:
                pos1, pos2 = x * m + y, new_x * m + new_y
                new_board = list(cur)
                new_board[pos1], new_board[pos2] = new_board[pos2], new_board[pos1]
                heapq.heappush(heap, (dis(new_x, new_y), new_x, new_y, ''.join(new_board)))

    return False

typedef tuple<int, int, int, string> boardInfo;
bool validSlidingGame(vector<vector<int> >& board) {
    const int m = board.size(), n = board[0].size();
    auto dis = [](int x, int y, int z, int p) {return (x - z) * (x - z) + (y - p) * (y - p); };
    int x = 0, y = 0;
    string key = "";
    const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    priority_queue<boardInfo> pq;
    unordered_set<string> visited;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 0) {
                x = i, y = j;
            }
            key += to_string(board[i][j]);
        }
    }
    pq.push(make_tuple(-dis(x, y, m - 1, n - 1), x, y, key));
    visited.insert(key);
    while (!pq.empty()) {
        auto tp = pq.top();
        pq.pop();
        string curKey;
        tie(ignore, x, y, curKey) = tp;
//        x = get<1>(tp), y = get<2>(tp);
//        auto curKey = get<3>(tp);
        if (curKey == "123456780") return true;
        for (int i = 0; i < 4; ++i) {
            int newX = x + dir[i][0];
            int newY = y + dir[i][1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                swap(curKey[x * m + y], curKey[newX * m + newY]);
                if (!visited.count(curKey)) {
                    pq.push(make_tuple(-dis(newX, newY, m - 1, n - 1), newX, newY, curKey));
                    visited.insert(curKey);
                }
            }
        }
    }
    return false;
}

https://medium.com/towards-data-science/solve-slide-puzzle-with-hill-climbing-search-algorithm-d7fb93321325

https://www.codeproject.com/Articles/368188/AI-Sliding-Puzzle-Solution-Analyzer
BFS algorithm also works without history, but due to the loopy structure of the sliding puzzle, the search space becomes unbounded. Hence, filling up the memory before the solution is found to become extremely possible. On the algorithm tests, it is seen that BFS cannot solve puzzles exceeding 15 steps in a reasonable time (2-3 minutes). However, after implementing history, it can reach to 25 steps in a reasonable time.

HackerRank: Pacman A*

HackerRank: Pacman A*

In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes expanded using search using a simple yet efficient heuristic.

AStar on graphs uses the following function

cost = d(s,c) + h(c)

where s is the source node, c is the node currently expanded and h(c) is the estimation of the cost to reach from c to the destination ( food ).

In this game, we use manhattan heuristic as an estimate. Given two nodes (r,c) and (r1,c1). The manhattan heuristic is the manhattan distance between the two nodes and is given by

|r1 - r | + |c1 - c|

https://codepair.hackerrank.com/paper/QG1xc8Pg?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
private Node UCS() {
Queue<Node> queue = new PriorityQueue<Node>(X * Y, new Comparator<Node>() {
@Override
public int compare(Node node1, Node node2) {
return node1.distance() + cost(node1) - (node2.distance() + cost(node2));
}
});

boolean[][] explored = new boolean[X][Y];

queue.add(new Node(pacman));

while (!queue.isEmpty()) {
Node node = queue.poll();

int x = node.position()[0];
int y = node.position()[1];

if (explored[x][y]) {
continue;
}
explored[x][y] = true;

if (node.isFood()) {
return node;
}

if (isValidMove(x - 1, y) && !explored[x - 1][y]) {
queue.add(new Node(new int[] {x - 1, y}, node));
}
if (isValidMove(x, y - 1) && !explored[x][y - 1]) {
queue.add(new Node(new int[] {x, y - 1}, node));
}
if (isValidMove(x, y + 1) && !explored[x][y + 1]) {
queue.add(new Node(new int[] {x, y + 1}, node));
}
if (isValidMove(x + 1, y) && !explored[x + 1][y]) {
queue.add(new Node(new int[] {x + 1, y}, node));
}
}
return null;
}
private boolean isValidMove(int x, int y) {
return x >= 0 && y >= 0 && x < X && y < Y && board[x][y] != WALL;
}

private int cost(Node node) {
return (node.position()[0] > food[0] ? node.position()[0] - food[0] : food[0] - node.position()[0]) +
(node.position()[1] > food[1] ? node.position()[1] - food[1] : food[1] - node.position()[1]);
}
private Node(int[] position, Node parent) {
this.position = position;
this.parent = parent;
this.distance = parent.distance() + 1;
}

Searching using A* (A-Star)

Searching using A* (A-Star)
The question arises while programming bfs and dfs: What if instead of blindly guessing the next node to traverse like in a simple dfs we pick the node which looks most promising? A* searches exactly like that: in a nutshell, we generate our possibilities and pick the one with the least projected cost. Once a possibility is generated and its cost is calculated, it stays in the list of possibilities until all the better nodes have been searched before it.

The cost function: f = g + h
 g is the cost it took to get to the node, most likely the number of squares we passed by from the start. h is our guess as to how much it'll cost to reach the goal from that node. It's our heuristic (a heuristic, informally, is something which is not a definite series of steps to a solution (like an algorithm) but it helps us determine our answers is a rough way).

struct node {
    node *parent;
    int x, y;
    float f, g, h;
}

Introduction to A*
http://www.redblobgames.com/pathfinding/a-star/introduction.html
I recommend using both: pathfinding for big picture, slow changing obstacles, and long paths; and movement for local area, fast changing, and short paths.

These algorithms represent the map as a graph and then find a path in that graph.
The key idea for all of these algorithms is that we keep track of an expanding ring called the frontier.
BFS:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

current = goal
path = [current]
while current != start:
   current = came_from[current]
   path.append(current)

Movement costs

We want Dijkstra’s Algorithm for this.

We need to track movement costs, so let’s add a new variable, cost_so_far, to keep track of the total movement cost from the start location. We want to take the movement costs into account when deciding how to evaluate locations; let’s turn our queue into a priority queue. Less obviously, we may end up visiting a location multiple times, with different costs, so we need to alter the logic a little bit. Instead of adding a location to the frontier if the location has never been visited, we’ll add it if the new path to the location is better than the best previous path.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost
         frontier.put(next, priority)
         came_from[next] = current

Movement costs can also be used to avoid or prefer areas based on proximity to enemies or allies.
Heuristic search

With Breadth First Search and Dijkstra’s Algorithm, the frontier expands in all directions. This is a reasonable choice if you’re trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. Let’s make the frontier expand towards the goal more than it expands in other directions. First, we’ll define a heuristic function that tells us how close we are to the goal:

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y)

In Dijkstra’s Algorithm we used the actual distance from the start for the priority queue ordering. Here instead, in Greedy Best First Search, we’ll use the estimated distance to the goal for the priority queue ordering. The location closest to the goal will be explored first. The code uses the priority queue from Breadth First Search but not cost_so_farfrom Dijkstra’s Algorithm:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      if next not in came_from:
         priority = heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

Those paths aren’t the shortest. So this algorithm runs faster when there aren’t a lot of obstacles, but the paths aren’t as good.
The A* algorithm
Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. Greedy Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

A* combines the two. Instead of contour lines showing distances from start or goal, in A* the contour lines show the length of the paths. The inner region has the shortest paths. A* starts by exploring that inner region, and moves outwards only if it can’t find a path in there. Try drawing some walls to see how A* has to climb out of the innermost region to find a path.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

You can see that A* tries to stay within the same estimated path length (which we use as the priority for the queue) as much as possible. Why does it run faster than Dijkstra’s Algorithm? Both algorithms explore the same set of locations. However, the heuristic function lets us visit the locations in a different order that makes it more likely that the goal node will be encountered sooner.

• If you want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary.
• If you want to find paths to one location, use Greedy Best First Search or A*. Prefer A* in most cases. When you’re tempted to use Greedy Best First Search, consider using A* with an “inadmissible” heuristic.

What about optimal paths? Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic is never larger than the true distance. As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. As the heuristic becomes larger, A* turns into Greedy Best First Search.

What about performance? The best thing to do is to eliminate unnecessary locations in your graph. If using a grid, see this. Reducing the size of the graph helps all the graph search algorithms. After that, use the simplest algorithm you can; simpler queues run faster. Greedy Best First Search typically runs faster than Dijkstra’s Algorithm but doesn’t produce optimal paths. A* is a good choice for most pathfinding needs.

Read full article from Searching using A* (A-Star)