在 C/C++ Tutorial, Goal-Oriented Style (2) 中，有一個問題是如何用遞迴 (Recursive) 算出井字遊戲下一步。如果對遞迴邏輯覺得有困難，請參考下面的 C Style 的解答 (no object-oriented at all!)。
- 最重要的是 get_score() 這個 function，它是遞迴的主體，pseudo-code 可以見第二章的說明。
- 在 function parameter 前加上 const，表示該變數不會被 function 改變，是給 compiler 做安全檢查用的。
- 在 function parameter 加上 & 是 pass-by-reference，參考第二章
#include <string>
#include <iostream>
#include <vector>
const int EMPTY = 0;
const int COMPUTER = 1;
const int PLAYER = 2;
// vector board
//
// 1 2 3
// 4 5 6
// 7 8 9
//
// layer is from 1 to 9
int g_weight[10] = { 0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1 };
// draw board
void draw( const std::vector<int>& board );
// return COMPUTER / PLAYER / EMPTY (if no one wins)
int check_winner( const std::vector<int>& board );
// return true if all slots are filled, else false
bool is_all_filled( const std::vector<int>& board );
// recommand a next move based on current board
int get_move( const std::vector<int>& board );
// get a 'score' based on the board and the next move
// 'who' is PLAYER or COMPUTER
// 'where' is from 1 ~ 9
int get_score( const std::vector<int>& board, int who, int where );
int main()
{
char y_or_n;
int move;
// init a vector with 10 slots (index 0 ~ 9) filled with EMPTY (0)
std::vector<int> board( 10, EMPTY );
std::cout << "Do you want to go first? (y/N)" << std::endl;
std::cin >> y_or_n;
// check if user want to move first, if so, get his/her move
if ( y_or_n == 'Y' || y_or_n == 'y' )
{
draw( board );
std::cout << "Gimme your move (1~9): " << std::endl;
std::cin >> move;
if ( move <= 0 || move >= 10 )
{
std::cout << "Bad move, I don't wanna handle such error." << std::endl;
return -1;
}
board[move] = PLAYER;
}
draw( board );
while ( true )
{
bool first_trial;
int best_move, best_score;
// get the computer's best move based on score
first_trial = true;
for ( int i = 1; i <= 9; i ++ )
{
if ( board[i] != EMPTY )
{
continue;
}
int score;
std::vector next_board( board );
next_board[i] = COMPUTER;
score = get_score( next_board, COMPUTER, i );
if ( first_trial )
{
best_score = score;
best_move = i;
first_trial = false;
}
else if ( score > best_score )
{
best_score = score;
best_move = i;
}
}
// do the best move and get user's move
board[best_move] = COMPUTER;
draw( board );
if ( check_winner( board ) == COMPUTER )
{
std::cout << "COMPUTER WINS!" << std::endl;
return 0;
}
// check if draw
if ( is_all_filled( board ))
{
std::cout << "DRAW!" << std::endl;
return 0;
}
// get user's move
std::cout << "Gimme your move (1~9): " << std::endl; std::cin >> move;
if ( move <= 0 || move >= 10 )
{
std::cout << "Bad move, I don't wanna handle such error." << std::endl;
return -1;
}
board[move] = PLAYER;
draw( board );
if ( check_winner( board ) == PLAYER )
{
std::cout << "PLAYER WINS!" << std::endl;
return 0;
}
else if ( is_all_filled ( board ) )
{
draw( board );
std::cout << "DRAW!" << std::endl;
}
}
return 0;
}
int get_score( const std::vector<int>& pre_board, int who, int where )
{
bool no_more_slot = true;
int next_who;
int score = 0;
int layer = 0;
std::vector<int> board( pre_board );
board[where] = who;
// check current 'layer', i.e. how many slots are filled
for ( int i = 1; i <= 9; i ++ )
{
if ( board[i] != EMPTY )
{
layer ++;
}
}
// check if there is already an winner
if ( check_winner( board ) == COMPUTER )
{
return 1 * g_weight[layer];
}
else if ( check_winner( board ) == PLAYER )
{
return -1 * g_weight[layer];
}
// check if no more move
for ( int i = 0; i <= 9; i ++ )
{
if ( board[i] != EMPTY )
{
no_more_slot = false;
break;
}
}
// draw!
if ( no_more_slot )
{
return 0;
}
// check who move next
if ( who == PLAYER )
{
next_who = COMPUTER;
}
else
{
next_who = PLAYER;
}
// generate all possible board for the next step, then
// sum up the score all of the possible board
for ( int i = 1; i <= 9; i ++ )
{
if ( board[i] != EMPTY )
{
continue;
}
std::vector<int> next_board( board );
next_board[i] = next_who;
score = score + get_score( next_board, next_who, i );
}
return score;
}
// return true if all slots are filled, else false
bool is_all_filled( const std::vector<int>& board )
{
for ( int i = 0; i <= 9; i ++ )
{
if ( board[i] != EMPTY )
{
return false;
}
}
return true;
}
int check_winner( const std::vector<int>& board )
{
// check play a
if ( board[1] == COMPUTER && board[2] == COMPUTER && board[3] == COMPUTER ) {
return COMPUTER;
}
if ( board[4] == COMPUTER && board[5] == COMPUTER && board[6] == COMPUTER ) {
return COMPUTER;
}
if ( board[7] == COMPUTER && board[8] == COMPUTER && board[9] == COMPUTER ) {
return COMPUTER;
}
if ( board[1] == COMPUTER && board[4] == COMPUTER && board[7] == COMPUTER ) {
return COMPUTER;
}
if ( board[2] == COMPUTER && board[5] == COMPUTER && board[8] == COMPUTER ) {
return COMPUTER;
}
if ( board[3] == COMPUTER && board[6] == COMPUTER && board[9] == COMPUTER ) {
return COMPUTER;
}
if ( board[1] == COMPUTER && board[5] == COMPUTER && board[9] == COMPUTER ) {
return COMPUTER;
}
if ( board[3] == COMPUTER && board[5] == COMPUTER && board[7] == COMPUTER ) {
return COMPUTER;
}
// check play b
if ( board[1] == PLAYER && board[2] == PLAYER && board[3] == PLAYER ) {
return PLAYER;
}
if ( board[4] == PLAYER && board[5] == PLAYER && board[6] == PLAYER ) {
return PLAYER;
}
if ( board[7] == PLAYER && board[8] == PLAYER && board[9] == PLAYER ) {
return PLAYER;
}
if ( board[1] == PLAYER && board[4] == PLAYER && board[7] == PLAYER ) {
return PLAYER;
}
if ( board[2] == PLAYER && board[5] == PLAYER && board[8] == PLAYER ) {
return PLAYER;
}
if ( board[3] == PLAYER && board[6] == PLAYER && board[9] == PLAYER ) {
return PLAYER;
}
if ( board[1] == PLAYER && board[5] == PLAYER && board[9] == PLAYER ) {
return PLAYER;
}
if ( board[3] == PLAYER && board[5] == PLAYER && board[7] == PLAYER ) {
return PLAYER;
}
return EMPTY;
}
// draw board
void draw( const std::vector<int>& board )
{
std::cout << std::endl;
std::cout << "COMPUTER(1) vs PLAYER(2)" << std::endl;
std::cout << board[1] << " " << board[2] << " " << board[3] << std::endl;
std::cout << board[4] << " " << board[5] << " " << board[6] << std::endl;
std::cout << board[7] << " " << board[8] << " " << board[9] << std::endl;
std::cout << std::endl;
}