Main Doc Page

Contents:
    So what is Quoridor, anyway?
    Common Elements of the Three Versions
    Original Lisp Implementation
    First Version C++Implementation
    Second Version C++ Implementation

So what is Quoridor, anyway?

I am so glad that you asked that. Quoridor is a board-game (similar to checkers, minus the checkers, and with some other, extra things). It is played on an 8 x 8 checkered game board. (That's why it's similar to checkers.) It is a two-player game, and each player spends his or her moments of game-playing glory moving his or her token around on the game board. The goal of both players is to reach the opposite side of the board, and the first one to reach his or her goal wins. The white token begins at the bottom of the board, and attempts to move upward- the black token begins at the top, and tries to move down.

So how do you play this game, anyway?

During one turn, a player may do one of two things: move his or her token, or place a wall. (We'll get to the wall-placing bit in just a minute.) Tokens may move horizontally or vertically, one square at a time. (This part isn't like checkers. No moving diagonally.)

So what about that wall-placing bit, anyway?

Each player starts a standard game with nine walls. A player may place a wall by simply clicking on the place he or she wishes to put the wall. Each wall may be placed on the gameboard in one of two ways: horizontally or vertically. A vertical wall blocks two rows, and a horizontal wall blocks two columns. Walls may not overlap one another in the middle. Once a player is out of walls, tough cookies. He or she may not place any more walls.

So how do I play Quoridor on a Computer, anyway?

This particular implementation is played with the mouse. It's not terribly difficult. To move a token, click on the square to which you want to move the token. To place a wall, click on the place where you want the wall. Horizontal walls will fall where you click and to the right, and vertical walls will fall where you click and up.

Here- look at this picture to the right. In order for the playing pieces (the two tokens and the two walls) to be in the positions shown, a player must have clicked on each of the places indicated by a red dot. For the horizontal wall, the player clicked in the space between the squares where he or she wanted the wall, and the wall blocks that column and the one to the right. For the vertical wall, the wall blocks the row where the player clicked, and the one directly above. (Note: these dots are not in the real game. They are shown here for demonstration purposes only.) You can click in the area where potential walls intersect- but I can't promise which wall will show up! Clicking anywhere between two squares places a wall, and clicking anywhere within a square moves a token- if it is a valid move. (Once in awhile you may attempt a move, and nothing will happen. Don't panic. Just try it again. Sometimes you're one pixel off, and the game doesn't sense your click, and sometimes it just doesn't register. So try again.)

There are two boxes of walls to the right of the board (one is shown to the right of this explanation); these contain each player's remaining walls. The box on the bottom holds the white token's walls, the box on the top holds the black token's walls. When your box is empty- you can't place any more walls!

The game will flash messages at you, telling you whose turn it is, whether or not you attempted an invalid move, or who won. One last note: the white token always moves first, regardless of who is playing which token.

So how do I start a game, anyway?

In order to start a game, drop down the "Game" menu and select an option. (Was that vague enough? I'm trying to account for lots of versions, so I don't have to change this web page every time I compile. :-) In a standard game, the white token is "player 1" and the black token is "player 2". As it says above, the menu changes quite regularly, so experiment with what your version has!

So I found a big bug, what do I do, anyway?

First of all, don't tell my professor! Just kidding. If you would, please provide a detailed description of the game situation that caused the bug (a screenshot or two would be nice) and email it to

moquist

majen

net

. If you wouldn't do that, then at least complain bitterly to everyone around you. Everyone involved will appreciate this immensely.

Common Elements of the Three Versions

So what are these common elements, anyway?

As one could probably guess, three different versions of the same game, by the same programmer, and all stemming from the same source are very likely to have some things in common. The game representation has been constant throughout the life of this program. (Matt Mastroine and I went through a few different ideas as we developed the first version, but the representation has been constant since then.) The token positions are stored as four variables, which simply contain their (x,y) coordinates (p1x, p1y, p2x, p2y). The walls are stored in two seperate arrays: vwalls and hwalls. (Betcha'd never guess which array holds which walls...) The vwalls array holds the vertical walls, and the hwalls array holds the horizontal walls.

(Note: Because of the way Lisp prints out arrays, Matt and I used a weird coordinate system- it's like taking the Cartesian plane and rotating it clockwise 90 degrees, and then using the (relocated) first quadrant. The axes do not change. The x-axis is now vertical, and the y-axis is horizontal, and they both begin in the upper-left corner of the gameboard. You get used to it after a while.)

Other common variables include:

start-game- which is set to true when a game is initialized, and set to false when a game is finished. If it's false, no one is allowed to move. This stops a player from moving around after a game has been won.
human1 & human2- which is true for each player that is a human, and false for each player that the computer is playing.
turn- which stores whose turn it is. This is used all over the place, to determine whose turn it is. (Oh, the cleverness of me!) (That was sarcasm.)
pwent- which is true if it is a player's turn, and that player has already gone. That's how the program knows when it's time to let the other player have a turn.
current-wall- which holds an integer, which is inserted into the wall arrays to represent walls placements. It is increased after each wall placement, to aid in differentiating between walls... Here's why. Because a wall blocks two rows or columns, you can't know which rows or columns belong to which wall, unless each wall has different numbers storing its value...
nump1walls & nump2walls- which hold the number of walls that each player has remaining.
path-keeper- which contains the array storing a player's path to his or her goal
path-keeper-2- which contains the array storing a player's BEST path to his or her goal

Original Lisp Implementation

So how is this one different from the others, anyway?

In both this program, and the first version of the C++ implementation (the direct port version...(;-), all of the variables described in the Common Elements section are global, along with the following:

valid-wall- which contains 1 if a valid wall has been found, and 0 if no valid wall was found.

xbest & ybest- which contain the coordinates of the best move (wall or token) for the player.

xtest & ytest- which contain the coordinates of the potential move (wall or token) currently being tested for the player.

piece- which contains the character ('m' for "move token" or 'h' or 'v' for a horizontal or vertical wall) denoting which type of move the player should make.

valid- which contains the array storing the valid moves for a player.

This AI player was advanced enough to win in our class tournament, but is easily beatable by a human. The game operates on 16 functions altogether (They are listed below, with links to the code.), but the foundation of the AI is our path-finding system of functions, which consists of num-moves, find-recursive-path, find-best-path, and happy-trail.

So how do these functions work, anyway?

    find-recursive-path isn't truly recursive, the name is part of its legacy of recursion. It is now an iterative imitation of recursion which uses stacks. Basically, it starts from a given starting position and finds a path to the goal, by trying each of the four directions from each square into which it moves. As it moves, it keeps track of its progress by placing markers in path-keeper. If it reaches a dead end, it "recurses" back until it finds a square from which all four directions have not been tried. As it moves through path-keeper, it calls happy-trail, passing to it the current position.
    happy-trail marks all the squares around the passed-in position to point to that position. When a path has been found, then, find-best-path is called to analyze the path-keeper left by find-recursive-path.
    find-best-path follows the trail left by find-recursive-path and happy-trail, storing its progress in path-keeper-2. It then returns the number of moves in the path.
    num-moves returns the number of moves for a player to reach his or her goal, by using find-recursive-path, find-best-path, and happy-trail. validate-move is called to generate the valid (moves) array, and each of these positions is then passed into find-recursive-path and find-best-path in order to determine which valid starting move results in the smallest number of moves in the path.
    The final piece of our AI was the put-wall function. This function places the most advantageous blocking wall, unless the player can place no walls. If no wall can be placed, the calling AI function moves its token instead.

    (The functionality of the directly ported C++ implementation is *gasp* exactly the same (up to this point)- so click here to jump to that section of this page.)

    These "tools" are utilized by two AI functions. Pay careful attention, so that you catch these names: ai1 and ai2. The comments provided at these functions themselves are just as detailed as any documentation that I would include here. Follow the links to see these marvellous comments.

So, I want more code-level specifics. Where is the code, anyway?

The full code is here: quoridor-lisp.cl, or you can pick which function in the full code you would like to view, below.

Functions:

initialize()
game-play()
clickedon(piece x y)
decide()
ai1()
ai2()
validate-move(x y who)
validate-wall(piece x y)
check-path(xtry ytry who)
find-best-path(xtry ytry who)
find-recursive-path(xtry ytry who right ox oy)
happy-trail(path-keeper xtry ytry)
num-moves(player)
put-wall()
refresh-board(piece x y)
setpics()

First Version C++ Implementation (Direct port from Lisp)

So how is this one different from the others, anyway?

In both this program, and the original Lisp implementation, all of the variables described in the Common Elements section are global. The commented declarations of these variables (and any ones specific to this implementation) are here.
The functionality of the game is *gasp again* exactly the same as the original Lisp implementation- so click here to look at a high-level description, on the Lisp side. Click on one of the links below to view an entire file or a specific function within its file.

Full Code Files

quoridora.h
quoridora.cpp
list.h
list.cpp

Functions:

Clicked(TImage *inImg, char piece, int x, int y);
RepaintPSquare(TImage *inImg, char state);
RepaintWall (TImage *inWall, bool show);
ResetBoard();
Initialize();
ValidateMove(int x, int y, int turn);
ValidateWall(char piece, int x, int y);
RepaintPSquareXY(int x, int y, char state);
RepaintWallXY(char piece, int x, int y);
PrintWalls(char piece);
GamePlay();
Decide();
AI1();
PutWall(int origMeMoves, int origNotMeMoves);
FindBestPath(int xTry, int yTry, int who);
NumMoves(int who);
CheckPath(int xTry, int yTry, int who);
FindPath(int xTry, int yTry, int who, bool right, int ox, int oy);
HappyTrail(int pathKeeper[][8], int hWalls[][8], int vWalls[][7], int xTry, int yTry);
DisplayRemainingWalls(int who);
DisplayRemainingWallsXY(int who, int which, bool show);
GetUndoInfo(int p1x, int p1y, int p2x, int p2y, int hWalls[][8], int vWalls[][7], int turn, int numP1Walls, int numP2Walls);
DoUndo(int &p1x, int &p1y, int &p2x, int &p2y, int hWalls[][8], int vWalls[][7], int &turn, int &numP1Walls, int &numP2Walls, int &pWent);
Dialog(int messageType);

Second Version C++ Implementation (Improved)

Full Code Files

quoridorb.h
quoridorb.cpp
stack.h
stack.cpp

Functions:

Initialize(Gamestate &inGame);
AI1(Gamestate &inGame);
TryWalls(Gamestate inGame, int howFar);
CanBlockAll(Gamestate inGame, Stack <Movestruct> &goodWalls);
CanBlockAll(Gamestate inGame, Stack <Movestruct> &goodWalls, Movestruct &blockingWall);
GamePlay(Gamestate &inGame);
ApplyMove(Gamestate &inGame);
ValidateMove(Gamestate &inGame, Movestruct move, int player);
ValidateWall(Gamestate inGame, Movestruct wall);
CheckPath(Gamestate inGame, int player);
NumMoves(Gamestate &inGame, int player);
NumMoves(Gamestate &inGame, Stack <Pathstruct> &pathStack, int player);
FindBestPath(Gamestate &inGame, Stack <Pathstruct> &pathStack, int xTry, int yTry, int player, int currentBest);
FindPath(Gamestate &inGame, int xTry, int yTry, int player, bool right, bool up, int ox, int oy);
HappyTrail(Pathstruct &pathKeeper, int hWalls[][8], int vWalls[][7], int xTry, int yTry);
FindWalls(Gamestate &inGame, Pathstruct inpath, Stack <Movestruct> &testWalls, int player);
TestWalls(Gamestate inGame, Stack <Movestruct> &testWalls, Stack <Movestruct> &goodWalls, int advantage);
UntilLastWall(Gamestate inGame, Stack <Movestruct> &goodWalls, Movestruct &bestWall, int player);
RemoveDumbPaths(Stack <Pathstruct> &pathStack);
Dialog(Gamestate &inGame, int messageType);
DisplayRemainingWalls(Gamestate inGame, int player);
GetUndoInfo(Gamestate realGame);
GetRedoInfo(Gamestate realGame);
DoUndo(Gamestate &inGame);
DoRedo(Gamestate &inGame);
PrintPath(Pathstruct inPath);
PrintWalls(int inArray[][8], char piece);