Creating a bot for Checkers

In the previous post, we learnt about adversarial search. Before we relax more assumptions on search problems and move on to general games, let’s first see how we can create a bot for a zero-sum game, in particular, checkers.

Checkers State

Checkers or Draughts is a strategy board game for two players, played on an 8×8 chess board. There is a challenge on Hackerrank for creating a checkers bot. You can read the problem statement and the input/output format there. We’ll try to solve that challenge in this post.

Continue reading

Informed Search Algorithms

In the previous post, we discussed some uninformed search algorithms. The reason they performed so inefficiently is, well unsurprisingly, because they were uninformed. They used no knowledge about features of the search space. It’s frustrating and sometimes hilarious to see your agent running around the entire search space, always missing a goal node nearby. For most problems, we always have some indication of which nodes are better than others; which nodes are closer to a solution and which are not, and it would be nice if we could inject this knowledge in our agent so that it can direct its search towards more promising paths and find a solution more efficiently while exploring as little of the search space as possible.

Continue reading

Uninformed Search Algorithms

In the previous post, we learnt how we can model a search problem, the general tree search algorithm and properties of search algorithms. In this post, we’ll see how a search problem looks like in code, several uninformed search algorithms, why they are called uninformed and their properties.

Continue reading

Alpha Beta Search

It’s been a long time since my last post. Lets hope this one goes alright. Alpha Beta Search is typically used for two-player competitive (fixed sum) games and is a variant of naive Minimax search. It can save almost 99.9% of the work while still computing the same move as found by the minimax search. Lets look at how it works.

Continue reading

Heuristic/Evaluation Function for Nine Men’s Morris

Nine Men’s Morris is a two-player strategy board game. The game has three clearly delimited phases:

Phase 1: Placing pieces
Players alternatively place their pieces on the board. If a player closes a morris (or mill), she will grab one of her opponent’s piece. Strategically placing the pieces is more important than closing a morris in this phase.
Phase 2: Moving pieces
Players alternatively move their pieces one at a time to an adjacent empty point, close morrises and grab pieces.
Phase 3: Flying pieces
A player reaches phase 3 when she is left with only 3 pieces. She can now move any of her piece to any empty point on the board.

A player wins by reducing her opponent to two pieces, or by leaving her without a legal move.

Continue reading

A* search algorithm

A* search is an informed search algorithm used for path-finding and graph traversal. It combines the advantages of both Dijkstra’s algorithm (in that it can find a shortest path) and Greedy Best-First-Search (in that it can use a heuristic to guide search). It combines the information that Dijkstra’s algorithm uses (favoring vertices that are close to the starting point) and information that Best-First-Search uses (favoring vertices that are closer to the goal).

Continue reading

Median of a dynamic list

Here, I discuss the problem of maintaining the running median of a list when numbers are added and removed from the list. The straightforward solution of keeping the list sorted takes constant time per median calculation but linear time per addition/deletion. It would be too slow for our purpose.

Continue reading