sc/source/core/tool/sctictac.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: sctictac.cxx,v $
  10  * $Revision: 1.7 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sc.hxx"
  33
  34 /* Tic-Tac-Toe program by Steve Chapel schapel@cs.ucsb.edu
  35    Uses alpha-beta pruning minimax search to play a "perfect" game.
  36    The alpha-beta pruning can be removed, but will increase search time.
  37    The heuristic and move ordering in BestMove() can also be removed with
  38      an increase in search time. */
  39
  40 #include <stdio.h>
  41 #include <ctype.h>
  42
  43
  44 #include "sctictac.hxx"
  45
  46 #ifdef TICTACTOE_SC
  47 #include "document.hxx"
  48 #include "cell.hxx"
  49 #endif
  50
  51 const Square_Type ScTicTacToe::Empty = ' ';
  52 const Square_Type ScTicTacToe::Human = 'X';
  53 const Square_Type ScTicTacToe::Compi = 'O';
  54 const int ScTicTacToe::Infinity = 10;           /* Higher value than any score */
  55 const int ScTicTacToe::Maximum_Moves = ScTicTacToe_Squares;     /* Maximum moves in a game */
  56
  57 /* Array describing the eight combinations of three squares in a row */
  58 const int ScTicTacToe::Three_in_a_Row[ScTicTacToe_Possible_Wins][3] = {
  59     { 0, 1, 2 },
  60     { 3, 4, 5 },
  61     { 6, 7, 8 },
  62     { 0, 3, 6 },
  63     { 1, 4, 7 },
  64     { 2, 5, 8 },
  65     { 0, 4, 8 },
  66     { 2, 4, 6 }
  67 };
  68
  69 /* Array used in heuristic formula for each move. */
  70 const int ScTicTacToe::Heuristic_Array[4][4] = {
  71     {     0,   -10,      -100, -1000 },
  72     {    10,     0,             0,         0 },
  73     {   100,     0,             0,         0 },
  74     {  1000,     0,             0,         0 }
  75 };
  76
  77
  78 #ifdef TICTACTOE_SC
  79 ScTicTacToe::ScTicTacToe( ScDocument* pDocP, const ScAddress& rPos ) :
  80         aPos( rPos ),
  81         pDoc( pDocP ),
  82         aStdOut( "Computer plays O, you play X. " ),
  83         bInitialized( FALSE )
  84 {
  85 }
  86 #else
  87 ScTicTacToe::ScTicTacToe() :
  88         bInitialized( FALSE ),
  89         aStdOut( "Computer plays O, you play X. " )
  90 {
  91 }
  92 #endif
  93
  94
  95 /* Return the other player */
  96 inline Square_Type ScTicTacToe::Other(Square_Type Player)
  97 {
  98     return Player == Human ? Compi : Human;
  99 }
 100
 101
 102 /* Make a move on the board */
 103 inline void ScTicTacToe::Play(int Square, Square_Type Player)
 104 {
 105     Board[Square] = Player;
 106 }
 107
 108
 109 #ifdef TICTACTOE_STDOUT
 110
 111 void ScTicTacToe::GetOutput( ByteString& rStr )
 112 {
 113      rStr = aStdOut;
 114      aStdOut.Erase();
 115 }
 116
 117 #else // !TICTACTOE_STDOUT
 118
 119 void ScTicTacToe::GetOutput( String& rStr )
 120 {
 121      rStr = String( aStdOut, gsl_getSystemTextEncoding() );
 122      aStdOut.Erase();
 123 }
 124
 125 #endif // TICTACTOE_STDOUT
 126
 127
 128 /* Clear the board */
 129 void ScTicTacToe::Initialize( BOOL bHumanFirst )
 130 {
 131     bInitialized = TRUE;
 132     aPlayer = (bHumanFirst ? Human : Compi);
 133     nMove = 1;
 134     for (int i = 0; i < ScTicTacToe_Squares; i++)
 135         Board[i] = Empty;
 136 }
 137
 138
 139 /* If a player has won, return the winner. If the game is a tie,
 140    return 'C' (for cat). If the game is not over, return Empty. */
 141 Square_Type ScTicTacToe::Winner()
 142 {
 143     int i;
 144     for (i = 0; i < ScTicTacToe_Possible_Wins; i++)
 145     {
 146         Square_Type Possible_Winner = Board[Three_in_a_Row[i][0]];
 147         if (Possible_Winner != Empty &&
 148             Possible_Winner == Board[Three_in_a_Row[i][1]] &&
 149             Possible_Winner == Board[Three_in_a_Row[i][2]])
 150             return Possible_Winner;
 151     }
 152
 153     for (i = 0; i < ScTicTacToe_Squares; i++)
 154     {
 155         if (Board[i] == Empty)
 156             return Empty;
 157     }
 158
 159     return 'C';
 160 }
 161
 162
 163 /* Return a heuristic used to determine the order in which the
 164    children of a node are searched */
 165 int ScTicTacToe::Evaluate(Square_Type Player)
 166 {
 167     int i;
 168     int Heuristic = 0;
 169     for (i = 0; i < ScTicTacToe_Possible_Wins; i++)
 170     {
 171         int j;
 172         int Players = 0, Others = 0;
 173         for (j = 0; j < 3; j++)
 174         {
 175             Square_Type Piece = Board[Three_in_a_Row[i][j]];
 176             if (Piece == Player)
 177                 Players++;
 178             else if (Piece == Other(Player))
 179                 Others++;
 180         }
 181         Heuristic += Heuristic_Array[Players][Others];
 182     }
 183     return Heuristic;
 184 }
 185
 186
 187 /* Return the score of the best move found for a board
 188    The square to move to is returned in *Square */
 189 int ScTicTacToe::BestMove(Square_Type Player, int *Square,
 190         int Move_Nbr, int Alpha, int Beta)
 191 {
 192     int Best_Square = -1;
 193     int Moves = 0;
 194     int i;
 195     Move_Heuristic_Type Move_Heuristic[ScTicTacToe_Squares];
 196
 197     Total_Nodes++;
 198
 199     /* Find the heuristic for each move and sort moves in descending order */
 200     for (i = 0; i < ScTicTacToe_Squares; i++)
 201     {
 202         if (Board[i] == Empty)
 203         {
 204             int Heuristic;
 205             int j;
 206             Play(i, Player);
 207             Heuristic = Evaluate(Player);
 208             Play(i, Empty);
 209             for (j = Moves-1; j >= 0 &&
 210                     Move_Heuristic[j].Heuristic < Heuristic; j--)
 211             {
 212                 Move_Heuristic[j + 1].Heuristic = Move_Heuristic[j].Heuristic;
 213                 Move_Heuristic[j + 1].Square = Move_Heuristic[j].Square;
 214             }
 215             Move_Heuristic[j + 1].Heuristic = Heuristic;
 216             Move_Heuristic[j + 1].Square = i;
 217             Moves++;
 218         }
 219     }
 220
 221     for (i = 0; i < Moves; i++)
 222     {
 223         int Score;
 224         int Sq = Move_Heuristic[i].Square;
 225         Square_Type W;
 226
 227         /* Make a move and get its score */
 228         Play(Sq, Player);
 229
 230         W = Winner();
 231         if (W == Compi)
 232             Score = (Maximum_Moves + 1) - Move_Nbr;
 233         else if (W == Human)
 234             Score = Move_Nbr - (Maximum_Moves + 1);
 235         else if (W == 'C')
 236             Score = 0;
 237         else
 238             Score = BestMove(Other(Player), Square, Move_Nbr + 1,
 239                     Alpha, Beta);
 240
 241         Play(Sq, Empty);
 242
 243         /* Perform alpha-beta pruning */
 244         if (Player == Compi)
 245         {
 246             if (Score >= Beta)
 247             {
 248                 *Square = Sq;
 249                 return Score;
 250             }
 251             else if (Score > Alpha)
 252             {
 253                 Alpha = Score;
 254                 Best_Square = Sq;
 255             }
 256         }
 257         else
 258         {
 259             if (Score <= Alpha)
 260             {
 261                 *Square = Sq;
 262                 return Score;
 263             }
 264             else if (Score < Beta)
 265             {
 266                 Beta = Score;
 267                 Best_Square = Sq;
 268             }
 269         }
 270     }
 271     *Square = Best_Square;
 272     if (Player == Compi)
 273         return Alpha;
 274     else
 275         return Beta;
 276 }
 277
 278
 279 /* Provide an English description of the score returned by BestMove */
 280 void ScTicTacToe::Describe(int Score)
 281 {
 282     if (Score < 0)
 283         aStdOut += "You have a guaranteed win. ";
 284     else if (Score == 0)
 285         aStdOut += "I can guarantee a tie. ";
 286     else
 287     {
 288         aStdOut += "I have a guaranteed win by move ";
 289         aStdOut += ByteString::CreateFromInt32( Maximum_Moves - Score + 1 );
 290         aStdOut += ". ";
 291     }
 292 }
 293
 294
 295 /* Have the human or the computer move */
 296 void ScTicTacToe::Move( int& Square )
 297 {
 298     if (aPlayer == Compi)
 299     {
 300         Total_Nodes = 0;
 301         Describe(BestMove(aPlayer, &Square, nMove, -Infinity, Infinity));
 302         aStdOut += ByteString::CreateFromInt32( Total_Nodes );
 303         aStdOut += " nodes examined. ";
 304         Play(Square, aPlayer);
 305         aStdOut += "Move #";
 306         aStdOut += ByteString::CreateFromInt32( nMove );
 307         aStdOut += " - O moves to ";
 308         aStdOut += ByteString::CreateFromInt32( Square + 1 );
 309         aStdOut += ". ";
 310         aPlayer = Other( aPlayer );
 311         nMove++;
 312     }
 313     else
 314     {
 315         if ( Square < 0 || Square >= ScTicTacToe_Squares
 316                 || Board[Square] != Empty )
 317             Square = -1;
 318         else
 319         {
 320             Play(Square, aPlayer);
 321             aPlayer = Other( aPlayer );
 322             nMove++;
 323         }
 324     }
 325 }
 326
 327
 328 // Try a move
 329 Square_Type ScTicTacToe::TryMove( int& Square )
 330 {
 331     if ( !bInitialized )
 332         Initialize( FALSE );
 333
 334     Square_Type W = Winner();
 335     if ( W == Empty )
 336     {
 337         Move( Square );
 338 #ifdef TICTACTOE_STDOUT
 339         if ( aStdOut.Len() )
 340         {
 341             puts( aStdOut.GetBuffer() );
 342             aStdOut.Erase();
 343         }
 344 #endif
 345         W = Winner();
 346     }
 347     if ( W == Empty )
 348     {
 349         if ( aPlayer == Human )
 350             PromptHuman();
 351     }
 352     else
 353     {
 354         if (W != 'C')
 355         {
 356             aStdOut += static_cast< char >(W);
 357             aStdOut += " wins!";
 358         }
 359         else
 360             aStdOut += "It's a tie.";
 361     }
 362     return W;
 363 }
 364
 365
 366 void ScTicTacToe::PromptHuman()
 367 {
 368     aStdOut += "Move #";
 369     aStdOut += ByteString::CreateFromInt32( nMove );
 370     aStdOut += " - What is X's move?";
 371 }
 372
 373
 374 #ifdef TICTACTOE_SC
 375
 376 void ScTicTacToe::DrawPos( int nSquare, const String& rStr )
 377 {
 378     pDoc->SetString( sal::static_int_cast<SCCOL>( aPos.Col()+(nSquare%3) ),
 379         sal::static_int_cast<SCROW>( aPos.Row()+(nSquare/3) ), aPos.Tab(), rStr );
 380 }
 381
 382
 383 void ScTicTacToe::DrawBoard()
 384 {
 385     String aStr;
 386     for ( USHORT j = 0; j < ScTicTacToe_Squares; j++ )
 387     {
 388         aStr = Board[j];
 389         DrawPos( j, aStr );
 390     }
 391 }
 392
 393
 394 // -1 == Fehler/Redraw, 0 == keine Aenderung, >0 == UserMoveSquare+1
 395 int ScTicTacToe::GetStatus()
 396 {
 397     SCCOL nCol;
 398     SCROW nRow;
 399     SCTAB nTab;
 400     nCol = aPos.Col();
 401     nRow = aPos.Row();
 402     nTab = aPos.Tab();
 403     String aStr;
 404     int nDiffs = 0;
 405     int nSquare = 0;
 406     for ( USHORT j = 0; j < ScTicTacToe_Squares; j++ )
 407     {
 408         pDoc->GetString( nCol+(j%3), nRow+(j/3), nTab, aStr );
 409         if ( !aStr.Len() )
 410         {
 411             if ( Board[j] != Empty )
 412                 return -1;                      // wo was sein muss muss was sein
 413         }
 414         else
 415         {
 416             aStr.ToUpperAscii();
 417             if ( aStr.GetChar(0) != Board[j] )
 418             {
 419                 if ( Board[j] != Empty )
 420                     return -1;          // bestehendes ueberschrieben
 421                                     // bei erstem Move hat Human angefangen
 422                 if ( ++nDiffs > 1 )
 423                     return -1;          // mehr als eine Aenderung
 424                 nSquare = j;
 425             }
 426         }
 427     }
 428     if ( nDiffs == 1 )
 429         return nSquare + 1;
 430     return 0;
 431 }
 432
 433
 434 Square_Type ScTicTacToe::CalcMove()
 435 {
 436     Square_Type W = Winner();
 437     int nStat = GetStatus();
 438     if ( nStat || (W == Empty && aPlayer == Compi) )
 439     {
 440         if ( nStat == -1 || (nStat > 0 && aPlayer == Compi) )
 441             DrawBoard();
 442         if ( W == Empty && aPlayer == Human )
 443         {
 444             if ( nStat > 0 )
 445             {
 446                 int nSquare = --nStat;
 447                 W = TryMove( nStat );
 448                 if ( nStat == -1 )
 449                     DrawPos( nSquare, String( ' ' ) );
 450                 else
 451                     DrawPos( nStat, String( Human ) );
 452             }
 453             else
 454                 PromptHuman();
 455         }
 456         if ( W == Empty && aPlayer == Compi )
 457         {
 458             W = TryMove( nStat );               // ComputerMove, nStat egal
 459             DrawPos( nStat, String( Compi ) );
 460         }
 461     }
 462     else if ( W == Empty && aPlayer == Human )
 463         PromptHuman();
 464     return W;
 465 }
 466
 467 #endif // TICTACTOE_SC
 468
 469
 470 #ifdef TICTACTOE_STDOUT
 471 /* Print the board */
 472 void ScTicTacToe::Print()
 473 {
 474     int i;
 475     for (i = 0; i < ScTicTacToe_Squares; i += 3)
 476     {
 477         if (i > 0)
 478             printf("---+---+---\n");
 479         printf(" %c | %c | %c \n", Board[i], Board[i + 1], Board[i + 2]);
 480     }
 481     printf("\n");
 482 }
 483
 484
 485 /* Play a game of tic-tac-toe */
 486 void ScTicTacToe::Game()
 487 {
 488     if ( !bInitialized )
 489         Initialize( FALSE );
 490
 491     int Square = (aPlayer == Compi ? 0 : -1);
 492     Square_Type W = Winner();
 493     while( W == Empty )
 494     {
 495         Print();
 496         W = TryMove( Square );
 497         if ( W == Empty )
 498         {
 499             if ( aPlayer == Human )
 500             {
 501                 if ( Square != -1 )
 502                     Print();    // empty board already printed if human moves first
 503                 do
 504                 {
 505                     puts( aStdOut.GetBuffer() );
 506                     aStdOut.Erase();
 507                     scanf("%d", &Square);
 508                     Square--;
 509                     W = TryMove( Square );
 510                 } while ( Square == -1 );
 511             }
 512         }
 513     }
 514     Print();
 515     puts( aStdOut.GetBuffer() );
 516     aStdOut.Erase();
 517 }
 518 #endif  // TICTACTOE_STDOUT
 519
 520
 521 #ifdef TICTACTOE_MAIN
 522 int main()
 523 {
 524     char Answer[80];
 525
 526     printf("Welcome to Tic-Tac-Toe!\n\n");
 527     printf("Here is the board numbering:\n");
 528     printf(" 1 | 2 | 3\n");
 529     printf("---+---+---\n");
 530     printf(" 4 | 5 | 6\n");
 531     printf("---+---+---\n");
 532     printf(" 7 | 8 | 9\n");
 533     printf("\n");
 534 //    printf("Computer plays X, you play O.\n");
 535
 536     ScTicTacToe aTTT;
 537     ByteString aStr;
 538     aTTT.GetOutput( aStr );
 539     puts( aStr.GetBuffer() );
 540
 541     do
 542     {
 543         printf("\nDo you want to move first? ");
 544         scanf("%s", Answer);
 545         aTTT.Initialize( toupper(Answer[0]) == 'Y' );
 546         aTTT.Game();
 547         printf("\nDo you want to play again? ");
 548         scanf("%s", Answer);
 549     } while (toupper(Answer[0]) == 'Y');
 550
 551     return 0;
 552 }
 553 #endif  // TICTACTOE_MAIN
 554