Anti-Chess Progress Report

Overview of Progress

The computer_player is not in its final form, but it is functional as set forth by the schedule. The main additions that are left to be made before the May 1st deadline are a distinction between skill levels and a strategy for dealing with the time limit. The program for determining an optimal static_evaluator was finished a day late due to some unanticipated bugs in the static_evaluator and chess_board clusters. However, a program that searches for an optimal static_evaluator using a genetic algorithm is now complete and is currently running. At last check, the algorithm had gone through 1,363 generations. The results from this run will be fed into future runs using enhanced computer_player's.The machine_player cluster is already written, but remains to be debugged by the May 6th deadline.

Two preliminary versions of the user interface (an all-text version and a text/window hybrid) have all ready been written and are fully functional. User interface will not be adapted to accept mouse input by Tuesday. Probably won't be ready until this weekend. The three reasons for this are: Patrick has too much work in his other classes, Patrick underestimated the amount of time it would take to write the user interface, and Patrick has hurt his fingers typing. Otherwise, things are on schedule. Blackbox tests have already been written and run for most of the clusters that have already been written. No known bugs or expected problems.

Validation Strategies

Steven

In order to test the chess_board data structure, I initially simply used the main program, which causes invocations to all of its functions. This is because it is difficult to verify that the correct moves have been made, etc., except by eye, looking at the output of the program. However, it has been possible to automate a series of tests by saving a sequence of commands in a text file and pasting them into the terminal window. In addition, the operation of the computer_player algorithm exercises the functions of chess_board in a very vigorous way, making thousands of different moves as it looks ahead into the future. This process would be more certain to cause errors to appear, if the code were buggy, than any small sample of test cases possibly could.

Tim

Also, I've been compiling everything with the debug option until it becomes neccessary to compile it with the optimize option for speed. The debugging environment allows me to test each procedure individually without having to insert many compile-time-checks.

In the future when everything appears to be running smoothly, I plan to use automated testing to ensure that everything is in fact running smoothly.

Patrick

The first technique is to avoid making errors in the first place. This is the best method but is not always possible.

The second technique is blackbox testing. For each cluster of the user interface, a blackbox test program will be written which tests all of the operations of that cluster.

The third technique is glassbox testing. For particularly tricky parts where blackbox testing alone may be insufficient to find all errors, a glassbox test will be written to test the code based on the particular internals of the code.

The fourth testing method is to play with the final program and make sure it behaves as expected.

Implementation Overview

• chess_board
  • Overview: chess_board is a mutable data type which represents a chess board for anti-chess. It keeps track of the location of all the pieces, checks for the legality of the moves, and provides the capability to undo moves. It also has some utility procedures which are of use to computer strategy algorithms.
  • Representation
    • rep = record[pieceList: ap, board: bm, nmoves: int]
    • ap = array[piece]
    • piece = record[kind: pieceKind, color: pieceColor, taken: bool,location: boardPt, id: int]
    • boardPt = record[row,col: int]
    • ai = array[int]
    • bm = array[ai]
  • Abstraction Function
    • A typical chess_board is a set of 4-tuples representing the pieces that are currently on the board: <kind of piece, color, row, col> where kind of piece is king, queen, etcetera, color is black or white, and row and col range from 1 to 8.
    • The abstraction function A(r) is the set, for all p:piece in elements(r.pieceList) with p.taken = false, of the n-tuples <p.kind, p.color, p.location.row, p.location.col>. Recall from chess_board.equ that p.kind is a oneof record whose elements are king, queen, etcetera, and that p.color is either whitePiece or blackPiece.
  • Rep. Invariants
    • size(r.whites) = size(r.blacks)
    • for all i in indices of rep.pieceList, rep.pieceList[i].id = i
    • all elements of rep.pieceList are unique
    • for any piece p in rep.pieceList, p.location.row and p.location.col are in [1, boardSize]
    • all non-taken elements are at unique boardPt's
    • r.board is a boardSize x boardSize matrix
    • for any piece p in r.pieceList, r.board[p.location.row][p.location.col] = p.id
    • for entries in r.board which are not specified by the previous condition, that r.board[i][j] = -1
    • r.nmoves = number of calls to make_move - number of calls to undo_move which have been made since the board was created.
    • If the board is parsed from a string, then starts at 1 or 2 rather than 0 if exactly 1 or at least 2 moves have been made, respectively.
• computer_player
  • Overview
    • computer_player is a mutable data type representing a computer anti-chess player. Given the state of an anti-chess game, it is able to propose an "intelligent" move. The related machine_player data structure is implemented as a wrapper around this data structure and the chess_board data structure.
    • We use this, rather than machine_player, for two reasons. First, since the arbiter can pass our computer_player the chess_board data structure, we don't have to keep a redundant copy of all that information (as we would have to with machine_player). Second, machine_player requires you to pass information to it in a human-readable format, which is silly, and it breaks down the abstraction barrier between the strategy and interface modules.
  • Representation
    • rep = record[opts: options, name: string, evaluator: static_evaluator]
  • Abstraction Function
    • A typical computer_player is an n-tuple containing opts (of type options) which describe the computer_player's options, a name for the computer_player (of type string), and a static_evaluator which the computer_player uses in the determination of a strategy. Opts is a struct containing the level (type int) which describes the level of skill with which the computer_player plays and "iswhite" which is a boolean flag which indicates the color of the computer_player.
    • The abstraction function A(r) = <[r.opts.level, r.opts.iswhite], r.name, r.evaluator>
  • Rep. Invariants
    • 1 <= r.opts.level <= 7
  • Algorithms for Some Procedures
    • create: Most of this procedure's implementation is obvious. However, a clarification of how the options passed to it are used is needed. Specifically, the level determines what type of static_evaluator the computer_player gets (lower levels mean sub-optimal static_evaluators), and how far ahead it looks to determine its next move.
    • reset_state: The computer_player currently holds no state and reset_state therefore doesn't do anything at this point.
    • make_move: The computer_player uses its static_evaluator to perform a mini-max search of the game tree with alpha-beta pruning. Currently there is no distinction between different skill levels of computer_players, but once there is a distinction make_move will perform a deeper search for higher skill levels (in addition to the static_evaluators being inherently different at different skill levels).
• static_evaluator
  • Overview
    • static_evaluator is an immutable data type which is used by computer_player to determine an anti-chess strategy. The essential feature of the static_evaluator is that, given a chess_board, it can return a real number describing how "good" that board is for a player whose pieces are a given color. This number is only a heuristic result, but it can be used to build a more sophisticated algorithm.
    • This data structure also contains operations to aid in a genetic-algorithm optimization of an anti-chess strategy, allowing static evaluators to be randomly generated, "mated," and "mutated".
  • Representation
    • sr = sequence[real]
    • ptbl = p_table[chess_board, real]
    • rep = record[the_weights: sr, memo: ptbl]
    • kingWeight = 1
    • pawnWeight = 2
    • knightWeight = 3
    • rookWeight = 4
    • bishopWeight = 5
    • queenWeight = 6
    • rowWeight = 7
    • colWeight = 8
  • Abstraction Function
    • A typical static evaluator is a set of weights for various quantities about the chess board. For example, there is a weight for the number of pawns on the board. To evaluate a chess board, the weights of the weighted pieces are multiplied by the quantity of that type of piece and summed, the absolute difference between the average column for white and the average column for black is multiplied by its weight and added to this quantity, and the absolute difference between the average row for white and the average row for black is multiplied by it's weight and added to the quantity. The memo portion of the record is used for memoization.
    • The abstraction function A(r) = { elements of sequence r are the weights whose associated quantities are described by the equate for that index of r; e.g. r[kingWeight] is the weight for the number of kings on the board, and r[rowWeight] is the weight for the absolute difference between the average rows of white and black. }
  • Rep. Invariants
    • size(r) = number of weights (8)
    • each element of r is in the interval [0,1]
    • the sum of the elements of r is 1 (weights are normalized)
    • ptbl$lookup(r.memo, board: chess_board) = static_evaluator$evaluate(r.the_weights)
  • Algorithms for Some Procedures
    • create_random: Eight numbers in the range [0, 1] are generated and normalized so they sum to 1, and the normalized numbers are used as the weights of the static_evaluator.
    • create_mutant: One weight is randomly selected, and changed by a factor of x where x is in the range [0, 2]. The weights are then summed and normalized to 1.
    • mate: Returns a static_evaluator who's weights are the arithmetic average of the corresponding weights from the two given static_evaluators.
    • evaluate: Returns the sum of the quantity of a particular piece type on the board multiplied by its weight, the absolute difference between the average row for white and the average row for black multiplied by its weight, and the absolute difference of the average column for white and the average column for black multiplied by its weight.
• machine_player
  • Overview
    • A machine player is a mutable data type reflecting the state and strategy of a player in a game of antichess. It is basically used as a wrapper around the computer_player cluster and chess_board clusters.
  • Representation
    • rep = record[player: computer_player, bd: chess_board]
  • Abstraction Function
    • A typical machine player is a pair containing a player (type computer_player), and a bd (type chess_board). The player is used to determine a playing strategy, and the board (bd) is the most current state of the board that the machine_player has knowledge of.
    • The abstraction function is A(r) = <player, bd>
  • Rep. Invariants
    • The internal state of player is up to date with bd. i.e., computer_player$opponent_moved is called after the opponent moves, or computer_player$reset_state has been called.
• user_interface
  • Overview
    • user_interface is a data structure which encapsulates the user interface for chess/antichess. It handles only the *interface* for displaying the board, making moves, etcetera and doesn't make any decisions of its own...it is called by the arbiter.
  • Representation
    • rep = record[w: window, gbp: graphic_board_with_pieces, white: graphic_player, black: graphic_player, gcmds: graphic_game_commands, tcmds: graphic_text_commands status: graphic_status_line, long_process: bool]
  • Abstraction Function
    • A typical user_interface is a window which displays a chess board with pieces on it, as well as a bunch of buttons and stuff so the user can issue commands. r.w is the window. r.gbp is the graphical chess board with pieces. r.white and r.black are the parts of the window that have buttons for sending player-specific commands. r.gcmds is the part of the window that has buttons for general commands, and r. tcmds is the part of the window where the user can type textual commands. r.status is the part of the window where messages are displayed. r.long_process indicates whether a "long process" message is currently being displayed.
  • Rep. Invariants
    • r.gpb, r.white, r.black r.gcmds, r.tcmds, and r.status are all in r.w
    • r.white has a pieceColor of whitePiece, and r.black has a pieceColor of blackPiece
• graphic_board
  • Overview
    • a graphic_board is a visible, immutable object. It is a pattern of black and white squares displayed in a window.
  • Representation
    • rep = record[w: window, squares: array[window_item], size: square_size, x: int, y: int]
  • Abstraction Function
    • A typical graphic_board exists in a window at some location and is made up of many rectangles which are small, medium, or large. r.w is the window it exists in. r.x and r.y are the coordinates of the upper left corner of the graphic_board in that window. r.squares is an array of the rectangles. r.size indicates whether the rectangles are small, medium, or large.
  • Rep. Invariants
    • r.squares.size = boardSize*boardSize
    • each r.squares[i] is a valid window_item of r.w
• graphic_piece
  • Overview
    • a graphic_piece is a visible, mutable object. It is a chess piece which is located on a graphic_board.
  • Representation
    • rep = record[gb: graphic_board, bm: window_item, r: int, c:int, pc: pieceColor, pk: pieceKind]
  • Abstraction Function
    • A typical graphic_piece is a bitmap of a piece of some color and some kind which is displayed in some square on a graphic_board. r.gb is the graphic board, r.bm is the bitmap, and r.r and r.c are the row and column of the square where it is located. r.pc is the color of the piece and r.pk is the kind of the piece
  • Rep. Invariants
    • 1 <= r.r <= boardSize
    • 1 <= r.c <= boardSize
    • r.bm is a valid window item of the window that r.gb exists in.
• graphic_player
  • Overview
    • a graphic_player is a visible, mutable object. It is a an area of a window that displays information about a player and contains buttons that represent commands that can act upon the player.
  • Representation
    • rep = record[w: window, x: pixel, y: pixel, pc: pieceColor, ps: player_state, box: window_item, pieceIcon: window_item, playerIcon: window_item, playerName: window_item, time: window_item, current: bool, nameButton: window_item, timeButton: window_item, computerButton: window_item, humanButton: window_item, levelButton: window_item]
  • Abstraction Function
    • A typical graphic_player exists in a window at some coordinates and represents a player of some color which has some state. It has a box to display player information in. It has icons for the player and the player's piece color. It displays the player's name and time. The player may or may not be current. The graphic_player also has command buttons to act upon the player. r.w is the window the graphic player is in. The upper left corner is at (r.x, r.y) within the window. The player is of color r.pc and has state r.ps, and is current if and only if r.current is true. r.box is the window item for the information box. r.pieceIcon is the window item for the piece color bitmap, and r.playerIcon is the window item for the player bitmap. r.playerName is the text item that displays the player's name, and r.time is the text item that displays the player's time. The remaining items of r are the button items for the command buttons.
  • Rep. Invariants
    • r.box, r.pieceIcon, r.playerIcon, r.playerName, r.time, r.nameButton, r.timeButton, r.computerButton, r.humanButton, and r.levelButton are all window items of r.w
• graphic_game_commands
  • Overview
    • a graphic_game_commands is a visible, mutable object. It is an area of a window that contains buttons that represent commands that can act upon the game as a whole.
  • Representation
    • rep = record[pause: bool, loadButton: window_item, saveButton: window_item, pauseButton: window_item, unpauseButton: window_item, stepButton: window_item, newButton: window_item, quitButton: window_item, w:window, x: pixel, y: pixel]
  • Abstraction Function
    • A typical graphic_game_commands is either paused or not, and it has a lot of buttons, and it exists at some coordinates in some window. r.pause is true if the game is paused and false otherwise. r.w is the window the graphic_game_commands exists in. r.x and r.y are the coordinates it exists at in that window. The other members of r are the various buttons that do commands.
  • Rep. Invariants
    • all the window_items are buttons in r.w
• graphic_status_line
  • Overview
    • a graphic_status_line is a visible, mutable object. It is an area of a window that displays a line of text
  • Representation
    • rep = record[w: window, x: pixel, y: pixel, item: window_item, message: string]
  • Abstraction Function
    • Abstraction Function: A typical graphic_status_line is displayed at some coordinates in some window. It displays some message using a text item. r.w is the window. The upper left corner of the graphic_status_line is at (r.x, r.y) in that window. The message displayed is r.message, and the window item the message is displayed in is r.item.
  • Rep. Invariants
    • w.item is a text item in r.w that contains the text r.message
• graphic_text_commands
  • Overview
    • a graphic_text_commands is a visible, immutable object. It is an area of a window that contains a text box where the user can type in textual commands.
  • Representation
    • rep = record[w: window, x: pixel, y: pixel, prompt: window_item, textbox: window_item]
  • Abstraction Function
    • A typical graphic_text_commands is displayed at some coordinates in some window. It displays a prompt for the user to enter text commands, and it has a text box the user can enter the commands into. r.w is the window. (r.x, r.y) is the coordinates of its upper left corner in that window. r.prompt is the text item that displays the prompt, and r.textbox is the typein item.
  • Rep. Invariants
    • r.prompt is a text item of r.w
    • r.textbox is a typein item of r.w
• graphic_frame
  • Overview
    • a graphic_frame is a a visible, mutable object. It is something which can be displayed on top of a graphic_board to highlight a particular square.
  • Representation
    • rep = record[gb: graphic_board, displayed: bool, r: int, c: int, top: window_item, right: window_item, bottom: window_item, left: window_item]
  • Abstraction Function
    • A typical graphic_frame exists on some graphic_board and is either displayed on a particular square or is hidden. It is composed of four bitmaps that make up the four sides of the frame. r.gb is the graphic_board. The graphic_frame is displayed if and only if r.displayed is true, and if it is displayed then r.r and r.c are the row and column where it is displayed. r.top, r.right, r.bottom, and r.left are the bitmap items that make up the frame.
  • Rep. Invariants
    • 1 <= r <= boardSize
    • 1 <= c <= boardSize
    • r.top, r.right, r.bottom, and r.left are bitmap items of r.gb.w
• graphic_board
  • Overview
    • a graphic_board with pieces is a visible, mutable object. It is an abstraction that represents a chess board and the pieces on it.
  • Representation
    • rep = record[gb: graphic_board, locations: p_table[int, graphic_piece], gf1: graphic_frame, gf2: graphic_frame, mousedown: bool, onesquare: bool, move: movedata]
  • Abstraction Function
    • A typical graphic_board_with_pieces is a container for a graphic_board, a bunch of graphic_pieces, and a couple of graphic_frames. It also contains state about a move currently being made by the user. r.gb is the graphical chess board, and r.locations is a p_table of all of the pieces and their locations. r.gf1 is the graphic_frame used to highlight the first square of a move, and r.gf2 is the graphic_frame used to highlight the destination square of a move. r.mousedown is true if and only if a mouse press event has been received more recently than a mouse release event. r.onesquare is true if and only if the first square of a move has been chosen but the second square has not. r.move contains the information about the move being made.
  • Rep. Invariants
    • all ints in r.locations are >= 0 and < boardSize*boardSize
    • r.gf1 and r.gf2 exist on r.gb