CPSC 415 - Artificial Intelligence - Fall 2023

Program #3 — Adversarial search

Possible experience: up to +50XP (or possibly even +60XP or, incredibly, +70XP)

Due: Tuesday, Oct. 31st, midnight

Overview

This program concerns one of the most time-honored applications of AI: playing fully-observable, deterministic, multi-agent, zero-sum games (specifically, chess). You will be writing an automated chess 'bot that uses the minimax algorithm and/or other logic to compete against yourself, my test scripts, and other players.

Supporting classes

The files chess_model.py, chess_config.py, chess_player.py, chess_view.py, main_chess.py, and chess_piece.py in the class's github repo have a few Python classes you'll need to know about.

The Board class (chess_model.py)

A Board object represents the state of a chess board. In true Pythonic style, it is itself a dictionary that maps locations (in chess notation) to Piece objects; i.e., if you have an object "my_board", you can say "my_board['c5']" to get the Piece object that is currently on space c5. (Third column from left, fifth row from bottom.) You can also use ".items()" in the usual way to iterate through it.

Here are the legal operations you may use on a Board object:

1. Read-only dictionary operations such as [], .get(), .items(), and the "in" operator.
2. Calling "deepcopy()" on a Board (from the "copy" module) to clone it.
3. .get_all_available_legal_moves(color) takes a string as an argument (lowercase 'black' or 'white') and returns a list of 2-tuples of strings, each containing an original square and a destination square, in chess notation. For instance, the return value might be:

   [('a1','a2'), ('a1','b1'), ('e4','e2'), ('d4','d7')]
   

   which would indicate four possible moves for the player in question, the first of which is to move the piece in the lower-right corner up one square. All of these moves are guaranteed to be legal to play.
4. .make_move(original_location, new_location) to actually make a move on this chess board. Important: do not call this to experiment (look ahead) with hypothetical moves. (Use deepcopy() to do that, and experiment with your cloned board; see above.) This method raises an exception if you attempt to move illegally.
5. .get_king_location(color) to find the chess notation for the square on which the king of the given color rests.
6. .is_king_in_check(color) to find out whether a player is in check on this board.
7. .is_king_in_checkmate(color) to find out whether a player is in checkmate on this board.

Anything else is considered cheating, and will result in public flogging.

The Piece class (chess_piece.py)

Piece objects represent individual pieces on the board. The only thing you should ever have to do to a Piece object is call .get_notation() to get the chess notation for its piece type (e.g., "R" for a white rook, or "n" for a black knight.)

The ChessPlayer class (chess_player.py)

If you wanna be a playa, you'll need to create a subclass of the ChessPlayer class (see below).

Your mission

Your job is to create a Python class called yourUmwId_ChessPlayer, which inherits from ChessPlayer, an abstract base class. It should be in a file called yourUmwId_ChessPlayer.py. Its first few lines should look like this:

from chess_player import ChessPlayer

class jsmith3_ChessPlayer(ChessPlayer):

    def __init__(self, board, color):
        super().__init__(board, color)

    def get_move(self, your_remaining_time, opp_remaining_time, prog_stuff):
        # YOUR MIND-BOGGLING CODE GOES HERE

Notice that a Board object is given to your ChessPlayer class as an argument to the constructor, is passed up to the superclass's constructor for safekeeping, and is stored in an instance variable ("self.board") that is accessible whenever your player feels the need to examine it. You may also access self.color to find out which color your player is (the string 'black' or 'white' will be returned).

The only meaningful method of your class (besides any helper methods you may want to create) is .get_move(), described here in some detail. The purpose of the method is to return a tuple describing your chosen move. The tuples are the same as described in the return value for .get_all_available_legal_moves(color), above. In fact, you could write a completely random chess player with this line of code:

    def get_move(self, your_remaining_time, opp_remaining_time, prog_stuff):
        return random.choice(self.board.get_all_available_legal_moves(self.color))

and this has in fact been provided for you in the file Random_ChessPlayer.py, which you can pit your agent (or yourself) against.

The other arguments to .get_move(), all completely optional, are as follows:

• your_remaining_time — The number of seconds left on your chess clock. If this ever reaches zero, life will suck since the simulator will thereafter ignore your agent entirely and make random moves for you instead. It will be hard not to lose if this happens, unless it also happens around the same time to your opponent. Your chess clock will start at 600 seconds (10 minutes), although I reserve the right to increase this value for the tournament.
• opp_remaining_time — Same as above, but for your opponent.
• prog_stuff — This argument, should you care to use it, gives you access to the progress bar status & text at the bottom of the screen when your agent runs. It's a useful alternative to debug messages so you can see in a prettier way how your agent is progressing. See the Using the Progress Bar section below for details on how to use it.

Again, all three of these extra arguments are completely optional. The most fundamental piece of information your .get_move() method will need is the Board object itself, accessible via self.board.

Getting started

Get the fresh version of the class repo by doing a git pull. Make sure you can run the simulator in player-vs-player mode by typing:

$ python3 main_chess.py

and drag/dropping pieces. Also make sure you can quit and restart the simulator and run it in player-vs-computer mode with the Random player provided, and in computer-vs-computer mode.

When you get bored of this, create your player class, in a file named exactly as above, and give it the random player implementation suggested. Make sure it shows up in the menu for the computer players and that you can run it. Then check your fledgling player class into your repo via git commit.

You are now ready to begin thinking. No matter what other bells and whistles you eventually toss into your pot of soup, the core of your algorithm is going to be minimax, so take a deep breath and think about how to implement that.

Rules

Board sizes

In addition to the standard 8×8 board, the simulation supports other configurations (via JSON files in the chess_configs directory). For tournament play (see below), I will be using the mini (6×6) board so things run faster. Any of them can be chosen from the left-hand menu on startup.

Crazy mode

The simulation can operate in two modes: regular mode (in which case the positions of the pieces are specified in the JSON file in chess_configs) or "crazy mode." In crazy mode, all the pieces behind the pawns are chosen randomly from the possible pieces, with two exceptions: (1) there will always be exactly one King per side, and (2) the piece configurations of the two sides will be mirror images of each other across the board, so that neither side has an advantage. For tournament play, I will in fact be using crazy mode. It can be enabled via the checkbox at startup, or with "crazy=True" or "crazy=False" as the final command-line argument to main_chess.py.

Pieces

All the standard chess pieces move in their standard ways. There are also three others my kids and I made up:

The Princess — like the Queen, the Princess can move in any direction (including diagonally), but at most three squares at a time. She is hence a limited-range Queen. The chess notation for the princess is "S" (or "s").

The Fool — like the Knight, the Fool can jump over other pieces. It doesn't move in a knight's hook, though; it simply moves exactly two spaces in any direction. The chess notation for the fool is "F" (or "f").

The Disintegration Ray — like the Queen, the Disintegration Ray can move in any direction (including diagonally). However, if it makes a capture, it is exchanged for a pawn. This might seem a detriment, but used cleverly the Ray can get you a quick pawn promotion. The chess notation for the disintegration ray is "Y" (or "y").

Misc

All the other rules of the game are as in standard chess, except the following:

1. If you advance a pawn to the last rank, it is automatically promoted to a queen. There is no other choice.
2. There is no such thing as an en passant pawn capture. You simply can't do it, sorry.
3. Unlike in real chess, it is legal to castle "through" check. In other words, if all the spaces between your king and rook are empty, and neither your king nor rook have ever moved, and your king is not currently in check, you are free to castle even though some of the squares in between the king and rook may be under attack from the other side. (This comes up only rarely.)
4. Drawn (tied) games are not detected in all the ways they can actually occur in real chess. My simulation only declares a draw when "stalemate" occurs: this is when your king is not in check but you have no legal moves. There are other kinds of draws in chess, including reaching the same position three different times, having fifty moves pass without a capture or a pawn move, or when there aren't enough pieces of the right type to get a checkmate no matter how hard you try. In practice, I'm going to terminate the game after a large number of moves (maybe 500) and declare a draw that way.

Using the Progress Bar (optional)

While your agent is thinking about its next move, you can put status messages on the screen and control the progress bar. Here's how:

The prog_stuff argument given to your .get_move() method has two components: prog_stuff.bar and prog_stuff.text.

Any time you want to put text in the status bar, write:

    prog_stuff.text.set('The text I want to appear')

The progress bar widget, like all progress bars, has a (numeric) maximum size as well as a number indicating how far along its progress is. To set its maximum size, in whatever units you wish, type:

    prog_stuff.bar.config(maximum=theMaximumNumber)

Then, to update its current value so that it progresses rightwards as your algorithm makes progress:

    prog_stuff.bar.value.set(someNumberLessThanTheMaximumNumber)
    prog_stuff.bar.update_idletasks()

Throwdown

On Thursday, Nov. 2nd, we'll have a bracket-style single-elimination chess tournament on the big screen. Best of five games will determine each pairing's winner, with players alternating the black and white pieces for each game. This contest will take place on the 6×6 board in crazy mode. The winner and runner-up will obtain valuable prizes (see below).

Grading

If your agent can consistently beat my random player (provided with the simulation code), it will earn at least +30XP.

If your agent can consistently beat my pretty sucky attempt at an actual thinking player (not provided), it will earn at least +50XP.

The runner-up in the Nov. 2 Chess Challenge will earn +60XP. The grand prize winner will earn a whopping +70XP, plus a year's supply reasonable amount of Swedish Fish, plus a valuable trophy not available in stores.

Finally, if your agent can beat Magnus Carlsen in a best-of-7 match under actual live tournament conditions, you will earn +10,000XP and a lifetime's supply of Norwegian Fish.

Turning it in

You will turn this assignment in by attaching your properly-named ChessPlayer Python file to an email with subject line "CPSC 415 Program #3 turnin". For an additional +1XP, include in the body of the email the name of your own original chess piece and a description of how it would work.

Getting help

Come to office hours, or send me email with subject line "CPSC 415 Program #3 help!!"