Success!

Note

Error

Session expiration Your session is going to expireClick here to extend

Budget:

Small project <800

Posted on

10/27/13 12:59 AM

Buyer:

mka***

This project has expired

Why don't you register anyway? We are sure that you will find many similar projects out of the thousands waiting for you!

Post similar project now

Description

Project needs to be completed by 29th October, 2013 midnight PST. Please find the detailed project description in the PDF attached. Payment shall be made only after complete project completion. Sample input and output files for testing will be provided. Pictorial representations are attached in the pdf

 

Adversarial Search –Reversi

 

 

 1. Introduction

 

 Develop the Reversi game using Minimax and Alpha-Beta pruning algorithms with two different evaluation functions:

1) number of pieces

2) positional weights.

The rules of the Reversi game can be found e.g. in http://en.wikipedia.org/wiki/Reversi [1]. The interactive examples can be found e.g. http://www.samsoft.org.uk/reversi/[2].

 

The starting position will be specified in the input file.

 

 

 2. Tasks

Write a program to implement the following algorithms for both min and max players.

2.1 Minimax using number of pieces as an evaluation function ;

2.2 Alpha-Beta pruning using number of pieces as an evaluation function ;

2.3 Alpha-Beta pruning using positional weights as an evaluation function ;

 

 

 3. Specifications and Illustrative Examples

3.1 Players

Black = max player, White = min player

Assume that Max player always makes the first move from the configuration provided.

 

3.2 Legal moves and Flips/Captures

Let us assume that the current position is as shown in the right image below and that the current turn is Black’s. Black must place a piece with the black side up on the board, in such a position that there exists at least one straight (horizontal, vertical, or diagonal) occupied line between the new piece and another black piece, with one or more contiguous light pieces between them. The right image shows all the legal moves available to the Black player (see the translucent circles below that highlight the legal Black moves). If one player cannot make a valid move, play passes back to the other player.

 

 

Example of Flips/Captures: In the left image below, the legal Black moves are shown as red cells. After placing the piece at e7, Black turns over (i.e., flips or captures) all White pieces lying on a straight line between the newly added piece and any anchoring Black pieces [1]. All reversed pieces are shown in blue cell in the center image. In the right image, White can reverse those pieces back on his turn if those Black pieces lie on a straight line between the new White piece and any anchoring White pieces.

 

Example of Flips/Captures: In the left image, the available legal White moves are shown as red cells. After placing a new White piece at d3, all captured pieces are shown in blue cell in the center image. In the right image, Black can use his own turn to reverse those pieces back if he so chooses. However, in this example, Black makes a different move, essentially choosing to flip other pieces.

 

 

3.3 Evaluation function: number of pieces

 

The evaluation function of number of pieces can be computed by

E(s) = #black - #white

For example, the board in the picture above has evaluated value: E(s) = 4-1 = 3

 

3.4 Evaluation function: positional weights

 

 

Each position on the board has different strategic value. For example, the corners have higher strategic values than others. This evaluation function assigns different values for each position.

The evaluation function of positional weights can be computed by

E(s) = Weight_black - Weight_white

For example, the board in the picture above has evaluated value: E(s) = (4+0+0+0) - (0) = 4

 

3.5 Tie Breaking and Expand order

 

 

Ties between nodes are broken by selecting the node that is first in positional order on the right figure above. For example, if all legal moves (c4, d3, e6, f5) have the same evaluated values, the program must pick the d3 according to the tie breaker rule on the right figure.

Your traverse order must be in the positional order also. For example, your program will traverse on d3, c4, f5, e6 branch in order.

 

3.6 Ending the Game

The game ends when all squares are filled in or when both players have no play left.

 

3.7 Board size

The board size is fixed. It has 8 rows and 8 columns. The number of cells is 64.

 

4. Input

There are three inputs for your programs;

4.1 Which task to perform: there are three possible values

1 è Minimax using number of pieces as an evaluation function

2 è Alpha-Beta pruning using number of pieces as an evaluation function

3 è Alpha-Beta pruning using positional weights as an evaluation function

 

4.2 The cutting off depth

More details in AIMA section 5.4.2

 

4.3The initial board configuration:

* represents an empty space. X represents a black piece. O represents a white piece. For example, if the initial board configuration is in the left image, the input file contain texts in the right image.

 

5. Output

It is important to show how your search algorithms traverse the tree and moves. There are two output files that your program should produce.

 

5.1 Moves: List the moves at each step in order.

 

5.2 Logs of the first step: Show complete traverse logs of the first step. Please see the complete examples in output1_tlog_t1.txt, output1_tlog _t2.txt, output1_ tlog_t3.txt, output2_tlog_t1.txt, output2_tlog_t2.txt, output2_tlog_t3.txt.

 

6 Program Specifications

6.1 Your program must be written in C++.

6.2 Your program name must be "reversi" (without quotation mark).

 

7. Execution Details

Your program should run on a Linux Machine. Your program will receive 5 arguments, 3 for inputs and 2 for outputs.

 

7.1 C/C++

The code should execute using this command:

reversi -t <task> -d < cutting_off_depth> -i <input_file> -op <output_path> -ol <output_log>

Example:

reversi -t 1 -d 3 -i input1.txt -op output1_moves_minimax.txt -ol output1_tlog_ minimax.txt

 

7.3 Arguments:

7.3.1 <task> : there are 3 possible values 1, 2 and 3.

7.3.2 < cutting_off_depth >: the cutting-off depth

7.3.4 <input_file>: location of an input file.

7.3.5 <output_path>: location of an path output.

7.3.6 <output_log>: location of an traverse log output.

Thus, you should interpret the example:

reversi -t 1 -d 3 -i input1.txt -op output1_moves_minimax.txt -ol output1_tlog_ minimax.txt

The first task is chosen. The cutting-off depth is 3. The location of the input file is same as your program and its name is input1.txt. The location of path output file is same as your program and its name is output1_moves_minimax.txt. Finally, the location of traverse log output file is same as your program and its name is output1_tlog_ minimax.txt.

 

8.

Include an analysis of similarities/differences result between task1 and task2 and task2 and task3 evaluation functions. (Include in Readme)

 

9. References

1. http://en.wikipedia.org/wiki/Reversi

2. http://www.samsoft.org.uk/reversi/