Question

Kōnane is a two-player game of capture played on a rectangular board. It begins with the board filled with alternating black and white stones. The players remove two stones that are adjacent vertically or horizontally, either from the middle of the board or from a corner.

Then, players alternate moves in which a stone of the player's color jumps over one or more opposing stones, all in the same direction. The stones jumped over are removed. Moves are either vertical or horizontal, never diagonal. Each move must make at least one jump, though if more jumps are possible in one direction, jumps after the first are optional.

The first player unable to jump an opponent's piece loses; the other player wins.

questions:

How does the program's static evaluation function (SEF) evaluate a board configuration?

Answer 1

SOLUTION:

This ancient Hawaiian version of Checkers is a challenging game of strategy and skill. Originally played using shells and lava rocks as pieces, Konane is a simple game to learn, yet is complicated enough to take a lifetime to master. The objective is simple: be the last player able to make a move.

Konane is played on a rectangular grid of spaces all of which are initially occupied by alternating black and white pieces. Konane boards do not follow any established pattern in size and range from 6x6 boards to well over 14x14 boards.

To begin the game the first player (black) must remove one of their pieces, either the center piece, one laterally next to it or one at a corner. Using the row and column numbering, black would remove either (1,8), (8,1), (4,5) or (5,4). The second player (white) now removes a piece of their own, adjacent to the space created by black’s first move. For example, if black removed (1,8) white may remove (2,8) or (1,7). If black removed (4,5), white may remove (4,6), (4,4), (3,5) or (5,5). Thereafter players take turns making moves on the board. A move consists of jumping the players piece over an adjacent opponent’s piece into an empty space and removing that opponent’s piece. Jumping must occur along a row or column (not diagonally) and a player may jump over multiple opponent’s pieces provided they are all on the same row/column and are all separated by empty spaces. The piece may jump up to (6,7), right to (8,5), left to (4,5), multiple jump left to (2,5) or down to (6,3). However, these are not the only possible moves for the black player. They may move from (7,8) to (7,6), (7,8) to (7,4), (7,8) to (7,2), (8,7) to (6,7), (8,7) to (8,5), (8,3) to (6,3), (2,3) to (2,5), (5,2) to (7,2) or (6,1) to (6,3). The game is finished when the current player has no available moves left.

Game Playing and the Minimax Algorithm:

The Minimax algorithm can be applied to any two-player game in which it is possible to enumerate all of the next moves. In theory we could represent the entire game in a search tree, starting with the root node as the original state of the game, and expanding the nodes at each level to represent possible states after the next move has taken place. The levels could be expanded all the way to the end-game state to complete the tree. This, however, becomes very complex when dealing with a game with a high branching factor such as Konane which typically has a branching factor averaging 10 (using an 8x8 board), and impossible with games such as Chess which has an average branching factor of 30. It is therefore not feasible for an artificial player to store the entire tree or search down to the leaves to determine the best move. Instead we use a static evaluation function which estimates the goodness of a board position for one player. The static evaluation function is used in conjunction with the Minimax algorithm and a search is performed through a limited depth of the tree to approximate the best move.

Minimax defines two players; MIN and MAX. A search tree is generated starting with the current game state down to a specified depth. A MAX node is a node that represents the game state directly after a move by the MIN player. Likewise, a MIN node is a node that represents the game state directly after a move by the MAX player. The leaf nodes are evaluated using a static evaluation function defined by the user. Then the values of the inner nodes of the tree are filled in from the leaves upwards. MAX nodes take the maximum value returned by all of their children, while MIN nodes take the minimum value returned by all of their children. The values at each level represent how ‘good’ a move is for the MAX player. In a game of perfect information such as Konane, the MIN player will always make the move with the lowest value and the MAX player will always make the move with the highest value. This algorithm is popular and effective in game playing. However it is computationally expensive, so searching deeper than four levels to play Konane is unrealistic during a real-time game. Its expensive nature is partially due to the move/board generation. However, a good static evaluation function for an nxn Konane board can take up to O(2n 3 ) time. Therefore search to depth d using the Minimax algorithm can be expected to take O(2n 3k d ) time where k is the average branching factor. The Alpha-Beta pruning algorithm can be used to decrease the potential number of evaluations, however it may prune out potentially excellent moves, and in this work it was not used. It is also important to note that Minimax is dependent on having a decent static evaluation function (although a deeper search will make up for some weakness in the static evaluation function).

Characteristics of Konane Game :

1.The activity must not be deterministic in the practical sense. There exists no known algorithm which will guarantee a win or a draw in Konane.

2. A definite goal must exist and at least one criterion or intermediate goal must exist which has a bearing on the achievement of the final goal and for which the sign should be known. In Konane the goal is to deprive the opponent of the possibility of moving, and one of the dominant criteria is the number of pieces of each color on the board, another is the number of movable pieces of each color on the board.

3. The rules of the activity must be definite and they should be known. Konane is a perfect information game and therefore satisfies this requirement.

4. There should be a background of knowledge concerning the activity against which the learning progress can be tested. For the purpose of testing the artificial Konane player, multiple strategic players have been created, as well as a random player.

5. The activity should be one that is familiar to a substantial body of people so that the behavior of the program can be made understandable to them. The ability to have the program play against human opponents (or antagonists) adds spice to the study and, incidentally, provides a convincing demonstration for those who do not believe that machines can learn. Konane has simple rules and is easy to learn.

Konane and Combinational game theory :

Konane complies with six essential assumptions needed by combinational game theory; it is a two player game, both players have complete information, chance takes no part, players move alternately, the first player unable to move loses, and the game is guaranteed to win. Another property which makes Konane an ideal candidate for combinational game theory is that it can of ten can be divided into independent sub-games whose outcomes can be combined to determine the outcome of the entire game.Although using game theory to analyze Konane suggests that with enough analysis a winning strategy could be formed, research performed in this area has only focused on 1-dimensional patterns in Konane, and few 2-dimensional sub-game patterns. This form of analysis assigns to each board layout a value indicating which player wins and how many moves ahead the winning player is. This value is actually a sum of the game-theoretic mathematical values assigned to each sub-game.