Anti-Chess Final Report

Overview of Project

In general, I would have to say that our group has worked together remarkably well. We got organized very quickly; by the end of spring break all the major modules had specifications written (and some were partially implemented). Our basic strategy was essentially top-down: we tried to get minimal implementations of all the modules done very quickly, so that we could have a running program which could then be used to do testing, etc. There were several advantages to this. First, writing driver programs is a pain. Second, since the modules are integrated from the start we never experienced any painful "integration phase." Third, progress on the program was very tangible since we could see it evolving before our eyes; new features and bug fixes appeared immediately in the program.

I have to take this opportunity to compliment Patrick and Tim on the fine jobs they've done, not only in writing their own code, but in looking over the other code in the program and helping in the debugging and testing. They've put a lot of work into doing a good job and it shows.

Individual Progress Reports

Steven

Tim

The machine_player cluster has been written, but not tested yet. This is not a problem because the machine_player is completely seperate from the final product that we produced and will be used only for participation in the tournament.

The static_evaluator that my genetic algorithm program produced may not be optimal. There seems to be a bias towards the black palyer. This bias may be inherent in the game, but I suspect it has to do with the way the computer_player budgets its time for each move, or the order in which the chess_board yeilds its pieces. Either way, I think that this bias may have hindered the determination of an optimal static_evaluator. If improvements were to be made in the determination of the computer_strategy, they should definitely be made in the direction of the eliminating the bias, because the current static_evaluator that has resulted from my genetic algorithm plays better than any static_evaluator I've hand created.

Patrick

1. April 9, 1995
   • Patrick: have a functioning user interface completed, which displays the chess board in a window and accepts typed input from the keyboard, but does not support mouse input
   • Patrick: write initial test-shell for user interface module.
   • Status: completed on time.
2. April 15, 1995
   • Patrick: thoroughly test initial user-interface implementation, completing the test-shell program so that it incorporates a full suite of black/glass box tests.
   • Status: completed on time.
3. April 25, 1995 Patrick: modify the user interface to accept mouse input Status: not completed on time. (see below)
4. May 6, 1995
   • Patrick: pretty up the user interface to make it look nice, and add fun and exciting extra features; continue testing
   • Status: this step was combined with the previous step; in other words, the nice features were included as the mouse-based interface was being written. Rather than doing steps 3 and 4 sequentially, they were done together and completed by the step 4 deadline. This was not a problem since a functioning text-based user interface already existed and could be used for testing the other parts of the program.
5. May 13, 1995
   • Patrick: thoroughly test the user interface and make sure there are no obscure bugs
   • Status: completed on time.

Regarding Teleports

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. Finally, I constructed several standard "test boards" containing strange cases to make sure that the program worked, especially in cases involving teleports.

Tim

For the vast majority of the time that I was testing and developing the computer_player and static_evaluator, I inserted several run-time checks into the code so that my program would continually send information to the screen on what was actually going on internally so I wouldn't get any surprises.

Also, whenever possible I compiled with the debug option so that I could take advantage of the tools offered by the debugger. This allowed me to check the values of various variables during run-time and to easily test all the procedures with numerous different hand picked values without writing a full fledged driver for the specific purpose of testing.

Patrick

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
    • 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.
  • Changes Since Last Time
    • Rep. invariant removed: size(r.whites) = size(r.blacks); this was deleted since we were notified that load files with 20 white kings, for example, were valid.
• 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 holds information on the number of nodes on the game tree it has searched up to the current point in the game. reset_state ereases all the previously stored information just as if the computer_player had just been created.
    • make_move: The computer_player uses its static_evaluator to perform a mini-max search of the game tree with alpha-beta pruning. Instead of searching to a set depth, the computer_player searches a set number of nodes per turn (using the calibration information stored in its internal state). Searching a set number of nodes is accomplished by starting with a set number of nodes to be searched and having each parent node distribute the number of nodes to be searched equally among its children. This has the advantage of using the time quota more fully because if a particular level has only a small number of possible moves (say two, for example) then there will theoretically be time left over from not having to search as many nodes as usual. Make_move also calibrates the computer_player's internal state on each move.

      Make_move initially determines a move using a reduced number of nodes and if this search is executed within a specific time boundary, the full search is performed. This is done in order to guard against using up too much time in cases when the alpha-beta method prunes significantly less than the usual number of nodes, or when background processes are slowing down the whole game.

      There are also several short cuts that make_move takes. If there is only one possible move, make_move returns it immediately instead of using a mini-max search to pointlessly assign that move a score. If there are no possible moves, make_move returns the empty move immediately. And the first two moves for white and the first move for black have already been determined and are memoized.

      Make_move distiguishes between different levels by having lower levels search fewer nodes, in addition to the static_evaluators being inherintly different for different 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
    • rep = sequence[int]
    • kingWeight = 1
    • pawnWeight = 2
    • knightWeight = 3
    • rookWeight = 4
    • bishopWeight = 5
    • queenWeight = 6
    • movesPerGame = 7
  • 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. A player's own pieces are subtracted from its score and a player's opponent's pieces are added to its score.
    • 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 }
  • Rep. Invariants
    • size(r) = number of weights (7)
    • each element of r is in the interval [0,100000] except for the move weight which is in the range [1000,75000]
    • the sum of the elements of r is 100,000 (weights are normalized)
  • Algorithms for Some Procedures
    • create_random: Seven numbers are randomly generated and normalized so that they sum to 100,000. Checks are also applied to satisfy the rep invariant.
    • create_mutant: One weight is randomly selected and randomly reassigned. If the selected weight is a piece weight, it is randomly reassigned so that it is within one order of magnitude of all other piece weights, the move weight stays the same (not just relatively), and the piece weights are normalized so that all weights sum to 100,000.
    • 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 multiplied by its weight. If a piece is of the specified color, the weight is subtracted from the score that is eventually returned. If the piece is not of the specified color, the weight is added to the score that is eventually returned.
  • Differences from Initial Design: The static_evaluator is now implimented using integer weights instead of real weights as was originally the case. This change in design was brought about by the consideration that integer arithmetic is faster than real number arithmetic and integer arithmetic avoids floating point errors that result from real number arithmetic. Also, I was originally planning on memoizing the results of static_evaluator$evaluate, but I dropped this idea because the evaluate procedure is very efficient.
• 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, em: event_manager, lp_index: int, stuff: array[window_item]]
  • 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. r.em is the event_manager used to supplement the window cluster's event capabilities. r.lp_index is the line number of the last long process status message displayed. r.stuff is an array of window items that are used to decorate the user interface window but serve no functional purpose.
  • 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
  • Changes since Progress Report:command_waiting eliminated and update_state added, to better handle computer versus computer play. em, lp_index, and stuff added to rep.
• 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
  • Changes since progress report: color_square added so squares can be colored for teleportation
• 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, sbm: maybe_window_item, obm: maybe_window_item, sbm_showing: bool, 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.sbm is the solid bitmap of the piece, r.obm is the outline bitmap of the piece, 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. r.sbm_showing is true if the solid bitmap is being used and false if the outline bitmap is being used.
  • Rep. Invariants
    • 1 <= r.r <= boardSize
    • 1 <= r.c <= boardSize
    • r.sbm & r.obm are valid window items of the window that r.gb exists in
  • Changes since Progress Report: Added color argument to moveto, to support coloring for teleportation. Replaced bm with sbm and obm, and added sbm_showing, so that pieces can be displayed in the right color
• 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, setteleportButton: window_item, teleportoffButton: window_item, x: pixel, y: pixel, pauseable: bool, tele: bool]
  • Abstraction Function
    • A typical graphic_game_commands has a lot of buttons, and it exists at some coordinates in some window. The exact buttons displayed depend upon whether the game can be paused, whether the game is paused (assuming it can be), and whether teleportation is in effect. r.pause is true if the game is paused and false otherwise. r.pausable is true if the game can be paused and false otherwise. t.tele is true if teleportation is in effect 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
  • Changes since Progress Report: added set_pauseable, get_pauseable, set_tele, get_tele procedures. added setteleportButton, teleportoffButton, pauseable, and tele to rep.
• 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, items: array[window_item], message: sequence[string], ourmessage: sequence[string]]

      totallines = 5

  • 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 items the message is displayed in are r.items. The padded, truncated version of the message being displayed is r.ourmessage.
  • Rep. Invariants
    • w.item is an array with lower bound 1 containing totallines text items of r.w that contain the text r.ourmessage.
    • r.ourmessage always has a size of totallines
  • Spec changes since progress report: get_message and set_message work with sequences of strings instead of strings
  • Rep changes since progress report: item renamed as items and changed to array[window_item]; message changed from string to array[string], to support multiple line messages; ourmessage added, so that both processed and unprocessed copies of message can be kept
• 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_with_pieces
  • 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, teleport: teleportState, doing_teleport: bool]
  • 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. r.teleport is the teleport state of the graphic_board_with_pieces. r.doing_teleport is true if and only if the graphic_board_with_pieces is doing recursion to handle a teleport.
  • Rep. Invariants
    • all ints in r.locations are >= 0 and < boardSize*boardSize
    • r.gf1 and r.gf2 exist on r.gb
  • Spec changes since progress report: reset_state, set_teleport, get_teleport, get_onesquare, width, and height procedures added
  • Rep changes since progress report: teleport and doing_teleport added, to support teleportation