/*************************************************************************/
/*                                                                       */
/*  Title:     QUARTERS                                                  */
/*             Copyright (C) 2004, Gregory E. Bailey                     */
/*             All Rights Reserved.                                      */
/*                                                                       */
/*  Version:   4.0                                                       */
/*                                                                       */
/*  Author:    Gregory E. Bailey                                         */
/*             3152 Evergreen Avenue                                     */
/*             Salt Lake City, UT 84109-3150                             */
/*             (801) 474-3250                                            */
/*             gbailey@lxpro.com                                         */
/*                                                                       */
/*  Created:   April 1, 1990                                             */
/*                                                                       */
/*  Modified:  04/01/1990  Initial coding of C version                   */
/*             04/02/1990  Debugging of GetSuggestedMove()               */
/*                         Changed UpdateScreen()                        */
/*                         Added GetLet, GetNum, ShowMove #defines       */
/*                         Added Command()                               */
/*             04/04/1990  Added randomness to GetSuggestedMove()        */
/*                         Removed curses dependency                     */
/*                         Terminate search tree if quarter taken        */
/*             01/23/1991  Added movelist, pass, restart to Command()    */
/*                         Changed UpdateScreen()                        */
/*                         Fixed MaxInd in GetSuggestedMove()            */
/*             01/24/1991  Replaced EvaluateBoard() function             */
/*                         Removed HumanWins(), ComputerWins()           */
/*             07/20/2004  Added termios handling for Linux              */
/*                         Changed default playing level                 */
/*                         Added debug level option 'Z'                  */
/*                                                                       */
/*  Compile:   gcc -Wall -O2 quarters.c -o quarters       (* LINUX   *)  */
/*             gcc -Dsun -O quarters.c -o quarters -lbsd  (* SUN/BSD *)  */
/*             tcc -G -O -Z -mt -lt quarters.c            (* TURBOC  *)  */
/*                                                                       */
/*************************************************************************/

/*************************************************************************/
/*                          INCLUDE FILES                                */
/*************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>

#if defined( linux )
#  include <sys/termios.h>
#elif defined( sun )
#  include <bsd/sgtty.h>
#  include <sys/ioctl.h>
#else
#  include <conio.h>
#endif

/*************************************************************************/
/*                        GLOBAL DEFINITIONS                             */
/*************************************************************************/

#define   ValueEmpty         0
#define   ValueHeadPenny     1
#define   ValueHeadNickel    2
#define   ValueHeadDime      3
#define   ValueHeadQuarter   25
#define   ValueTailPenny     (-1)
#define   ValueTailNickel    (-2)
#define   ValueTailDime      (-3)
#define   ValueTailQuarter   (-25)

#define   PresetLevel        4
#define   MinLevel           '1'
#define   MaxLevel           '7'

#define   BoardSize          7
#define   MaxMoves           100
#define   boolean            short
#define   Heads              1
#define   Tails              (-1)

#define   Sgn(x)             ( x < 0 ? -1 : ( x == 0 ? 0 : 1 ) )
#define   isslash(x)         ( x == '/' )
#define   isLetter(x)        ( ( x >= 'A' ) && ( x <= 'G' ) )
#define   isNumber(x)        ( ( x >= '1' ) && ( x <= '7' ) )
#define   Chance             ( ( rand() % 256 ) < 64 )

#ifndef TRUE
#  define TRUE               1
#endif

#ifndef FALSE
#  define FALSE              0
#endif

#define   GetLet(x)          { do { \
                                  x = getch(); \
                                  if ( islower( x ) ) \
                                     x = toupper( x ); \
                               } while ( !isLetter( x ) ); }

#define   GetNum(x)          { do { \
                                  x = getch(); \
                               } while ( !isNumber( x ) ); }

#define   ShowMove(x)        { printf( "%c%c-%c%c", ( 'A' + x[0] ), \
                                  ( '1' + x[1] ), ( 'A' + x[2] ), \
                                  ( '1' + x[3] ) ); }

#if defined( linux ) || defined( sun )
#  define getch              getchar
#endif

/*************************************************************************/
/*                        TYPE DECLARATIONS                              */
/*************************************************************************/

typedef   short   BoardType[BoardSize][BoardSize];
typedef   short   MoveType[4];

/*************************************************************************/
/*                         GLOBAL VARIABLES                              */
/*************************************************************************/

BoardType         Board;

#if defined( linux )
  struct termios  SavedTermState, TempTermState;
#elif defined( sun )
  struct sgttyb   SavedTermState, TempTermState;
#endif

/*************************************************************************/
/*                         SetupTerminal()                               */
/*************************************************************************/

void SetupTerminal()
{

#if defined( linux )
  if ( tcgetattr( 0, &TempTermState ) == -1 )
  {
    exit( 2 );
  }
  SavedTermState = TempTermState;
  TempTermState.c_lflag ^= ICANON;
  TempTermState.c_lflag ^= ECHO;
  tcsetattr( 0, TCSANOW, &TempTermState );
#elif defined( sun )
  if ( ioctl( 0, TIOCGETP, &TempTermState ) == -1 )
  {
    exit( 2 );
  }
  SavedTermState = TempTermState;
  TempTermState.sg_flags |= CBREAK;
  TempTermState.sg_flags ^= ECHO;
  ioctl( 0, TIOCSETP, &TempTermState );
#endif

}  /* SetupTerminal() */

/*************************************************************************/
/*                         ResetTerminal()                               */
/*************************************************************************/

void ResetTerminal()
{

#if defined( linux )
  tcsetattr( 0, TCSANOW, &SavedTermState );
#elif defined( sun )
  ioctl( 0, TIOCSETP, &SavedTermState );
#endif

}  /* ResetTerminal() */

/*************************************************************************/
/*                           InitBoard()                                 */
/*************************************************************************/

void InitBoard( boolean *EndGame, short *Level, short *DebugLevel )
{
  short   tempx, tempy;

  *EndGame = FALSE;
  *Level = PresetLevel;
  *DebugLevel = 0;
  srand( time(0) );

  for ( tempx = 0; tempx < BoardSize; tempx++ )
  {
    for ( tempy = 0; tempy < BoardSize; tempy++ )
    {
      Board[tempx][tempy] = ValueEmpty;
    }
  }

  Board[1][1] = ValueHeadDime;
  Board[1][5] = ValueTailDime;
  Board[2][0] = ValueHeadNickel;
  Board[2][2] = ValueHeadPenny;
  Board[2][4] = ValueTailPenny;
  Board[2][6] = ValueTailNickel;
  Board[3][1] = ValueHeadQuarter;
  Board[3][5] = ValueTailQuarter;
  Board[4][0] = ValueHeadNickel;
  Board[4][2] = ValueHeadPenny;
  Board[4][4] = ValueTailPenny;
  Board[4][6] = ValueTailNickel;
  Board[5][1] = ValueHeadDime;
  Board[5][5] = ValueTailDime;

}  /* InitBoard() */

/*************************************************************************/
/*                          UpdateScreen()                               */
/*************************************************************************/

void UpdateScreen( short Level )
{
  short   tempx, tempy;

  printf( "     A  B  C  D  E  F  G          " );
  printf( "=========   QUARTERS   =========\n" );
  printf( "  +-----------------------+       " );
  printf( "    (prefix commands with /)\n" );

  for ( tempy = ( BoardSize - 1 ); tempy >= 0; tempy-- )
  {
    printf( "%d |  ", ( tempy + 1 ) );

    for ( tempx = 0; tempx < BoardSize; tempx++ )
    {
      switch ( Board[tempx][tempy] )
      {
        case ValueEmpty       : if ( ( tempx % 2 ) == ( tempy % 2 ) )
                                {
                                  printf( "." );
                                }
                                else
                                {
                                  printf( " " );
                                }
                                break;
        case ValueHeadPenny   : printf( "P" ); break;
        case ValueHeadNickel  : printf( "N" ); break;
        case ValueHeadDime    : printf( "D" ); break;
        case ValueHeadQuarter : printf( "Q" ); break;
        case ValueTailPenny   : printf( "p" ); break;
        case ValueTailNickel  : printf( "n" ); break;
        case ValueTailDime    : printf( "d" ); break;
        case ValueTailQuarter : printf( "q" ); break;
      }
      printf( "  " );
    }

    printf( "| %d     ", ( tempy + 1 ) );

    switch ( tempy )
    {
      case 6 : printf( "--------------------------------" ); break;
      case 5 : printf( "  C = clear       M = movelist" );   break;
      case 4 : printf( "  D = display     P = pass" );       break;
      case 3 : printf( "  E = edit        R = restart" );    break;
      case 2 : printf( "  H = hint        S = switch" );     break;
      case 1 : printf( "  L = level       Q = quit" );       break;
      case 0 : printf( "--------------------------------" ); break;
    }

    printf( "\n" );
  }

  printf( "  +-----------------------+       " );
  printf( "       Current level:  %d\n", Level );
  printf( "     A  B  C  D  E  F  G          " );
  printf( "================================\n\n" );

}  /* UpdateScreen() */

/*************************************************************************/
/*                           CheckMove()                                 */
/*************************************************************************/

void CheckMove( boolean *StopFlag, short *NumMoves,
                MoveType MoveList[MaxMoves],
                short xfr, short yfr, short xto, short yto )
{
  *StopFlag = FALSE;

  if ( xto < 0 || xto >= BoardSize || yto < 0 || yto >= BoardSize )
  {
    *StopFlag = TRUE;
  }
  else if ( Sgn( Board[xfr][yfr] ) == Sgn( Board[xto][yto] ) )
  {
    *StopFlag = TRUE;
  }
  else
  {
    if ( Sgn( Board[xfr][yfr] ) == -Sgn( Board[xto][yto] ) )
    {
      *StopFlag = TRUE;
    }
    MoveList[*NumMoves][0] = xfr;
    MoveList[*NumMoves][1] = yfr;
    MoveList[*NumMoves][2] = xto;
    MoveList[*NumMoves][3] = yto;
    (*NumMoves)++;
  }

}  /* CheckMove() */

/*************************************************************************/
/*                          MakeMoveList()                               */
/*************************************************************************/

void MakeMoveList( short PlayFor, short *NM, MoveType ML[MaxMoves] )
{
  boolean   SF;
  short     xfr, yfr, xto, yto;

  *NM = 0;
  for ( xfr = 0; xfr < BoardSize; xfr++ )
  {
    for ( yfr = 0; yfr < BoardSize; yfr++ )
    {
      if ( Sgn( Board[xfr][yfr] ) == PlayFor )
      {
        switch ( Board[xfr][yfr] )
        {
          case ValueHeadPenny   :
          case ValueTailPenny   :
          case ValueHeadQuarter :
          case ValueTailQuarter :

            CheckMove( &SF, NM, ML, xfr, yfr, xfr - 1, yfr - 1 );
            CheckMove( &SF, NM, ML, xfr, yfr, xfr - 1, yfr + 1 );
            CheckMove( &SF, NM, ML, xfr, yfr, xfr + 1, yfr - 1 );
            CheckMove( &SF, NM, ML, xfr, yfr, xfr + 1, yfr + 1 );
            if ( ( xfr % 2 ) == 0 )
            {
              CheckMove( &SF, NM, ML, xfr, yfr, xfr, yfr - 2 );
              CheckMove( &SF, NM, ML, xfr, yfr, xfr, yfr + 2 );
              CheckMove( &SF, NM, ML, xfr, yfr, xfr - 2, yfr );
              CheckMove( &SF, NM, ML, xfr, yfr, xfr + 2, yfr );
            }
            break;

          case ValueHeadNickel :
          case ValueTailNickel :

            xto = xfr; yto = yfr;
            do {
              yto -= 2;
              CheckMove( &SF, NM, ML, xfr, yfr, xto, yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              yto += 2;
              CheckMove( &SF, NM, ML, xfr, yfr, xto, yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              xto -= 2;
              CheckMove( &SF, NM, ML, xfr, yfr, xto, yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              xto += 2;
              CheckMove( &SF, NM, ML, xfr, yfr, xto, yto );
            } while ( !SF );
            break;

          case ValueHeadDime :
          case ValueTailDime :

            xto = xfr; yto = yfr;
            do {
              CheckMove( &SF, NM, ML, xfr, yfr, --xto, --yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              CheckMove( &SF, NM, ML, xfr, yfr, --xto, ++yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              CheckMove( &SF, NM, ML, xfr, yfr, ++xto, --yto );
            } while ( !SF );
            xto = xfr; yto = yfr;
            do {
              CheckMove( &SF, NM, ML, xfr, yfr, ++xto, ++yto );
            } while ( !SF );
            break;
        }
      }
    }
  }

}  /* MakeMoveList() */

/*************************************************************************/
/*                        GetSuggestedMove()                             */
/*************************************************************************/

short GetSuggestedMove( short Level, short PlayFor, MoveType ReturnMove,
                        short DebugLevel )
{
  MoveType   DummyMove, MoveList[MaxMoves];
  short      NumMoves, MaxVal, temp, BoardContents, CurVal, MaxInd;

  MakeMoveList( PlayFor, &NumMoves, MoveList );
  MaxVal = -128;
  MaxInd = 0;

  for ( temp = 0; temp < NumMoves; temp++ )
  {
    if ( DebugLevel > 0 )
    {
      printf( "Considering[%d]:  ", DebugLevel );
      ShowMove( MoveList[temp] );

      if ( DebugLevel > 1 )
      {
        printf( "\n" );
      }
    }

    BoardContents = Board[MoveList[temp][2]][MoveList[temp][3]];
    Board[MoveList[temp][2]][MoveList[temp][3]] =
      Board[MoveList[temp][0]][MoveList[temp][1]];
    Board[MoveList[temp][0]][MoveList[temp][1]] = ValueEmpty;

    if ( ( BoardContents == ValueHeadQuarter )
      || ( BoardContents == ValueTailQuarter ) )
    {
      CurVal = 127;
    }
    else
    {
      CurVal = - ( PlayFor * BoardContents );
      if ( Level > 1 )
      {
        CurVal -= GetSuggestedMove( ( Level - 1 ), ( -PlayFor ), DummyMove,
                                    ( DebugLevel - 1 ) );
      }
    }

    Board[MoveList[temp][0]][MoveList[temp][1]] =
      Board[MoveList[temp][2]][MoveList[temp][3]];
    Board[MoveList[temp][2]][MoveList[temp][3]] = BoardContents;

    if ( DebugLevel > 0 )
    {
      if ( DebugLevel > 1 )
      {
        printf( "    Results[%d]:  ", DebugLevel );
        ShowMove( MoveList[temp] );
      }

      printf( "  Score: %+4d", CurVal );
      if ( CurVal >= MaxVal )
      {
        printf( " ***" );
      }
      printf( "\n" );

      if ( DebugLevel > 1 )
      {
        printf( "\n" );
      }
    }

    if ( ( CurVal > MaxVal ) || ( ( CurVal == MaxVal ) && Chance ) )
    {
      MaxVal = CurVal;
      MaxInd = temp;
    }
  }

  for ( temp = 0; temp < 4; temp++ )
  {
    ReturnMove[temp] = MoveList[MaxInd][temp];
  }

  return( MaxVal );

}  /* GetSuggestedMove */

/*************************************************************************/
/*                        GetComputerMove()                              */
/*************************************************************************/

void GetComputerMove( boolean *EndGame, short Level, short DebugLevel )
{
  MoveType   ComputerMove;

  GetSuggestedMove( Level, Tails, ComputerMove, DebugLevel );
  if ( DebugLevel > 0 )
  {
    printf( "\n" );
  }

  *EndGame = ( Board[ComputerMove[2]][ComputerMove[3]] ==
    ValueHeadQuarter );

  Board[ComputerMove[2]][ComputerMove[3]] =
    Board[ComputerMove[0]][ComputerMove[1]];
  Board[ComputerMove[0]][ComputerMove[1]] = ValueEmpty;

  printf( "My Move:  " );
  ShowMove( ComputerMove );
  printf( "\n\n" );

}  /* GetComputerMove() */

/*************************************************************************/
/*                            Command()                                  */
/*************************************************************************/

void Command( boolean *EndGame, short *Level, short *DebugLevel )
{
  char       tempc;
  short      NumMoves, tempx, tempy;
  MoveType   HintMove, MoveList[MaxMoves];

  printf( "\n\nCommand:  " );
  tempc = getch();

  switch ( tempc )
  {
    case 'c' :
    case 'C' : printf( "clear\n\n" );
               for ( tempx = 0; tempx < BoardSize; tempx++ )
               {
                 for ( tempy = 0; tempy < BoardSize; tempy++ )
                 {
                   Board[tempx][tempy] = ValueEmpty;
                 }
               }
               break;

    case 'd' :
    case 'D' : printf( "display\n\n" );
               UpdateScreen( *Level );
               break;

    case 'e' :
    case 'E' : printf( "edit\n\n" );
               printf( "EDIT:  " );
               GetLet( tempc );
               printf( "%c", tempc );
               tempx = tempc - 'A';
               GetNum( tempc );
               printf( "%c", tempc );
               tempy = tempc - '1';
               printf( " = " );
               tempc = getch();
               switch ( tempc )
               {
                 case 'p' : Board[tempx][tempy] = ValueTailPenny; break;
                 case 'n' : Board[tempx][tempy] = ValueTailNickel; break;
                 case 'd' : Board[tempx][tempy] = ValueTailDime; break;
                 case 'q' : Board[tempx][tempy] = ValueTailQuarter; break;
                 case 'P' : Board[tempx][tempy] = ValueHeadPenny; break;
                 case 'N' : Board[tempx][tempy] = ValueHeadNickel; break;
                 case 'D' : Board[tempx][tempy] = ValueHeadDime; break;
                 case 'Q' : Board[tempx][tempy] = ValueHeadQuarter; break;
                 case ' ' :
                 case '.' : Board[tempx][tempy] = ValueEmpty; break;
                 default  : printf( "unrecognized character:  " );
               }
               printf( "%c\n\n", tempc );
               break;

    case 'h' :
    case 'H' : printf( "hint\n\n" );
               tempx = GetSuggestedMove( *Level, Heads, HintMove,
                                         *DebugLevel );
               if ( *DebugLevel > 0 )
               {
                 printf( "\n" );
               }
               printf( "HINT = " );
               ShowMove( HintMove );
               printf( "\n\n" );
               break;

    case 'l' :
    case 'L' : printf( "level\n\n" );
               printf( "LEVEL = " );
               do {
                 tempc = getch();
               } while ( ( tempc < MinLevel ) || ( tempc > MaxLevel ) );
               *Level = tempc - '0';
               printf( "%c\n\n", tempc );
               break;

    case 'm' :
    case 'M' : printf( "movelist\n\n" );
               MakeMoveList( Heads, &NumMoves, MoveList );
               printf( "Total number of moves:  %d\n\n", NumMoves );
               for ( tempx = 0; tempx < NumMoves; tempx++ )
               {
                 ShowMove( MoveList[tempx] );
                 printf( "   " );
                 if ( ( tempx % 8 ) == 7 )
                 {
                   printf( "\n" );
                 }
               }
               if ( ( tempx % 8 ) != 0 )
               {
                 printf( "\n" );
               }
               printf( "\n" );
               break;

    case 'p' :
    case 'P' : printf( "pass\n\n" );
               GetComputerMove( EndGame, *Level, *DebugLevel );
               UpdateScreen( *Level );
               if ( *EndGame )
               {
                 printf( "Computer wins the game.\n\n" );
                 ResetTerminal();
                 exit( 0 );
               }
               break;

    case 'r' :
    case 'R' : printf( "restart\n\n" );
               InitBoard( EndGame, Level, DebugLevel );
               UpdateScreen( *Level );
               break;

    case 's' :
    case 'S' : printf( "switch\n\n" );
               for ( tempx = 0; tempx < BoardSize; tempx++ )
               {
                 for ( tempy = 0; tempy < BoardSize; tempy++ )
                 {
                   switch ( Board[tempx][tempy] )
                   {
                     case ValueHeadPenny   :
                     case ValueTailPenny   :
                     case ValueHeadNickel  :
                     case ValueTailNickel  :
                     case ValueHeadDime    :
                     case ValueTailDime    :
                     case ValueHeadQuarter :
                     case ValueTailQuarter : Board[tempx][tempy] =
                                               -Board[tempx][tempy];
                                             break;
                     default               : break;
                   }
                 }
               }
               break;

    case 'q' :
    case 'Q' : printf( "quit\n\n" );
               ResetTerminal();
               exit( 0 );
               break;

    case 'z' :
    case 'Z' : printf( "debug level\n\n" );
               printf( "DEBUG LEVEL = " );
               do {
                 tempc = getch();
               } while ( ( tempc < '0' ) || ( tempc > MaxLevel ) );
               *DebugLevel = tempc - '0';
               printf( "%c\n\n", tempc );
               break;

    default  : printf( "unrecognized command\n\n" );
               break;
  }

}  /* Command() */

/*************************************************************************/
/*                          GetHumanMove()                               */
/*************************************************************************/

void GetHumanMove( boolean *EndGame, short *Level, short *DebugLevel )
{
  boolean    ValidFlag;
  char       tempc;
  short      temp, NVMoves;
  MoveType   HumanMove, ValidMoves[MaxMoves];

  do {

    printf( "Your Move:  " );
    do {
      tempc = getch();
      if ( islower( tempc ) )
      {
         tempc = toupper( tempc );
      }
    } while ( !isslash( tempc ) && !isLetter( tempc ) );

    while ( tempc == '/' )
    {
      Command( EndGame, Level, DebugLevel );

      printf( "Your Move:  " );
      do {
        tempc = getch();
        if ( islower( tempc ) )
        {
          tempc = toupper( tempc );
        }
      } while ( !isslash( tempc ) && !isLetter( tempc ) );
    }

    printf( "%c", tempc );
    HumanMove[0] = tempc - 'A';
    GetNum( tempc ); printf( "%c", tempc );
    HumanMove[1] = tempc - '1';
    printf( "-" );
    GetLet( tempc ); printf( "%c", tempc );
    HumanMove[2] = tempc - 'A';
    GetNum( tempc ); printf( "%c", tempc );
    HumanMove[3] = tempc - '1';

    MakeMoveList( Heads, &NVMoves, ValidMoves );
    ValidFlag = FALSE;

    for ( temp = 0; temp < NVMoves; temp++ )
    {
      if ( ( ValidMoves[temp][0] == HumanMove[0] )
        && ( ValidMoves[temp][1] == HumanMove[1] )
        && ( ValidMoves[temp][2] == HumanMove[2] )
        && ( ValidMoves[temp][3] == HumanMove[3] ) )
      {
        ValidFlag = TRUE;
      }
    }

    if ( !ValidFlag )
    {
      printf( " <=== ILLEGAL MOVE\n\n" );
    }

  } while ( !ValidFlag );

  printf( "\n\n" );

  *EndGame = ( Board[HumanMove[2]][HumanMove[3]] == ValueTailQuarter );
  Board[HumanMove[2]][HumanMove[3]] = Board[HumanMove[0]][HumanMove[1]];
  Board[HumanMove[0]][HumanMove[1]] = ValueEmpty;

}  /* GetHumanMove() */

/*************************************************************************/
/*                              main()                                   */
/*************************************************************************/

int main( int argc, char *argv[] )
{
  boolean   EndGame;
  short     Level, DebugLevel;

  SetupTerminal();
  InitBoard( &EndGame, &Level, &DebugLevel );
  printf( "\nQUARTERS Version 4.0\n" );
  printf( "Copyright (C) 2004, Gregory E. Bailey\n" );
  printf( "All Rights Reserved.\n\n" );
  UpdateScreen( Level );

  while ( !EndGame )
  {
    GetHumanMove( &EndGame, &Level, &DebugLevel );
    UpdateScreen( Level );

    if ( EndGame )
    {
      printf( "Human wins the game.\n\n" );
    }
    else
    {
      GetComputerMove( &EndGame, Level, DebugLevel );
      UpdateScreen( Level );
      if ( EndGame )
      {
        printf( "Computer wins the game.\n\n" );
      }
    }
  }

  ResetTerminal();
  exit( 0 );

}  /* main() */

/*************************************************************************/
/*                        END OF SOURCE FILE                             */
/*************************************************************************/