PROBLEM.	2
PSEUDO-CODE/ALGORITHMIC REPRESENTATION.	2
LEVEL 0:	2
LEVEL 1:	2
Section 1: Gameplay.	2
1.1.1: User Input.	2
1.1.2: Winning.	3
1.1.3: Takes.	3
1.1.3: Switch.	3
Section 2: Defensive AI.	3
1.2.1: Check for User Win.	3
1.2.2: Check for User Take.	3
Section 3:  Offensive AI.	4
1.3.1:  Check for computer Win.	4
1.3.3:  Strategy Line.	4
Section 4:  Miscellaneous AI.	4
1.4:  Make Move.	4
LEVEL 2:	4
Section 1:  Classes, Member Functions and Global Variables.	4
Section 2:  Algorithms.	5
2.2.1:  GetMove()	5
2.2.2:  CheckWin()	5
2.2.3:  D_Check4Win()	7
2.2.4:  CreateStrat()	8
2.2.5:  D_Check4Take()	8
2.2.6:  MakeMove()	9
SAMPLE OUTPUT.	11
AREAS OF IMPROVEMENT.	11
USER DOCUMENTATION.	12
REQUIREMENTS.	12
INSTALLATION.	12
HOW TO PLAY THE GAME.	12


Pente AI:
Internationl Baccalaureate Higher-Level Computer Project.
Problem.
To create a program, written in C++, that would recreate playing the traditional board game of Pente with sufficient Artificial Intelligence to challengers of beginner to intermediate skill.
	The way to go about board games with artificial intelligence is to loop through all the places on the board, and to prioritize each and every cell.  The computer should then move the position with the highest number.  Prioritization is computed by applying a series of rules - in Pente, such rules would be:  Possible to win?  Possible to take a piece?  Need to block a user win?  Need to block a user take?  Need to build along this line?
	To solve this problem, Pente was created using an object - with the two primary data structures (the game board and the priority board) listed in the PRIVATE section of the object.
Pseudo-code/Algorithmic Representation.
Level 0:












Level 1:

Section 1: Gameplay.

1.1.1: USER INPUT.
	The member function 'GetMove' gets the user input as a string and converts it into numerical data that the program can use.  It uses strings to make it more robust - the user can enter any of the following:



INPUT
VALID/INVALID.
2
Valid.
2a
Invalid - Letters not allowed
23
Invalid - Outside range
Quit
Valid.1


The program uses ASCII codes to convert the strings into numbers.  It checks for NULL to check whether the number is a two digit number or not.  The code uses the int() function to get the ASCII code, and based on the fact that 0 is 48 in ASCII.

1.1.2: WINNING.
The program uses two variables, up and down, to set boundaries around the current point the computer is checking for.  The computer uses a loop to decrement up from 5 to 0, whilst incrementing down from 0 to 5.  Nested within this loop, is a loop that counts the number of pieces within it.  If the number of pieces equals 5, then someone has won.  This loop is repeated four times, with small modifications to each to check for the different areas -- vertical, horizontal, diagonal SW to NE, diagonal NW to SE.

1.1.3: TAKES.
	The 'Check4Take' simply is a list of 'if-then' statements hard-coded into the program.  The one procedure is flexible enough to check for computer takes and user takes, and increment the necessary variable to keep track of how many pairs each has taken.  It does this by using two variables 'who' and 'notwho' that is set to either 1 or 2 (for Player 1, or Player 2).  The variables are set at the beginning of the procedure and the subsequent 'if-then' statement comprise of: 

	if (Board[row+2][col] == who ....&& Board[row][col] == notwho)
	
The Piecestaken array is updated using the 'who' variable to increment the relevant player.

1.1.3: SWITCH.
	Simply switch the players.  It regulates whose turn it is - computer or player.

Section 2: Defensive AI.

1.2.1: CHECK FOR USER WIN.
	This procedure checks for a potential user win.  It checks first whether the user has 4 within a group of 5 cells.  If it finds one, then it immediately blocks it, thus preventing the move.2  If no 4 are found the same, the procedure then proceeds to loop back through the users pieces to try to find 3 in a row, it tries to block the user from expanding on those 3.

1.2.2: CHECK FOR USER TAKE.
	This procedure attempts to predict, and counter, a potential user take.  A diagram best illustrates this - imagine the board layout was as follows (The numbers are reference points in the explanation):

[   ][   ][ 1 ][   ][   ]
[   ][ 0 ][ X ][ 2 ][ 3 ]
[   ][   ][   ][   ][   ]

	The computer would move to #1 in a situation like this.  If it moved to #2, the player would likely move to #3, thus taking the computer's pieces.  The reason it moves to #1 is described further in Section 4.##.  Note that the decrement in priority increases as the number of computer pieces that has been taken increases.  For example, the program would decrement by a smaller amount if the user had taken only 1 pair, and it would definitely prevent the move if it meant the computer would lose the game (the user has taken 4 computer pairs already).
	This procedure also blocks a potential take.  Thus, if the board looks like this:

[  ][ O ][ X ][ X ][ ? ]

The computer will move to ?, so that the player cannot take the pieces.

Section 3:  Offensive AI.

1.3.1:  CHECK FOR COMPUTER WIN.
	This is the highest priority move.  If it is found possible, the program will move.  It uses the same algorithm but on a simpler level to the defensive version.  It only checks for 4 pieces in a row.

1.3.3:  STRATEGY LINE.
	The computer creates a strategy line when deciding where to move.  This means that the computer finds the line that the computer has its most pieces and automatically increases the priority of moving to one of those places.  It creates a new strategy line each time instead of remembering, because it will naturally choose the same line again if needed, yet if the user has moved in such a way that inhibits the computer from using the 'strategy line' any further it will pick a new one.
	Once a 'Strategy Line' has been created, it further prioritizes the cells to in accordance to the most vulnerable areas.  For example, if a cell on the 'strategy line' is surrounded by two others, the computer will fill there first. 

Section 4:  Miscellaneous AI.

1.4:  MAKE MOVE.
	This member function loops through all pieces to try to find the one with the highest priority.  If it cannot find one, it proceeds to loop through all computer cells, and prioritizes the pieces around them.  It gives greater priority to those pieces in the vertical or horizontal to the computer piece.
	If the program still can't find a good area to move to (all pieces are wiped out), then the program starts in the centre, and works its way outwards, until it finds a blank space, and moves there.  Starting from the centre is a lot more natural than starting from the top-left of the board.

Level 2:

Section 1:  Classes, Member Functions and Global Variables.
Following is a list of the member functions and the global variables of the Pente class:
#include <iostream.h>

class Pente {

	public:
	  void Display();
	  void Getmove();
       Pente();
  void CheckTake();				
	  void CheckWin();				
	  void Switch();
	  int  gamewin;
	  int  who;						
	  int  want_to_quit;			
  void ClearStrat();
  void Check4Take();
  void Check4Win();
  void CreateStrat();
  void MakeMove();
  void D_Check4Take();
  void D_Check4Win();
private:
	  int Board[29][29];			
	  int row;						
	  int col;					 	
	  int computer;					
	  int player;					
	  int piecestaken[3];   	
  int StratBd[29][29];
	};
 
The algorithms of the following functions will be reviewed in-depth:  Getmove(),  CheckWin(), D_Check4Win(), CreateStrat(), D_Check4Take(), and MakeMove().
Section 2:  Algorithms.

2.2.1:  GETMOVE()
In order to provide robustness, the program uses strings to gain input, then converts the string to integers.  The program allows up to 80 characters to be entered for either column or row numbers - thus, for the user to crash the program, he must be attempting to crash it.
To convert from character to integer, the following formula was used:

Translated into C++, this code can be written as follows:
row = (int(rowstr[0])-48);

Note:  Rowstr is the array of characters used to get input from the user.
A problem, though, arises when a two-digit number is entered.  A way is needed to determine whether a one-digit or two-digit number has been entered.  This is done by checking where the NULL character exists.  A NULL character in C++ is represented as '\0'.  Thus, the program checks whether the second character is not null:
if (rowstr[1] != '\0')	
If is isn't then it knows that a two-digit number has been entered.  It takes the first character, converts it as shown above, and multiplies it by 10.  It then takes the second character converts it and adds it.  This is all done on one line:
	  row = ((int(rowstr[0])-48)*10)+(int(rowstr[1])-48);
		If the second character is a NULL then simply convert as shown above:
	else
	  row = (int(rowstr[0])-48);

2.2.2:  CHECKWIN()
	The next three functions are very similar with small differences.  This section will cover the basic principles of CheckWin(), Check4Win(), and CreateStrat().
	When checking for a win you must loop through all cells, then check every 5-cell combination in the 8 directions.  To do this I use two variables up and down that get decremented and incremented consecutively that determine how far up/left and down/right to search.  Up plus down always equals 5.
In the image below, the first row shows the range that computer checks on the first loop of the do statement, and the second row shows the second iteration.  Note:  In the first iteration up equals 4 and down equals 0.  In the second iteration, up equals 3 and down equals 1.

The following algorithm would have to be used:

This procedure checks for the win along a row.  Converted into C++ code, the following algorithm would look like:
do									
{
  for(int i=row-up;i<=row+down;i++)
    {
      if (Board[row][i] == who)
        pieces = pieces + 1;
    }
  if (pieces == 5)
    won = 1;
  else
    pieces = 0;
  up--;			// Decrement.
  down++;		// Increment.
}
while (up >= 0 && won==0);

Note:  This procedure is used to check for both computer wins and player wins.  Thus, at the beginning of the procedure, the variable who is set according to the player that the function should check for.
Checking Diagonals:
Checking for Diagonal wins is a little more complicated.  Since both coordinates change, another variable must be introduced.  Here is the modified pseudo-algorithm:

This algorithm would check for a win going from the NW to the SE.  Here is it's C++ counterpart:
do
{
  int tempcol=col-up;
  for(int i=row-up;i<=row+down;i++)
    {
      if (Board[i][tempcol] == who)
        pieces = pieces + 1;
      tempcol++;
    }
  if (pieces == 5)
    won = 1;
  else
    pieces = 0;
  up--;		
  down++;		
}

2.2.3:  D_CHECK4WIN()
There are a few differences between this procedure and CheckWin().  Firstly, the procedure has to loop through the entire board - it doesn't check just the one point.  Secondly, it must store the places where the zeros exist.  Lastly, it must further prioritize the points to decide where it should move to.
Looping is done through 3 FOR statements.  The first decrements the number of pieces that qualify for a potential 'win' from 4 to 3 after one iteration.  The other two loop through the row and column.
A two-dimensional array of 5 by 2 cells is used to store the zeros.  The dimensions allow both x and y coordinates to be held for 5 positions (although only two will ever be used for the AI purposes).  Every time a zero is found, the relevant variables are stored in the array and the array index is incremented.  This is shown in the following code:
	      if (Board[i][tempd_col] == 0)
	        {
			  zeros[zindex][0] = i;
			  zeros[zindex][1] = tempd_col;
			  zindex++;
	        }
	If a potential win is found the computer must decide which zero to move to (if the potential win contains only 3 player pieces).  It does this by counting the number of pieces surrounding the cells in the zeros array.

In C++ code:
for(int z_int=0;z_int<=1;z_int++){
    zerox = zeros[z_int][0];			
    zeroy = zeros[z_int][1];
 for(int z_row=zerox-1;z_row<=zerox+1;z_row++){
 for(int z_col=zeroy-1;z_col<=zeroy+1;z_col++){  
        if (Board[z_row][z_col] == player)
pieces = pieces + 1;
      }}
StratBd[zerox][zeroy] = StratBd[zerox][zeroy] + pieces + 500;
pieces = 0;
}

2.2.4:  CREATESTRAT()
	CreateStrat() creates the strategy line.  The difference is that the Strategy Board is incremented in five different places, not just the one.  CreateStrat() adds 5 to the Strategy Board, then adds up to an additional 2 if surrounded by pieces.  In C++ code, this is:
for (int ii=crow-up;ii<=crow+down;ii++)
	{
 if (Board[crow][ii] != computer)
  {
	   StratBd[ii][ccol] = StratBd[ii][ccol] + 5;
		int surround=0
	   if (Board[crow][ii-1] == computer) surround = surround + 1;
	   if (Board[crow][ii+1] == computer) surround = surround + 1;
	  }
}

2.2.5:  D_CHECK4TAKE()
	The program should be able to predict if a move makes the computer vulnerable to a capture, and also able to counteract a move by the player that puts the computer in a vulnerable position.  Both these are handled by D_Check4Take().
Predicting:  The prediction is simply a series of IF-Then Statements that let the computer check whether it should move there.  For example, the first statements reads:
if ((Board[i][j-2]==player && Board[i][j-1]==computer) || (Board[i][j-1]==player && Board[i][j+1]==computer))
     StratBd[i][j] = StratBd[i][j] - amount;

The procedure is looping through the rows and columns and prioritizing each cell according to these statements.  Here i = row, and j = col.  Thus, the above code enables the computer to check for the following:
 J                        J
[ O ][ X ][  ][  ]     or     [ O ][  ][ X ][  ]

The program will not move to J in either of the above cases because the player can move to the far right place and take the pieces.  Note: amount is set according to how many pieces have already been taken.  The computer might still move to that place if it is favourable for other reasons and only 1 computer pair has been captured - the computer will not move if 4 pairs have been captured, and moving there is a matter of winning or losing.
Blocking Potential:  The blocking 'algorithm' is also simply a list of IF-Then statements - for example:
if (Board[crow][ccol-3]==player && Board[crow][ccol-1]==computer && Board[crow][ccol-2]==computer)
    StratBd[crow][ccol] = StratBd[crow][ccol] + amount;

This example would check for the following:
[ O ][ X ][ X ][  ]

The program would move to the far right piece to block the player taking the computer pieces.
2.2.6:  MAKEMOVE()
	This program actually makes the move for the computer after the artificial intelligence has created the priority board.  The program at first merely loops through the board and tries to find the highest number.  Upon finding a high piece it stores the x and y coordinates of the piece.  Here is the C++ code:
for(int i=5;i<=23;i++)
{
  for(int j=5;j<=23;j++)
  {
    if(StratBd[i][j] > highest && Board[i][j] == 0)
      {
        highrow = i;
        highcol = j;
        highest = StratBd[i][j];
      }
  }
}

Yet, especially during the first 10 moves of the game, there is no favourable place to move to.  The computer has to move thus it first loops through all zero pieces, counts the number of computer pieces around the cell and adds it to the corresponding priority board cell.3  The computer favours pieces that are either on the horizontal or the vertical and increments the number of pieces by one again if that is the case.
Finally, if the computer still cannot find a place (for example, when all pieces are wiped out), the program will start in the centre and search outwards for a blank space, and move there.  The pseudocode for such an algorithm was as follows:

Here is a picture that shows the area of cells covered after one and two iterations:

The first iteration, the centre is checked (represented by the grey dot).  After the boundary variable is increased, the program checks 9 spaces - from top left to bottom right.  Here is the C++ Code:
for(TLBR=0;TLBR<=9;TLBR++){  if (found == 1) break;
   for(i=14-TLBR;i<=TLBR;i++){  if (found == 1) break;
   for(j=14-TLBR;j<=TLBR;j++){  if (found == 1) break;
     if(Board[i][j] == 0 && StratBd[i][j] == 0)
         found = 1;
   }
   }
   }
   highrow = i;
   highcol = j;
  }

The first piece it comes across, that is free, it will move to.  If it still cannot find a piece, the computer assumes that the board is full and calls a stalemate.


Sample Output.
Creating meaningful output from a game is hard to produce.  Sample output with be displayed as an example of each of the main procedures.  For example, there will be output showing the computer blocking a take, or winning, taking etc.  Finally, one entire game will be shown.
Note: All output is not typed in, but is 'copy and pasted' using Windows 95's Mark/Copy function in DOS windows.
3.1:  GETMOVE()

PIECES:  Player 1: 0  Player 2: 0.
Player 2's turn...
Row: Bad input
Col: 5
A problem has occurred!  Please re-enter move.
Row: 9999
Col: 1
A problem has occurred!  Please re-enter move.

The user enters in a string of characters, instead of numbers, and the computer asks the user to re-enter his/her move.  The user then enters in a number above (or below) the board coordinates - again the user is asked to re-enter the move.
3.2:  CHECKWIN() AND CREATESTRAT
The output here is a clipped section of the board.  In order not to complicate things, the user lets the computer win, so that only five moves are needed.
	 9  10
 6 [ ][ ]
 7 [ ][ ]
 8 [ ][ ]
 9 [ ] *
10  o  *

	 9  10  
 6 [ ][ ]
 7 [ ][ ]
 8 [ ] *
 9  o  *
10  o  *
	 9  10  
 6 [ ][ ]
 7 [ ][ ]
 8 [ ] *
 9  o  *
10  o  *

	 9  10  
 6 [ ][ ]
 7 [ ] * 
 8 [ ] *
 9  o  *
10  o  *

	 9  10  
 6 [ ] *
 7 [ ] * 
 8 [ ] *
 9  o  *
10  o  *
The computer won!


Note that from move 3, the player moves out of the field of view, so that computer doesn't try to block the move (which becomes a potential win)4.


Areas of Improvement.
Areas in which the program could expand include the following:
* A Win95 GUI-interface.
* Improved AI.  This includes better prioritization algorithms.
* Undo function.
* Different skill levels.

User Documentation.
Requirements.
Pente AI requires the following computer:
* IBM-compatible 100% processor.  80286 or higher.
* 4Mb or more RAM.
* 1.44Mb floppy disk (for installation).
* 0.5 Mb hard disk space.
* MS-DOS 5.0 or later.*
* CGA-capable (or greater) monitor.
*  Pente AI is fully compatible with Windows 3.1 or Windows 95.
Installation.
To install Pente AI, simply copy the file from the floppy disk to a directory.  This can be done several ways.
DOS:  Type the following commands at the DOS prompt.  Note:  The following commands assume that your floppy disk and the hard disk are specified as a-drive and c-drive consectutively.  Modify the commands if needed.
C:\
md PenteAI
copy a:\penteai.exe c:\penteai\
cd PenteAI
PenteAI

This should create a directory, copy the file to the hard disk, and play the game.
Windows 95:  Click the Start menu, and go to 'Explorer' under the sub-heading 'Programs'.  A window with a list of drives on your computer should show up.  Double click on your hard drive icon.  Go to the 'File' Menu, and select 'New' then 'Folder'.  Type in 'Pente AI'.  Now, double click on the floppy disk icon.  Drag the executable file from the floppy on to the folder you just created.
Creating a Win95 Shortcut: Whilst still in Explorer, select the executable Pente file on your hard disk, and drag it to the desktop.  A shortcut will be created - every time you double click on it, Pente AI will start up.
How to Play the Game.
The rules of Pente are simple.  The game is played on a 19x19 board, and the player and computer take turns alternately.  You can win either by placing five pieces in a row, or by capturing 5 enemy pieces.  Captures occur when the player places a piece adjacent to two pieces of the opponent that have another of the player's pieces in that same line.  A graphical example is needed:

A capture would occur if the player moved to position (4,4), in the bottom right hand corner.  When a capture occurs the opponent's pieces are removed from the board.
PenteAI simply asks for the players move through the keyboard.  Enter the row and column of the place you want to move to and, providing it is a valid move and number, the program moves for you, and plays the computer's piece.
Quitting the game:  To quit the game you have two choices:  either type 'quit' for the row or column.  Or complete a game, and select type 'no' when asked whether you want to play again.



1 The program is pre-programmed to accept 'quit'.  Or any word with 'q' or 'Q' as the first letter.  It assumes the user wants to quit the program.
2 Note: The program doesn't stop and simply move to that place - but it does sets the priority of that piece so high that the probability of the computer moving there is high.
3 Note:  Adding to the priority board means that if the computer has assigned a negative number to the place, the chances are the program will still not move to that place - picking a cell that originally had a zero for priority.
4 This is a flaw in the AI which should be corrected in any future updates (see Conclusion).
??

(footnote continued)