Minimax Algorithm in Game Playing

Consider a game of two players, call one of the players as MAX and the other player as MIN. And in the game MAX makes the first move and then they take turns alternatively till the end of the game.

The various components of the Game:

1. Initial State: This includes the board position and the player who will move first.
2. Successor Function: For a node it returns the list of it's successor function and the state they will result into.
3. Terminal States: The states where the game has ended.
4. Utility Function: This gives a numerical value to all the terminal states. High values are considered good for MAX and bad for MIN and vice-versa.

The following video gives a complete explanation of the Minimax Algorithm.

Following is the Minimax Algorithm:

Source: Artificial Intelligence: A Modern Approach

The Subset Problem and it's recursive implementation

Suppose we have a set S with n number of elements. How many different ways can you select k  elements from the set S. So we solve the problem using recursion. Here is a video explaining the problem and below that is the recursive implementation of the subset problem.

Implementation:

int C(int n,int k) {

   if (k==0 || k==n)

     return 1;

   return C(n-1,k-1) + C(n-1,k);

}

Boundary Fill Algorithm

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in games such as Go and Minesweeper for determining which pieces are cleared. When applied on an image to fill a particular bounded area with color, it is also known as boundary fill.

This is the code discussed in the video.

void boundaryFill4 (int x, int y, int fill, int boundary) {

 int current:

 current = getpixel (x, y);

  if ((current != boundary) && (current != fill)) {

   setcolor (fill);

   setpixel (x, y):

   boundaryFill4 (x+l, y, fill, boundary);

   boundaryFill4 (x-1, y, fill, boundary);

   boundaryFill4 (x, y+l, fill, boundary);

   boundaryFill4 (x, y-1, fill, boundary) ;

 }

}

Text Source: http://en.wikipedia.org/wiki/Flood_fill

Scan Line Polygon Fill Algorithm

The scanline fill algorithm is an ingenious way of filling in irregular polygons. The algorithm begins with a set of points. Each point is conected to the next, and the line between them is considered to be an edge of the polygon. The points of each edge are adjusted to ensure that the point wih the smaller y value appears first. Next, a data structure is created that contains a list of edges that begin on each scanline of the image. The program progresses from the first scanline upward. For each line, any pixels that contain an intersection between this scanline and an edge of the polygon are filled in. Then, the algorithm progresses along the scanline, turning on when it reaches a polygon pixel and turning off when it reaches another one, all the way across the scanline. 

Text Source: http://www.sccs.swarthmore.edu/users/02/jill/graphics/hw3/hw3.html