Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 6: Đệ quy

ước đi của trò chơi được nhìn trước với độ sâu là depth, nước đi tốt nhất được chỉ ra 
trong tham biến recommended. 
uses: các lớp Stack, Board, và Move, cùng với hàm look_ahead một cách đệ quy. 
*/ 
Algorithm look_ahead (thông số là một đối tượng Board); 
1. if đệ quy dừng (độ sâu depth == 0 hoặc game.done()) 
 1. return trị lượng giá của tình huống 
2. else 
 1. for mỗi nước đi Move hợp lệ 
 1. tạo một đối tượng Board mới bằng cách thực hiện nước đi Move. 
 2. gọi đệ quy look_ahead tương ứng với sự lựa chọn tốt nhất của 
người chơi kế tiếp; 
 2. Chọn cách đi tốt nhất cho người chơi trong số các cách đi tìm được 
trong vòng lặp trên; 
3. return đối tượng Move tương ứng và trị; 
Chương 6 – Đệ quy 
Giáo trình Cấu trúc dữ liệu và Giải thuật 132
{ 
 if (game.done() || depth == 0) 
 return game.evaluate(); 
 else { 
 Stack moves; 
 game.legal_moves(moves); 
 int value, best_value = game.worst_case(); 
 while (!moves.empty()) { 
 Move try_it, reply; 
 moves.top(try_it); 
 Board new_game = game; 
 new_game.play(try_it); 
 value = look_ahead(new_game, depth - 1, reply); 
 if (game.better(value, best_value)) { // nước đi thử try_it vừa rồi hiện 
là tốt nhất. 
 best_value = value; 
 recommended = try_it; 
 } 
 moves.pop(); 
 } 
 return best_value; 
 } 
} 
Tham biến recommended sẽ nhận về một nước đi được tiến cử (trừ khi đệ quy 
rơi vào điểm dừng, đó là khi trò chơi kết thúc hoặc độ sâu của việc nhìn trước 
depth bằng 0). Do chúng ta không muốn đối tượng game bị thay đổi trong hàm, đồng thời để 
tránh việc chép lại mất thời gian, nó được gởi cho hàm bằng tham chiếu hằng. Chúng ta cũng lưu 
ý rằng việc khai báo tham chiếu hằng này chỉ hợp lệ khi đối tượng game trong hàm chỉ thực hiện 
các phương thức đã được khai báo const trong định nghĩa của lớp Board. 
6.4.5. Tic-Tac-Toe 
Như trên đã nói, hàm đệ quy look_ahead cùng hai lớp Board và Move trên 
đây tuy rất đơn giản, nhưng nó lại là cốt lõi trong các chương trình biểu diễn trò 
chơi có hai đối thủ. Chúng ta sẽ triển khai phác thảo này trong trò chơi tic-tac-toe 
rất quen thuộc. Để làm được điều này, cả hai lớp sẽ chứa thêm một ít dữ liệu khác 
so với hiện thực hình thức ban đầu. 
Việc viết chương trình chính hoàn tất cùng hàm look_ahead cho trò chơi tic-
tac-toe được dành lại như bài tập. Chương trình có thể chứa thêm nhiều chức 
năng như cho phép người chơi với máy, đưa ra các phân tích đầy đủ cho mỗi tình 
huống, cung cấp chức năng cho hai người chơi với nhau, đánh giá các bước đi của 
hai đối thủ,... 
Chúng ta biểu diễn lưới trò chơi tic-tac-toe bằng một mảng 3x3 các số nguyên, 
ô có trị 0 là ô trống, trị 1 và 2 biểu diễn nước đi của người thứ nhất và thứ hai 
tương ứng. 
Chương 6 – Đệ quy 
Giáo trình Cấu trúc dữ liệu và Giải thuật 133
Trong đối tượng Move, chúng ta chứa tọa độ các ô trên lưới. Một nước đi hợp lệ 
chứa tọa độ có các trị từ 0 đến 2. Chúng ta không cần đến tính đóng kín của đối 
tượng Move vì nó chỉ như một vật chứa để chứa các giá trị. 
// lớp move cho trò chơi tic-tac-toe 
class Move { 
public: 
 Move(); 
 Move(int r, int c); 
 int row; 
 int col; 
}; 
Move::Move() 
/* 
post: đối tượng Move được khởi tạo bởi trị mặc định không hợp lệ. 
*/ 
{ 
 row = 3; 
 col = 3; 
} 
Move::Move(int r, int c) 
/* 
post: đối tượng Move được khởi tạo bởi toạ độ cho trước. 
*/ 
{ 
 row = r; 
 col = c; 
} 
Lớp Board cần một constructor để khởi tạo trò chơi, phương thức print và 
instruction (in các thông tin cho người chơi), phương thức done, play và 
legal_moves (hiện thực các quy tắc chơi), và các phương thức evaluate, 
better, và worst_case (phán đoán điểm cho các nước đi khác nhau). Chúng ta 
còn có thể bổ sung hàm phụ trợ the_winner cho biết rằng trò chơi đã có người 
thắng chưa và người thắng là ai. 
Lớp Board cần chứa thông tin về trạng thái hiện tại của trò chơi trong mảng 
3x3 và tổng số bước đi đã thực hiện. Chúng ta có lớp Board như sau: 
class Board { 
public: 
 Board(); 
 bool done() const; 
 void print() const; 
 void instructions() const; 
 bool better(int value, int old_value) const; 
 void play(Move try_it); 
 int worst_case() const; 
Chương 6 – Đệ quy 
Giáo trình Cấu trúc dữ liệu và Giải thuật 134
 int evaluate() const; 
 int legal_moves(Stack &moves) const; 
private: 
 int squares[3][3]; 
 int moves_done; 
 int the_winner() const; 
}; 
Constructor đơn giản chỉ làm một việc là khởi tạo tất cả các ô của mảng là 0 
để chỉ rằng cả hai người chơi đều chưa đi nước nào. 
Board::Board() 
/* 
post: đối tượng Board được khởi tạo rỗng tương ứng trạng thái ban đầu của trò chơi. 
*/ 
{ 
 for (int i = 0; i < 3; i++) 
 for (int j = 0; j < 3; j++) 
 squares[i][j] = 0; 
 moves_done = 0; 
} 
Chúng ta dành các phương thức in các thông tin cho người chơi như là bài tập. 
Thay vào đó, chúng ta tập trung vào các phương thức liên quan đến các quy tắc 
của trò chơi. Để thực hiện một nước đi, chúng ta chỉ cần gán lại trị cho một ô và 
tăng biến đếm moves_done lên 1. Dựa vào biến đếm này chúng ta còn biết được 
đến lượt người nào đi. 
void Board::play(Move try_it) 
/* 
post: nước đi try_it được thực hiện 
*/ 
{ 
 squares[try_it.row][try_it.col] = moves_done % 2 + 1; 
 moves_done++; 
} 
Hàm phụ trợ the_winner trả về một số khác không nếu đã có người thắng. 
int Board::the_winner() const 
/* 
post: trả về 0 nếu chưa ai thắng; 1 nếu người thứ nhất thắng; 2 nếu người thứ hai thắng. 
*/ 
{ 
 int i; 
 for (i = 0; i < 3; i++) 
 if (squares[i][0] && squares[i][0] == squares[i][1] 
 && squares[i][0] == squares[i][2]) 
 return squares[i][0]; 
 for (i = 0; i < 3; i++) 
 if (squares[0][i] && squares[0][i] == squares[1][i] 
 && squares[0][i] == squares[2][i]) 
 return squares[0][i]; 
Chương 6 – Đệ quy 
Giáo trình Cấu trúc dữ liệu và Giải thuật 135
 if (squares[0][0] && squares[0][0] == squares[1][1] 
 && squares[0][0] == squares[2][2]) 
 return squares[0][0]; 
 if (squares[0][2] && squares[0][2] == squares[1][1] 
 && squares[2][0] == squares[0][2]) 
 return squares[0][2]; 
 return 0; 
} 
Trò chơi kết thúc sau 9 nước đi hoặc khi có người thắng. (Chương trình của chúng ta không 
phát hiện sớm khả năng hòa trước khi kết thúc 9 nước đi). 
bool Board::done() const 
/* 
post: trả về true nếu trò chơi đã phân thắng bại hoặc cả 9 ô trên bàn cờ đã được đánh dấu, 
ngược lại trả về false. 
*/ 
{ 
 return moves_done == 9 || the_winner() > 0; 
} 
Trong trò chơi đơn giản này, nước đi hợp lệ là những ô mang trị 0. 
int Board::legal_moves(Stack &moves) const 
/* 
post: Thông số moves chứa các nước đi hợp lệ. 
*/ 
{ 
 int count = 0; 
 while (!moves.empty()) moves.pop(); 
 for (int i = 0; i < 3; i++) 
 for (int j = 0; j < 3; j++) 
 if (squares[i][j] == 0) { 
 Move can_play(i,j); 
 moves.push(can_play); 
 count++; 
 } 
 return count; 
} 
Chúng ta chuyển sang các phương thức có thể cho những sự đánh giá về một 
tình huống của trò chơi hoặc của một nước đi có thể xảy ra. Chúng ta sẽ bắt đầu 
đánh giá một tình huống của trò chơi là 0 trong trường hợp chưa có người nào 
thắng. Nếu một trong hai người thắng, chúng ta sẽ đánh giá tình huống dựa vào 
quy tắc: càng thắng nhanh thì càng hay. Điều này cũng đồng nghĩa với việc càng 
thua nhanh thì càng dở. Nếu moves_done là số nước đi cả hai người chơi đã thực 
hiện thì (10-moves_done) càng lớn khi số nước đã đi càng nhỏ, tương ứng sự 
đánh giá cao khi người thứ nhất sớm thắng. Ngược lại, nếu người thứ hai thắng 
thì chúng ta dùng trị (moves_done-10), số nước đi càng nhỏ thì trị này là một 
số càng âm, tương ứng việc thua nhanh chóng của người thứ nhất là rất dở. 
Chương 6 – Đệ quy 
Giáo trình Cấu trúc dữ liệu và Giải thuật 136
Dĩ nhiên rằng, cách đánh giá này chỉ được áp lên điểm cuối của việc nhìn 
trước (ở độ sâu mong muốn hoặc khi trò chơi đã phân thắng bại). Trong phần lớn 
các tình huống, nếu chúng ta nhìn trước càng xa thì bản chất chưa tinh của cách 
đánh giá sẽ đỡ gây hậu quả xấu hơn. 
int Board::evaluate() const 
/* 
post: trả về 0 khi chưa có người thắng cuộc; hoăc 1 số dương từ 1 đến 9 trong trường hợp người 
thứ nhất thắng, ngược lại là một số âm từ –1 đến –9 trong trường hợp người thứ hai 
thắng. 
*/ 
{ 
 int winner = the_winner(); 
 if (winner == 1) return 10 - moves_done; 
 else if (winner == 2) return moves_done - 10; 
 else return 0; 
} 
Phương thức worst_case có thể chỉ đơn giản trả về một trong hai trị 10 hoặc 
-10, do evaluate luôn trả một trị nằm giữa -9 và 9. Từ đó, phương thức so sánh 
better chỉ cần so sánh một cặp số nguyên có trị nằm giữa -10 và 10. Các phương 
thức này xem như bài tập. 
Giờ thì chúng ta đã phác thảo xong phần lớn chương trình trò chơi tic-tac-toe. 
Một chương trình lấy độ sâu cho việc nhìn trước là 9 sẽ chơi tốt do chúng ta luôn 
có thể nhìn trước đến một tình huống mà sự đánh giá về nó là chính xác. Một 
chương trình nhìn trước với một độ sâu không lớn có thể mắc phải sai lầm, do nó 
có thể kết thúc việc nhìn trước bởi tập các tình huống có trị đánh giá bằng 0 một 
cách nhầm lẫn.