/* Tic-tac-toe engine (3x3), adapted from a console program by
Alastair Francis, using minimax, alpha-beta pruning, and
depth-limited recursion with hueristic function
*/
/* This program is free software. You may redistribute and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License or
 * (at your option) any later version.
 *
 * Refer to the file C:\LCARS24\DATA\COPYING.TXT for details.
 */


#include "wb3.h"


void Wb3InitBoard (Wb3BoardType* board)
{
	int i;

	for (i = 0; i < Wb3BOARD_SIZE; ++i)
	board->Wb3Element[i] = Wb3empty;
	board->Wb3Elements_occupied = 0;
}  /* end Wb3InitBoard */

void Wb3PlacePiece (Wb3BoardType* board, int position, Wb3GamePiece piece)
{
	board->Wb3Element[position] = piece;
	++(board->Wb3Elements_occupied);
}  /* end Wb3PlacePiece */


void Wb3RemovePiece (Wb3BoardType* board, int position)
{
	/* check if position is not already Wb3empty */
	if (board->Wb3Element[position] != Wb3empty)  {
		board->Wb3Element[position] = Wb3empty;
		--(board->Wb3Elements_occupied);
	}  /* end if */
}  /* end Wb3RemovePiece */


Wb3Boolean Wb3IsWinner (Wb3BoardType board)
{
  int i, position;
  int check_line;
  Wb3Boolean winner = Wb3False;

  /* check rows */
  position = 0;
  while ((! winner) && (position < Wb3BOARD_SIZE))  {
	  check_line = board.Wb3Element[position];

	  /* check each row for consecutive pieces which are the same */
	  for (i = (position + 1); i < (position + Wb3BOARD_WIDTH); ++i)
	check_line = check_line & board.Wb3Element[i];

	  winner = (check_line != Wb3empty) ? Wb3True : Wb3False;
	  position += Wb3BOARD_WIDTH;
  }  /* end while - check rows */

  /* check columns */
  position = 0;
  while ((! winner) && (position < Wb3BOARD_WIDTH))  {
	  check_line = board.Wb3Element[position];

	  /* check each column for consecutive pieces which are the same */
	  for (i = (position + Wb3BOARD_WIDTH); i < Wb3BOARD_SIZE; i += Wb3BOARD_WIDTH)
	check_line = check_line & board.Wb3Element[i];

	  winner = (check_line != Wb3empty) ? Wb3True : Wb3False;
	  ++position;
  }  /* end while - check columns */

  /* check diagonals */
  /* diagonal from top left to bottom right */
  if (! winner)  {
	  check_line = board.Wb3Element[0];
	  for (i = (Wb3BOARD_WIDTH + 1); i < Wb3BOARD_SIZE; i += (Wb3BOARD_WIDTH + 1))
	check_line = check_line & board.Wb3Element[i];

	  winner = (check_line != Wb3empty) ? Wb3True : Wb3False;
  }  /* end if */

  /* diagonal from top right to bottom left */
  if (! winner)  {
	  check_line = board.Wb3Element[Wb3BOARD_WIDTH - 1];
	  for (i = (2 * Wb3BOARD_WIDTH - 2); i < (Wb3BOARD_SIZE - 1);
					  i += (Wb3BOARD_WIDTH - 1))
	check_line = check_line & board.Wb3Element[i];

	  winner = (check_line != Wb3empty) ? Wb3True : Wb3False;
  }  /* end if */

  return winner;
}  /* end Wb3IsWinner */


Wb3Boolean Wb3IsFull (Wb3BoardType board)
{
  if (board.Wb3Elements_occupied == Wb3BOARD_SIZE)  {
	  return Wb3True;
  }
  else  {
	  return Wb3False;
  }  /* end if else */
}  /* end Wb3IsFull */


int Wb3Heuristic (Wb3BoardType board)
{
  int i, position;
  Wb3Boolean possible_winner;
  int utility_tally, utility = 0;

  /* determine utility of rows */
  position = 0;
  while (position < Wb3BOARD_SIZE)  {
	  /* check each row for possible winning rows */
	  possible_winner = Wb3True;
	  utility_tally = 0;
	  for (i = position; (i < (position + Wb3BOARD_WIDTH)) && possible_winner; ++i)  {
	if (board.Wb3Element[i] != Wb3empty)  {
		if (Wb3Players_piece != board.Wb3Element[i])  {
			/* row has non-Wb3Player piece, can't be a winning row */
			possible_winner = Wb3False;
			utility_tally = 0;
		}
		else  {
			/* utility_tally counts the number of Wb3Player pieces per row */
			++utility_tally;
		}  /* end if else */
	}  /* end if - board position not Wb3empty */
	  }  /* end for loop - utility of a row */

	  utility += utility_tally;
	  position += Wb3BOARD_WIDTH;
  }  /* end while - utility of all rows */

  /* determine utility of columns */
  position = 0;
  while (position < Wb3BOARD_WIDTH)  {
	  possible_winner = Wb3True;
	  utility_tally = 0;
	  for (i = position; (i < Wb3BOARD_SIZE) && possible_winner; i += Wb3BOARD_WIDTH)  {
	if (board.Wb3Element[i] != Wb3empty)  {
		if (Wb3Players_piece != board.Wb3Element[i])  {
			possible_winner = Wb3False;
			utility_tally = 0;
		}
		else  {
			/* utility_tally counts the number of Wb3Player pieces per column */
			++utility_tally;
		}  /* end if else */
	}  /* end if - board position not Wb3empty */
	  }  /* end for loop - utility of column */

	  utility += utility_tally;
	  ++position;
  }  /* end while - utility of all columns */

  /* determine utility of diagonals */
  /* diagonal from top left to bottom right */
  possible_winner = Wb3True;
  utility_tally = 0;
  for (i = 0; (i < Wb3BOARD_SIZE) && possible_winner; i += (Wb3BOARD_WIDTH + 1))  {
	  if (board.Wb3Element[i] != Wb3empty)  {
	if (Wb3Players_piece != board.Wb3Element[i])  {
		possible_winner = Wb3False;
		utility_tally = 0;
	}
	else  {
		++utility_tally;
	}  /* end if else */
	  }  /* end if */
  }  /* end for loop */
  utility += utility_tally;

  /* diagonal from top right to bottom left */
  possible_winner = Wb3True;
  utility_tally = 0;
  for (i = Wb3BOARD_WIDTH - 1; (i < (Wb3BOARD_SIZE - 1)) && possible_winner;
						i += (Wb3BOARD_WIDTH - 1))  {
	  if (board.Wb3Element[i] != Wb3empty)  {
	if (Wb3Players_piece != board.Wb3Element[i])  {
		possible_winner = Wb3False;
		utility_tally = 0;
	}
	else  {
		++utility_tally;
	}  /* end if else */
	  }  /* end if */
  }  /* end for loop */
  utility += utility_tally;

  return utility;
}  /* end Wb3Heuristic */


int Wb3FindBestMove (Wb3BoardType board, Wb3GamePiece piece)
{
	const int corner_positions[4] =
	{0, Wb3BOARD_WIDTH - 1, Wb3BOARD_SIZE - Wb3BOARD_WIDTH, Wb3BOARD_SIZE - 1};
	int best_move, corner, centre_pos;
	Wb3Boolean occupied;
	int dummy;

	centre_pos = Wb3BOARD_SIZE / 2;
	if (board.Wb3Elements_occupied == 0)  {
		/* no pieces on board, best move is centre */
		best_move = centre_pos;
	}
	else  {
		if (board.Wb3Elements_occupied == 1)  {
	 if (board.Wb3Element[centre_pos] == Wb3empty)  {
		 /* centre position not taken, best move centre position */
		 best_move = centre_pos;
	 }
	 else  {
		 /* centre already taken, best move on a corner */
		 occupied = Wb3False;
		 do  {
			 /* choose a corner position at random */
/* Turbo code			corner = corner_positions[random (4)]; */
/* DJGPP code */  corner = corner_positions[rand() % 4];


			 if (board.Wb3Element[corner] != Wb3empty)
		  occupied = Wb3True;
		 } while (occupied);

		 best_move = corner;
	 }  /* end if else - 1 piece already on board*/
		}
		else  {
	 /* 2 or more pieces already on the board */
	 /* call minimax with alpha-beta pruning and recursion depth limitation */
	 Wb3Players_piece = piece;
	 best_move = Wb3FindPlayerMove (board, piece, &dummy, INT_MIN, INT_MAX, 0);
		}  /* end else */
	}  /* end if else */

	return best_move;
}  /* end Wb3FindBestMove */

void Wb3FindOpponentMove (Wb3BoardType board, Wb3GamePiece piece, int* status,
			 int alpha, int beta, int depth)
{
	int i, dont_care;
	int current_status;

	if (Wb3IsWinner (board))  {
		/* goal state and terminal case, Wb3Player has won by last move */
		/* utility value is an arbitrarly large number < MAX_INT */
		*status = 1000;
	}
	else  {
		if (Wb3IsFull (board))  {
	 /* terminal case, game drawn */
	 *status = 0;
		}
		else  {
	 /*
		 Opponent maximizes its outcome, minimum Wb3Player outcome.
		 beta is the upper bound on the value that the minimizing node
		 may be assigned.
		 If the value of the min position is determined to be less than
		 or equal to the alpha value of the parent node, then we can stop
		 generation of the remaining children of this min node.
	 */

	 if (depth < Wb3MaxDepth)  {
		 *status = beta;

		 for (i = 0; (i < Wb3BOARD_SIZE) && (*status > alpha); ++i)  {
			 if (board.Wb3Element[i] == Wb3empty)  {
		  Wb3PlacePiece (&board, i, piece);
		  dont_care = Wb3FindPlayerMove (board, ((piece == X) ? O : X),
				 &current_status, alpha, *status, (depth + 1));
		  Wb3RemovePiece (&board, i);
		  if (current_status < *status)  {
			  /* found a better move for opponent */
			  *status = current_status;
		  }  /* end if */
			 }  /* end if - try game piece in non Wb3empty position */
		 }  /* end for - try all Wb3empty board positions */
	 }
	 else  {
		 *status = Wb3Heuristic (board);
	 }  /* end if else */

		}  /* end if else */
	}  /* end if else */

}  /* end Wb3FindOpponentMove */

/* minimax routines with alpha-beta pruning and recurive depth limitation */
int Wb3FindPlayerMove (Wb3BoardType board, Wb3GamePiece piece, int* status,
				int alpha, int beta, int depth)
{
	int i, best_move;
	int current_status;

	if (Wb3IsWinner (board))  {
		/* terminal case, opponent has won by last move */
		/* utility value is an arbitrarly small number > MIN_INT */
		*status = -1000;
	}
	else  {
		if (Wb3IsFull (board))  {
	 /* terminal case, game drawn */
	 *status = 0;
		}
		else  {
	 /*
		 Keep searching for a better move, maximum Wb3Player outcome.
		 alpha is the lower bound on the value the maximizing node may
		 be assigned.
		 If the value of a max position is determined to be greater than
		 or equal to the beta value of its parent node, then we can
		 stop generation of the remaining children of this max node.
	 */
	 if (depth < Wb3MaxDepth)  {
		 *status = alpha;

		 for (i = 0; (i < Wb3BOARD_SIZE) && (*status < beta); ++i)  {
			 if (board.Wb3Element[i] == Wb3empty)  {
		  Wb3PlacePiece (&board, i, piece);
		  Wb3FindOpponentMove (board, ((piece == X) ? O : X),
				&current_status, *status, beta, (depth + 1));
		  Wb3RemovePiece (&board, i);
		  if (current_status > *status)  {
			  /* Found a move with better utility for the Wb3Player. */
			  *status = current_status;
			  best_move = i;
		  }  /* end if */
			 }  /* end if - try game piece in non Wb3empty position */
		 }  /* end for - try all Wb3empty board positions */
	 }
	 else  {
		 *status = Wb3Heuristic (board);
	 }  /* end if */

		}  /* end if else */
	}  /* end if else */

	return best_move;
}  /* end Wb3FindPlayerMove */
/* eof */

