Principles of Operating Systems

Part 1: Tic-Tac-Toe (40% of Project 2 Grade)

In part 1 of this assignment, you will be implementing a kernel module that can be used to play against the user in a game of tic-tac-toe. This module will implement a virtual character device (with a corresponding entry in /dev that the user can open a file descriptor to), which will be interacted with by the user using normal file read and write operations. The module will work on the principle that the user opens a file descriptor to the module's /dev entry (which shall be named /dev/tictactoe), writes commands to that file descriptor with the write() system call, and reads the responses to those commands with the read() system call. To this end, the module must keep track of the state of the game board, implement logic to read and parse commands, check the validity of any commands, and check if the game is over (either in the case that one player wins or there is a draw). Your module must be named tictactoe.ko once it is compiled.

A minimal solution to this project does not have to implement any sort of AI to determine what move to make when it is the computer's turn. It may simply choose a random valid move.

The set of commands that your module must support the user supplying from user-space, as well as the expected responses are described below. Each command consists of a two-digit command code followed by any arguments that are required for the command, and ends with a newline ('\n') character. Please note that you should always check the data sent in by the user for validity!

Your code may make the assumption that no more than one command is ever present in one write to your module and that if a write does not end in a newline character that it is invalid. Additionally, if multiple writes to your device occur without an intervening read, you shall return only the most recent response when a read does come in.

• 00 X/O — Begin a new game. Resets the game board to the initial state. Takes one argument specifying whether the user wishes to play as "X" (who goes first) or "O" (who goes second). Responds with "OK\n".
• 01 — Returns the current state of the game board. Takes no arguments. Responds with the current state of the game board as a string of nine characters followed by a newline. Each character represents one square of the game board and shall contain an 'X', 'O', or a '*' character (for a space that has not been occupied yet). Spaces shall be listed starting with the top row (starting from the left), then the middle row, then the bottom row.
• 02 X Y — Specifies a move for the player. X and Y shall be numbers between 0 and 2 representing the column and row that the player wishes to choose for their turn. Responds with "OK\n" if the move specified by the player is valid (and the user has not won), "WIN\n" if the move specified by the player is valid and the player has won by making that move, "TIE\n" if the move specified by the player is valid and the game has ended in a tie, "ILLMOVE\n" if the move specified by the player is not valid (for instance if there is already a mark in the specified square or an invalid coordinate is specified), "OOT\n" if the user is attempting to move outside of their turn, or "NOGAME\n" if the game has not been started or is otherwise over. If you believe that there are other error cases that we have not described above, please document them in your README file for this part of the project (error codes shall be textual strings that end with a newline character and contain no more than 8 characters before the newline). In the case of any error condition, the state of the game should not be changed in any way. It shall still be the user's turn if it was their turn and no marks on the board shall change.
• 03 — Asks the computer to make a move. Responds with one of the responses documented above for the 02 command, as appropriate (however, the "ILLMOVE\n" error shall never be returned from this command — the computer shall never attempt to make an illegal move). This command takes no arguments.

Any illegal commands shall respond with "UNKCMD\n". Improperly formatted commands shall respond with "INVFMT\n". If you wish to add additional error codes not covered here, document them in your README. All error codes must end with a newline character and be no more than 8 characters long (not counting the newline).

Commands must match the input and output described above exactly to be considered valid. It is not valid to change the output of the 01 command to return the data in a pictorial representation, for instance — this would be something that should be handled in a user-space program that interacts with your character device. If the input to your character device does not match exactly the format described above, then you shall return an invalid format error.

If you wish to add any additional commands to this list (for debugging purposes, for instance), the command code used must be two digits long and must start with a number greater than or equal to 7. Please document any extra commands you add in your README. Note: You must not make any additional commands required to be called in a normal playthrough of the game — our testcases will not call any such extra commands.

The board shall be oriented such that coordinate (0, 0) corresponds to the upper left corner of the board and such that coordinate (2, 2) corresponds to the lower right corner of the board, as shown in this diagram (which matches the description given for the 01 command):

 (0, 0) | (1, 0) | (2, 0)
--------------------------
 (0, 1) | (1, 1) | (2, 1)
--------------------------
 (0, 2) | (1, 2) | (2, 2)

Your submission for this part of the assignment must include a Makefile that can be used to build your kernel module. All source code for your module and the Makefile to build it must be in a subdirectory of your repository called "module". If you build any test programs for this portion of the project (and you are highly encouraged to do so), you shall place them in a subdirectory of your repository called "test" and include a Makefile to build them with. You shall also document what the test program(s) you created test in your README file. If you write your own driver program, we encourage you to include that in your repository as well in a directory called "driver".

As an example of how this works, please refer to the following example. Lines that start with > are written to the device with write(), whereas lines that start with < are read from the device with read(). Each line below ends with a single newline character (and the greater/less than signs are not included as a part of the data — they are only there for illustrative purposes).

>00 X
<OK
>01
<*********
>02 1 1
<OK
>02 0 0
<OOT
>01
<****X****
>03
<OK
>01
<O***X****
>02 0 0
<ILLMOVE
>03
<OOT
>02 1 0
<OK
>03
<OK
>01
<OX*OX****
>02 1 2
<WIN
>03
<NOGAME
>O1
<OX*OX**X*
>00
<INVFMT
>01
<OX*OX**X*
>00 O
<OK
>02 0 0
<OOT

Required Documentation

You must include a README file in the root of your repository for this part of the assignment, documenting anything that you feel that it would be useful to tell us as a part of grading the assignment, as well as any references outside of the course materials that you may have used in the development of this assignment.

Program to interact with the module

In order to qualify for any extra credit, you must make a reasonable attempt to complete all of the required portions of the assignment (including those in part 2). If you do not complete any portion of the assignment, including required documentation, you will not qualify for any extra credit you attempt! Extra credit on this assignment is not designed to help you make up for not attempting parts of the assignment that may be more difficult.

Any extra credit earned on this project will be applied toward the grade you receive on the assignment. That is to say, it is possible to earn more than a 100% on this assignment.

For part 1 of the project, there are three tasks that you can undertake in order to earn extra credit. Each of these tasks is worth 3% of your project grade, with an extra 1% if you attempt all three. The three tasks you can do to earn extra credit are detailed below (you may attempt them in any order you see fit).

1. Implement some form of artificial intelligence in your computer player for the game. For instance, if the computer sees that the human player has two marks in a row, it should place a mark to block the human from getting three in a row, if possible. In addition, it should make sensible moves that lead toward the goal of winning the game.
2. Allow for multiple file descriptors to be opened to the kernel module, each one representing a separate game state. That is to say that if there are five different programs open on your machine, each with a file descriptor open to the module, then each one should represent its own game in progress. Moves from one game should not affect any other games (obviously).
3. Allow for two "human" players to play against each other using the module. To this end, you will need to add two new commands to the module, described below:
   • 04 — Creates a two human-player game and initializes the game board. Player 1 will be X and Player 2 will be O. Player 1 will continue to specify their moves by way of the 02 command from above. Replies with "OK\n" on success. This command takes no arguments.
   • 05 X Y — Performs a move for Player 2. Otherwise works the same as the 02 command above.

You may work on extra credit for Part 1 of the project after Part 1 is due. If you choose to do so, please make another directory in your repository called "module-ec" to continue your work there. DO NOT CHANGE YOUR "module" DIRECTORY OR ANY FILES IN IT AFTER YOU HAVE SUBMITTED PART 1 OF THE ASSIGNMENT OR IT WILL BE MARKED AS LATE. Also, do not allow work on the extra credit to distract you from completing Part 2 of the project.

Part 2: Chess (60% of Project 2 Grade)

In part 2 of this assignment, you will be implementing a kernel module that can be used to play against the user in a game of chess. Once again, this will be implemented by way of a virtual device driver that the user can read/write with commands, much like in part 1 (except the device's entry shall be /dev/chess). The kernel module shall be compiled to a file named chess.ko.

A minimal solution to this part of the project need not implement any sort of complex AI for determining the CPU's move — you may randomly select a piece and then randomly make any valid move for that piece when a CPU move is requested. However, you must ensure that the CPU does not attempt to make any invalid moves (i.e, ones that move pieces incorrectly or ones that place their king in check).

Required Design Document

You will be required to include a design document along with your kernel module for part 2 of the project, describing in detail your choices for any data structures used, determining if moves are valid, determining if either the player or CPU is in check, and determining if a checkmate has occurred. In addition, if any extra credit is attempted, it must be fully described in the design document as well. This design document is a significant portion of your grade on this part of the assignment — 1/3 of your Part 2 grade (20% of the total grade on this project).

While we are not prescribing any particular template to be used for your design document, we do expect it to be of a significant length. We expect that your design document will consist of at least 4 double-spaced pages with 12 point fonts (Helvetica, Times, Arial, or Times New Roman), 1 inch margins, and Letter sized pages. You may include diagrams as needed, but any diagrams do not count toward your page count (nor do title pages, tables of contents, bibliographies, code segments from your project, etc). Your design document must be a PDF file named "design.pdf" and be in the root directory of your project2-part2 repository.

We expect that the design document would be sufficient for a relatively proficient kernel programmer (who knows how to play chess) to recreate your kernel module without consulting with your code, especially in the areas of how you checked the validity of moves, checked if either player is in check after a move, and determined which moves the CPU would make.

Move Notation

There are many different forms of notation for recording moves in the game of chess, each of which has its own pros and cons. To ensure that moves can be notated in a descript, yet compact form, we are requiring the following format for moves to be notated in your assignment (for sending player moves into the module).

A move shall be notated starting with a two-letter abbreviation of the piece that is being moved. White pieces shall start with a 'W' character, while black pieces shall start with a 'B'. After the color designation shall appear an abbreviation of the piece's rank: 'K' for king, 'Q' for queen, 'B' for bishop, 'N' for knight, 'R' for rook, and 'P' for pawn. After the piece abbreviation shall be the piece's location before the move as a two character position (columns are labeled a through h from left to right and rows are labeled 1 through 8 from bottom (where the white player's pieces start the game) to top (where the black player's pieces start the game), per the normal conventions of the game of chess. After the starting location of the piece, there shall be a hyphen ('-') character, followed by the location that the piece is moved to (in the same format as the starting location above). If any of the opponent's pieces are captured by the move, then an 'x' character shall be appended after the ending location, followed by the two-character abbreviation of the piece that was captured. There are two exceptions to this format for two special moves that are allowed. Support for these moves (castling and the en passant capture) is part of the extra credit for this part of the project, and will be described in the extra credit section.

Here are a few examples of moves that could be seen in a normal game (not necessarily in the same game):

• WPe2-e4 - White moves the king's pawn from its starting position to the space two spaces forward
• BNb8-c6xWP - Black moves the queen's knight from its starting position to the space c6, capturing a white pawn
• WPe4-f5xBB - White moves pawn from e4 to f5, capturing a black bishop

If a pawn reaches the other side of the board without being captured, it is promoted to a piece of the player's choosing. The pawn may be promoted to any piece of the same player's color, other than a pawn or king, even if this would mean there are more of a piece on the board than is allowed at the start of the game. This shall be notated in the move by appending a 'y' character, followed by the two letter abbreviation of the piece that the pawn is being promoted to. Below are a few examples:

• WPf7-f8yWQ - White pawn moves from f7 to f8 and is promoted to a queen
• WPf7-g8xBNyWB - White pawn moves from f7 to g8, capturing a black knight and being promoted to a bishop

Board Notation

When a user-space program requests the layout of the board from the module, it will reply with two characters for each square of the game board in row order. The two characters shall be the abbreviation of the piece that occupies that square (from the move notation above), or '**' for an unoccupied square of the board. The first two characters shall be for square a1, followed by b1, c1, d1, e1, f1, g1, h1, a2, and so on until you reach square h8.

Commands

The set of commands that the user-space program will use to interact with your kernel module is described below. As with Part 1 of this assignment, a valid command will end with a newline character.

Your code may make the assumption that no more than one command is ever present in one write to your module and that if a write does not end in a newline character that it is invalid. Additionally, if multiple writes to your device occur without an intervening read, you shall return only the most recent response when a read does come in.

• 00 W/B — Begin a new game. Resets the game board to the initial state. Takes one argument specifying whether the user wishes to play as white (who goes first) or black (who goes second), abbreviated with a capital W or B respectively. Responds with "OK\n".
• 01 — Responds with the current state of the game board, according to the format described above, followed by a newline character. If no game has been started, responds with "NOGAME\n".
• 02 MOVE — Specifies a move for the player, with MOVE being a string in the format described in the move notation format above (the word MOVE will not appear anywhere in a valid command). Responds with one of the following:
  • "ILLMOVE\n" — the move specified is illegal for any reason.
  • "OOT\n" — the player has attempted a move out of turn.
  • "NOGAME\n" — there is not currently an active game in progress.
  • "CHECK\n" — the move has resulted in the opponent being in check.
  • "MATE\n" — the move has resulted in the opponent being in checkmate (that is to say, the player has won the game).
  • "OK\n" — the move is valid, but has not resulted in a check or checkmate situation.
• 03 — Requests the CPU to make a move. Responds with one of the responses documented above for the 02 command (other than "ILLMOVE\n", as the CPU is not allowed to attempt to make any illegal moves).
• 04 — Resigns the game, declaring the CPU player the winner. Responds with "OK\n" unless some other error condition would otherwise apply (such as "INVFMT\n", "MATE\n", "NOGAME\n", or "OOT\n").

As with Part 1 of this assignment, any illegal commands shall respond with "UNKCMD\n" and any improperly formatted commands shall respond with "INVFMT\n". Once again, if you wish to add additional error codes not covered here, document them in your README, subject to the same requirements in Part 1 (no more than 8 characters and ending in a newline).

If you wish to add any additional commands to this list (for debugging purposes, for instance), the command code used must be two digits long and must start with a number greater than or equal to 7. Please document any such commands in your README. As with Part 1, you must not require any such commands to be called in a normal playthrough as our test programs will not call any such commands.

Repository Layout

Your submission for this part of the project must include a Makefile that can be used to build your kernel module. All source code for your module and the Makefile used to build it must be in a subdirectory of your project2-part2 repository called "module". If you build any test programs for this portion of the project and wish to share them with us, you must place them in a subdirectory of your repository called "test" and include a Makefile to build them. You shall also document what these test programs do in your README file. Any driver program that you might write that you wish to share with us shall go in a directory called "driver" in your repository.

Program to interact with the module

Extra Credit

Like with Part 1 of this project, extra credit cannot be used to make up for any part of the project that is not attempted. The extra credit for this part of the project can add up to 30% on top of your project grade. Each piece of the extra credit is worth a different amount, which is noted with each option. Some parts of the extra credit may require you to complete other parts of the extra credit to qualify, so please pay careful attention to the requirements listed below. If you attempt multiple parts of the extra credit, you must ensure that all of the parts you attempt work together properly.

As this is extra credit, the TAs and instructors will not answer any technical questions about it. Clarification questions are fine, but we will not help you implement the extra credit in any way. Do not ask.

If you attempt any part of the extra credit, you must document it in your design document for part 2 in full and you must also document it in your README. Failure to document your extra credit in both the design document and your README will forfeit any points that you may have otherwise earned for it.

To complete this option, you must allow for two human players, like in the extra credit for Part 1. To do this, once again, you will be adding a few new commands, as described below:

• 05 — begin a two-player game with two human players. Previous commands documented above (02 and 04 will be used for player 1 (the player who uses the white pieces) and the alternative commands below (06 and 07) will be used for player 2 (the player who uses the black pieces). This command is used in-place of the 00 command if two human players are playing. Responds with "OK\n" on successful completion.
• 06 MOVE — specifies a move for player 2, following the same format as command 02 above. If the game is a single player game this command shall reply with a reply of "ILLCMD\n" to inform the program that it is illegal to use this command (with a small exception for another part of the extra credit).
• 07 — resigns the game for player 2, following the same format as the 04 command above. If this command is used in a single player game, it shall reply with "ILLCMD\n".

To complete this portion of the extra credit, you must allow for multiple open file descriptors to the /dev/chess module to each represent their own game. That is to say if there are five different programs on your VM each opening a file descriptor to /dev/chess then there can be five different games in progress. Moves from one game should not affect any other games.

To complete this portion of the extra credit, you must implement an additional command to serialize the entire playthrough of a game. This means that the command will open a file and write out to that file the exact commands that have been used (successfully) to mutate the game board to the state it is in when the request is made. As the normal 03 command does not capture the moves made by the AI player, the 06 command from the first part of this extra credit must be used to represent any AI moves (this is the exception mentioned above). In addition, there will be another command added to load the state of the game from a file written by this command. To do this, you must store every move made in every game and keep track of the ordering of those moves. Your save files will consist of only the following commands: 00, 02, 04, 05, 06, and 07 (this means it is possible to save a game that has been completed, such as one that ended with a player resigning). Each line of the file should be terminated by a newline character. To implement this functionality, you must add two new commands to your program to serialize and deserialize game state:

• 08 filename — saves the game state to the specified filename on the filesystem. The file should be created if it does not exist and shall be overwritten in its entirety if it does exist. If the file is created, it shall be owned by the same user id as the calling process and must be at least readable/writable by that user. Responds with "OK\n" on success or "FILEERR\n" on any errors in creating/writing to the file. Does not change the state of the game in any way — you must allow this command to be called and then for the game to continue on afterwards. The filename given shall be an absolute path (you may return an appropriate error if the filename given does not begin with a /).
• 09 filename — loads the game state from the specified filename on the filesystem. Responds with "OK\n" on success, "FILEERR\n" on any errors in opening/reading the file, or "PARSEERR\n" on any errors in parsing the file. You may leave the system in an indeterminate state if any errors occur while parsing the file. The filename given shall be an absolute path (you may return an appropriate error if the filename given does not begin with a /).

To complete this portion of the extra credit, you must implement detection for a stalemate condition in the game of chess. A stalemate condition is one where one of the players is not in check but has no legal move to make when it is time to take their turn. This results in a tie game being declared. To this end, you must modify the handlers for any commmands that are used for taking a turn (02, 03, and 06) to check if the next player has a valid move to make. If not, these commands shall reply to their corresponding read() with "TIE\n" to represent that the game has ended in a stalemate.

Submission Instructions

The submission of this project follows the same procedure that you used for Homework 1, rather than that of project 0 and project 1. That is to say that you will use the git init command to create a blank repository in a directory, add files to the repository with git add, commit them to your local repository with git commit, set the remote location with git remote add, and push changes up to your GitHub repository with git push. You are not required to make any tags on your repositories for this project (unlike HW1). You will follow the same process for part 2 that you do for part 1 of this assignment, with the repository created for that part.

You should also verify that your changes are reflected in the GitHub repository by viewing your repository in your web browser.

References

Below is a list of references that you may find useful in your quest to complete this project: