Trong bài này chúng ta sẽ làm game caro C++ trên bàn 10×10, người chơi đấu với máy, ai có 5 quân liên tiếp trước là thắng. Phần thú vị nhất là “bộ não” của máy: thuật toán minimax để máy tự tính trước các nước đi, và cắt tỉa alpha-beta để bỏ qua những nhánh không cần xét. Đây là cùng ý tưởng mà các chương trình cờ vua kinh điển đã dùng.
Bài 39 trong Serie Lập trình C++ từ A tới Z
Yêu cầu của chương trình
- Bàn cờ 10×10 in ra console, người chơi cầm X đi trước, nhập nước đi dạng
hang cot. - Kiểm tra nước đi hợp lệ, kiểm tra thắng khi có 5 quân liên tiếp theo hàng ngang, hàng dọc hoặc đường chéo.
- Máy cầm O, tự chọn nước đi trong thời gian ngắn, biết chặn khi người chơi sắp thắng và biết tấn công.
Phần 1 và 2 chỉ là mảng 2 chiều và vòng lặp. Phần 3 cần một thuật toán, nên chúng ta học thuật toán trên bàn 3×3 trước rồi mới áp dụng cho bàn 10×10.
Thuật toán minimax
Ý tưởng của minimax giống cách người chơi cờ suy nghĩ: “nếu mình đi nước này, đối thủ sẽ đáp lại nước tốt nhất cho họ, rồi mình lại đi nước tốt nhất cho mình…”. Máy thử mọi nước đi, với mỗi nước lại thử mọi nước đáp trả, tạo thành một cây các thế cờ.
- Mỗi thế cờ cuối được chấm điểm theo góc nhìn của máy: máy thắng là +1, hòa là 0, người thắng là -1.
- Ở tầng lượt máy (MAX), máy chọn nước có điểm lớn nhất.
- Ở tầng lượt người (MIN), máy giả định người chơi đi nước có điểm nhỏ nhất, tức nước tệ nhất cho máy.
Điểm được truyền ngược từ lá lên gốc, và nước ở gốc có điểm cao nhất chính là nước máy chọn. Máy không trông chờ người chơi đi sai, nó luôn giả định người chơi đi đúng.
Cắt tỉa alpha-beta
Nhìn cây ở trên: nhánh trái cho máy điểm 3. Sang nhánh phải, lá đầu tiên đã là 2. Vì tầng MIN chọn điểm nhỏ nhất, nhánh phải chắc chắn chỉ có điểm 2 trở xuống, tệ hơn 3 mà máy đã có. Vậy hai lá còn lại của nhánh phải không cần xét nữa, dù chúng là bao nhiêu thì máy cũng không chọn nhánh này.
Đó là cắt tỉa alpha-beta. Khi duyệt cây, thuật toán mang theo 2 giá trị:
- alpha: điểm tốt nhất mà máy (MAX) đã chắc chắn có được.
- beta: điểm tốt nhất mà người (MIN) đã chắc chắn có được, tức điểm thấp nhất họ ép được máy.
Khi alpha >= beta thì nhánh đang xét không bao giờ được chọn, dừng duyệt nhánh đó. Kết quả cuối cùng giống hệt minimax, chỉ nhanh hơn.
Minimax trên cờ 3×3
Thử trước trên cờ 3×3 (tic-tac-toe), bàn nhỏ đủ để duyệt hết toàn bộ cây. Chương trình chạy cả minimax thường và alpha-beta, đếm số thế cờ đã xét:
#include <algorithm>
#include <array>
#include <iostream>
using BanCo = std::array<char, 9>; // 3x3, '.' la o trong
long long soNut = 0; // dem so the co da xet
char nguoiThang(const BanCo& b)
{
static const int duong[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
{1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};
for (const auto& d : duong)
if (b[d[0]] != '.' && b[d[0]] == b[d[1]] && b[d[1]] == b[d[2]])
return b[d[0]];
return 0;
}
// May cam O, muon diem cao nhat. Nguoi cam X, muon diem thap nhat.
// +1: may thang, -1: nguoi thang, 0: hoa
int minimax(BanCo& b, bool luotMay)
{
soNut++;
char thang = nguoiThang(b);
if (thang == 'O') return 1;
if (thang == 'X') return -1;
if (std::count(b.begin(), b.end(), '.') == 0) return 0;
int tot = luotMay ? -2 : 2;
for (int i = 0; i < 9; i++)
{
if (b[i] != '.')
continue;
b[i] = luotMay ? 'O' : 'X'; // thu di
int diem = minimax(b, !luotMay);
b[i] = '.'; // tra lai ban co
tot = luotMay ? std::max(tot, diem) : std::min(tot, diem);
}
return tot;
}
int alphaBeta(BanCo& b, bool luotMay, int alpha, int beta)
{
soNut++;
char thang = nguoiThang(b);
if (thang == 'O') return 1;
if (thang == 'X') return -1;
if (std::count(b.begin(), b.end(), '.') == 0) return 0;
int tot = luotMay ? -2 : 2;
for (int i = 0; i < 9; i++)
{
if (b[i] != '.')
continue;
b[i] = luotMay ? 'O' : 'X';
int diem = alphaBeta(b, !luotMay, alpha, beta);
b[i] = '.';
if (luotMay)
{
tot = std::max(tot, diem);
alpha = std::max(alpha, tot);
}
else
{
tot = std::min(tot, diem);
beta = std::min(beta, tot);
}
if (alpha >= beta) // doi thu se khong de nhanh nay xay ra
break;
}
return tot;
}
int main()
{
BanCo trong;
trong.fill('.');
soNut = 0;
int kq = minimax(trong, false);
std::cout << "Ban trong, X di truoc. Minimax: ket qua " << kq << ", xet " << soNut << " the co\n";
soNut = 0;
kq = alphaBeta(trong, false, -2, 2);
std::cout << "Ban trong, X di truoc. Alpha-beta: ket qua " << kq << ", xet " << soNut << " the co\n\n";
BanCo b = {'X', '.', '.',
'.', 'O', '.',
'.', '.', 'X'};
std::cout << "X . .\n. O .\n. . X Luot may (O), diem tung nuoc:\n";
for (int i = 0; i < 9; i++)
{
if (b[i] != '.')
continue;
b[i] = 'O';
int diem = alphaBeta(b, false, -2, 2);
b[i] = '.';
std::cout << " O vao o " << i << " (hang " << i / 3 << ", cot " << i % 3 << "): " << diem << '\n';
}
return 0;
}
Hàm minimax là đệ quy: thử đặt quân vào từng ô trống, gọi chính nó với lượt của bên kia, rồi trả lại ô trống trước khi thử ô tiếp theo. Cách “thử rồi trả lại” này giúp dùng chung một bàn cờ, không phải sao chép bàn cờ ở mỗi tầng. Hàm alphaBeta giống hệt, chỉ thêm alpha, beta và lệnh break khi cắt tỉa.
- Cả hai cách đều cho kết quả 0: cờ 3×3 nếu hai bên đều chơi đúng thì luôn hòa.
- Minimax xét 549.946 thế cờ, alpha-beta chỉ xét 18.297, ít hơn khoảng 30 lần mà kết quả như nhau.
- Ở thế cờ X đi 2 góc đối nhau, máy chấm điểm -1 cho 2 nước đánh vào góc: nếu O đánh góc, X sẽ đánh góc còn lại, tạo 2 đường thắng cùng lúc và O không chặn kịp. Nước đúng là đánh vào cạnh, và máy tự tìm ra điều này mà không ai dạy.
Từ 3×3 lên bàn caro 10×10
Bàn 10×10 có 100 ô, cây trò chơi lớn tới mức máy tính nào cũng không duyệt hết được. Phải thêm 3 thay đổi:
- Giới hạn độ sâu: chỉ tính trước 3 nước (máy, người, máy) rồi dừng.
- Hàm đánh giá: thế cờ ở độ sâu 3 thường chưa phân thắng thua, nên cần một hàm “ước lượng” xem thế cờ đang có lợi cho ai.
- Chỉ xét nước hợp lý: không thử cả 100 ô mà chỉ thử các ô sát quân đã đánh, sắp xếp ô hứa hẹn lên trước để alpha-beta cắt tỉa được nhiều hơn.
Hàm đánh giá thế cờ
Mình dùng cách “cửa sổ 5 ô”: xét mọi đoạn 5 ô liên tiếp trên bàn theo 4 hướng (ngang, dọc, 2 đường chéo). Đoạn nào chỉ có quân O thì cộng điểm cho máy, chỉ có quân X thì trừ, có cả hai thì bỏ qua vì đoạn đó không ai làm 5 được nữa.
// Diem cua ban co nhin tu phia may (O): duong la may loi, am la nguoi loi
int danhGia(const BanCo& b) const
{
static const int DIEM[6] = {0, 1, 10, 100, 1000, 100000}; // theo so quan trong 1 cua so 5 o
int tong = 0;
for (int h = 0; h < N; h++)
for (int c = 0; c < N; c++)
for (const auto& d : HUONG)
{
int hCuoi = h + 4 * d[0], cCuoi = c + 4 * d[1];
if (hCuoi < 0 || hCuoi >= N || cCuoi < 0 || cCuoi >= N)
continue;
int may = 0, nguoi = 0;
for (int k = 0; k < 5; k++)
{
char q = b.at(h + k * d[0], c + k * d[1]);
may += q == 'O';
nguoi += q == 'X';
}
if (may > 0 && nguoi == 0)
tong += DIEM[may];
else if (nguoi > 0 && may == 0)
tong -= DIEM[nguoi] * 2; // uu tien chan doi thu
}
return tong;
}
- Điểm tăng gấp 10 theo số quân trong đoạn: 1 quân được 1 điểm, 4 quân được 1000. Một đoạn 4 quân đáng giá hơn nhiều đoạn 2 quân cộng lại.
- Quân của người bị nhân 2: máy ưu tiên chặn đối thủ hơn là tự tấn công, vì để người chơi có 4 quân là thua.
DIEMcó 6 phần tử cho đủ trường hợp 0 tới 5 quân. Lúc đầu mình khai báo mảng 5 phần tử, quên trường hợp đủ 5 quân O: truy cậpDIEM[5]vượt mảng. Chương trình không crash, máy chỉ thỉnh thoảng bỏ lỡ nước thắng ngay trước mắt, và khi biên dịch với tùy chọn khác thì lỗi lại biến mất, vì đây là hành vi không xác định. Chạy thử bằng mắt rất khó thấy, nhưng biên dịch thêm-fsanitize=undefinedthì chương trình báo ngayindex 5 out of bounds for type 'int [5]'.
Chọn các nước đáng xét
// Chi xet o trong nam sat (cach 1 o) mot quan da danh, sap xep o tot truoc
std::vector<NuocDi> ungVien(BanCo& b, char quan)
{
std::vector<std::pair<int, NuocDi>> ds;
for (int h = 0; h < N; h++)
for (int c = 0; c < N; c++)
{
if (!b.trong(h, c) || !gan(b, h, c))
continue;
b.dat({h, c}, quan);
int diem = danhGia(b);
b.xoa({h, c});
ds.push_back({quan == 'O' ? diem : -diem, {h, c}});
}
std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.first > b.first; });
std::vector<NuocDi> kq;
for (const auto& p : ds)
kq.push_back(p.second);
if (kq.size() > 12)
kq.resize(12); // chi giu 12 nuoc hua hen nhat
return kq;
}
Chỉ những ô trống nằm sát (cách 1 ô) một quân đã có mới là ứng viên. Mỗi ứng viên được thử đặt quân và chấm điểm nhanh bằng danhGia, sắp xếp giảm dần rồi chỉ giữ 12 nước tốt nhất. Thứ tự này rất quan trọng với alpha-beta: xét nước tốt trước thì alpha tăng sớm, các nhánh sau bị cắt nhiều hơn.
Lưu ý: Giữ 12 nước là một sự đánh đổi. Bỏ bớt nước giúp máy nhanh hơn rất nhiều, nhưng nếu nước hay nhất lại bị hàm đánh giá chấm thấp thì máy sẽ không bao giờ thấy nó. Hầu hết chương trình chơi cờ đều phải cân bằng giữa tốc độ và độ chính xác như vậy.
Alpha-beta có giới hạn độ sâu
int alphaBeta(BanCo& b, int doSau, int alpha, int beta, bool luotMay)
{
soNut_++;
if (doSau == 0)
return danhGia(b);
char quan = luotMay ? 'O' : 'X';
std::vector<NuocDi> dsNuoc = ungVien(b, quan);
if (dsNuoc.empty())
return 0; // het cho danh: hoa
int tot = luotMay ? -THANG * 2 : THANG * 2;
for (NuocDi n : dsNuoc)
{
b.dat(n, quan);
int diem;
if (b.thang(n))
diem = luotMay ? THANG + doSau : -THANG - doSau; // thang cang som cang tot
else
diem = alphaBeta(b, doSau - 1, alpha, beta, !luotMay);
b.xoa(n);
if (luotMay)
{
tot = std::max(tot, diem);
alpha = std::max(alpha, tot);
}
else
{
tot = std::min(tot, diem);
beta = std::min(beta, tot);
}
if (alpha >= beta)
break;
}
return tot;
}
So với bản 3×3 có 3 điểm khác:
- Hết độ sâu (
doSau == 0) thì trả về điểm của hàm đánh giá thay vì đi tiếp. - Nước vừa đi tạo thành 5 quân thì dừng ngay, trả về
THANGcộng thêmdoSau. Độ sâu còn lại càng lớn nghĩa là thắng càng sớm, nên máy ưu tiên thắng ngay thay vì kéo dài ván cờ. HàmchonNuocở gốc cũng phải dùng đúng quy tắc này: nếu gốc chỉ cho nước thắng ngayTHANGđiểm, nó sẽ thấp hơnTHANG + 1của một nước thắng ở lượt sau, và máy sẽ bỏ qua nước thắng ngay. - Kiểm tra thắng chỉ cần xét quanh nước vừa đi chứ không quét cả bàn: hàm
BanCo::thangđếm số quân cùng loại liên tiếp về 2 phía theo từng hướng.
Code đầy đủ game caro C++
#include <algorithm>
#include <chrono>
#include <iostream>
#include <limits>
#include <vector>
constexpr int N = 10; // ban co 10x10
constexpr int THANG = 1000000;
const int HUONG[4][2] = {{0, 1}, {1, 0}, {1, 1}, {1, -1}}; // ngang, doc, 2 duong cheo
struct NuocDi
{
int hang, cot;
};
class BanCo
{
public:
BanCo()
{
for (auto& h : o_)
std::fill(std::begin(h), std::end(h), '.');
}
bool trong(int h, int c) const { return h >= 0 && h < N && c >= 0 && c < N && o_[h][c] == '.'; }
char at(int h, int c) const { return o_[h][c]; }
void dat(NuocDi n, char quan) { o_[n.hang][n.cot] = quan; }
void xoa(NuocDi n) { o_[n.hang][n.cot] = '.'; }
// Nuoc vua di co tao thanh 5 quan lien tiep khong?
bool thang(NuocDi n) const
{
char quan = o_[n.hang][n.cot];
for (const auto& d : HUONG)
{
int dem = 1;
for (int chieu : {1, -1})
{
int h = n.hang + d[0] * chieu, c = n.cot + d[1] * chieu;
while (h >= 0 && h < N && c >= 0 && c < N && o_[h][c] == quan)
{
dem++;
h += d[0] * chieu;
c += d[1] * chieu;
}
}
if (dem >= 5)
return true;
}
return false;
}
void in() const
{
std::cout << " ";
for (int c = 0; c < N; c++)
std::cout << c << ' ';
std::cout << '\n';
for (int h = 0; h < N; h++)
{
std::cout << ' ' << h << ' ';
for (int c = 0; c < N; c++)
std::cout << o_[h][c] << ' ';
std::cout << '\n';
}
}
private:
char o_[N][N];
};
class MayChoi
{
public:
explicit MayChoi(int doSau) : doSau_(doSau) {}
NuocDi chonNuoc(BanCo& b)
{
soNut_ = 0;
NuocDi tot = {N / 2, N / 2};
int diemTot = std::numeric_limits<int>::min();
int alpha = -THANG * 2, beta = THANG * 2;
for (NuocDi n : ungVien(b, 'O'))
{
b.dat(n, 'O');
int diem = b.thang(n) ? THANG + doSau_ : alphaBeta(b, doSau_ - 1, alpha, beta, false);
b.xoa(n);
if (diem > diemTot)
{
diemTot = diem;
tot = n;
}
alpha = std::max(alpha, diem);
}
return tot;
}
long long soNut() const { return soNut_; }
private:
// Diem cua ban co nhin tu phia may (O): duong la may loi, am la nguoi loi
int danhGia(const BanCo& b) const
{
static const int DIEM[6] = {0, 1, 10, 100, 1000, 100000}; // theo so quan trong 1 cua so 5 o
int tong = 0;
for (int h = 0; h < N; h++)
for (int c = 0; c < N; c++)
for (const auto& d : HUONG)
{
int hCuoi = h + 4 * d[0], cCuoi = c + 4 * d[1];
if (hCuoi < 0 || hCuoi >= N || cCuoi < 0 || cCuoi >= N)
continue;
int may = 0, nguoi = 0;
for (int k = 0; k < 5; k++)
{
char q = b.at(h + k * d[0], c + k * d[1]);
may += q == 'O';
nguoi += q == 'X';
}
if (may > 0 && nguoi == 0)
tong += DIEM[may];
else if (nguoi > 0 && may == 0)
tong -= DIEM[nguoi] * 2; // uu tien chan doi thu
}
return tong;
}
// Chi xet o trong nam sat (cach 1 o) mot quan da danh, sap xep o tot truoc
std::vector<NuocDi> ungVien(BanCo& b, char quan)
{
std::vector<std::pair<int, NuocDi>> ds;
for (int h = 0; h < N; h++)
for (int c = 0; c < N; c++)
{
if (!b.trong(h, c) || !gan(b, h, c))
continue;
b.dat({h, c}, quan);
int diem = danhGia(b);
b.xoa({h, c});
ds.push_back({quan == 'O' ? diem : -diem, {h, c}});
}
std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.first > b.first; });
std::vector<NuocDi> kq;
for (const auto& p : ds)
kq.push_back(p.second);
if (kq.size() > 12)
kq.resize(12); // chi giu 12 nuoc hua hen nhat
return kq;
}
bool gan(const BanCo& b, int h, int c) const
{
for (int dh = -1; dh <= 1; dh++)
for (int dc = -1; dc <= 1; dc++)
{
int hh = h + dh, cc = c + dc;
if (hh >= 0 && hh < N && cc >= 0 && cc < N && b.at(hh, cc) != '.')
return true;
}
return false;
}
int alphaBeta(BanCo& b, int doSau, int alpha, int beta, bool luotMay)
{
soNut_++;
if (doSau == 0)
return danhGia(b);
char quan = luotMay ? 'O' : 'X';
std::vector<NuocDi> dsNuoc = ungVien(b, quan);
if (dsNuoc.empty())
return 0; // het cho danh: hoa
int tot = luotMay ? -THANG * 2 : THANG * 2;
for (NuocDi n : dsNuoc)
{
b.dat(n, quan);
int diem;
if (b.thang(n))
diem = luotMay ? THANG + doSau : -THANG - doSau; // thang cang som cang tot
else
diem = alphaBeta(b, doSau - 1, alpha, beta, !luotMay);
b.xoa(n);
if (luotMay)
{
tot = std::max(tot, diem);
alpha = std::max(alpha, tot);
}
else
{
tot = std::min(tot, diem);
beta = std::min(beta, tot);
}
if (alpha >= beta)
break;
}
return tot;
}
int doSau_;
long long soNut_ = 0;
};
int main()
{
BanCo ban;
MayChoi may(3);
std::cout << "Co caro 10x10: ban (X) di truoc, 5 quan lien tiep la thang.\n";
ban.in();
for (int luot = 0; luot < N * N / 2; luot++)
{
int h, c;
std::cout << "Nuoc cua ban (hang cot): ";
if (!(std::cin >> h >> c))
return 0;
if (!ban.trong(h, c))
{
std::cout << "O khong hop le, nhap lai.\n";
luot--;
continue;
}
ban.dat({h, c}, 'X');
if (ban.thang({h, c}))
{
ban.in();
std::cout << "Ban thang!\n";
return 0;
}
auto batDau = std::chrono::steady_clock::now();
NuocDi n = may.chonNuoc(ban);
auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - batDau).count();
ban.dat(n, 'O');
std::cout << "May di " << n.hang << ' ' << n.cot << " (xet " << may.soNut() << " the co, " << ms << " ms)\n";
ban.in();
if (ban.thang(n))
{
std::cout << "May thang!\n";
return 0;
}
}
std::cout << "Hoa!\n";
return 0;
}
Class BanCo chỉ lo dữ liệu bàn cờ và luật thắng, class MayChoi lo thuật toán, hàm main lo nhập xuất. Muốn máy mạnh hơn chỉ cần tăng độ sâu MayChoi may(3) lên 4 hoặc 5, đổi lại máy nghĩ lâu hơn. Hàm main dùng std::chrono để in thời gian máy suy nghĩ mỗi nước.
Biên dịch và chơi thử
Biên dịch với -O2 để trình biên dịch tối ưu code, thuật toán tìm kiếm chạy nhanh hơn nhiều so với không tối ưu:
Mỗi nước máy chỉ xét khoảng 100–200 thế cờ và trả lời trong khoảng chục mili giây. Con số này nhỏ là nhờ giới hạn ứng viên và cắt tỉa, chứ không phải máy duyệt hết. Nhập một ký tự không phải số như q thì std::cin thất bại và chương trình thoát.
Một ván đầy đủ: người chơi mải dựng hàng X ở giữa bàn, không để ý máy đang xếp quân O theo đường chéo. Tới nước 7 3, máy đã có 4 quân O liên tiếp theo đường chéo và cả 2 đầu 3 7, 8 2 đều trống:
Ở nước cuối người chơi đi 5 4 mà không chặn, máy đánh 3 7 và thắng. Nhưng dù có chặn ô 3 7 thì máy vẫn thắng ở ô 8 2: “bốn mở hai đầu” là thế cờ không thể đỡ, người chơi đã thua từ lúc để máy có ba quân chéo mở hai đầu mà không chặn.
Hướng mở rộng
- Tăng độ sâu theo thời gian: bắt đầu với độ sâu 1, tăng dần cho tới khi hết 1 giây suy nghĩ, gọi là iterative deepening.
- Nhận diện thế cờ tốt hơn: hàm đánh giá hiện tại không phân biệt “ba mở hai đầu” với “ba bị chặn một đầu”. Thêm điểm riêng cho các thế này máy sẽ chơi mạnh hơn rõ rệt.
- Luật chặn hai đầu của caro Việt Nam: 5 quân bị chặn cả hai đầu thì không tính thắng. Chỉ cần sửa hàm
thang. - Giao diện đồ họa: kết hợp với SFML ở bài game rắn săn mồi, bấm chuột vào ô để đánh.
- Tách file:
ban_co.h,may_choi.h/.cpp,main.cppnhư project thư viện.
Kết
Game caro C++ có máy chơi là project rất hay để hiểu thuật toán tìm kiếm trong trò chơi: minimax thử các nước đi và giả định đối thủ luôn đi đúng, cắt tỉa alpha-beta bỏ những nhánh chắc chắn không được chọn mà kết quả vẫn y hệt. Với bàn cờ lớn, hàm đánh giá, giới hạn độ sâu và chọn lọc nước đi là những thứ quyết định máy chơi giỏi hay dở. Ngoài ra, hai lỗi thật mình gặp khi viết bài (mảng thiếu một phần tử, điểm thắng ở gốc thấp hơn điểm thắng ở lượt sau) đều làm máy chơi kém một cách khó hiểu chứ không làm chương trình crash, đó là lý do nên chạy thử với -fsanitize=address,undefined và kiểm tra những thế cờ có sẵn đáp án.
Muốn đọc thêm lý thuyết về minimax và cắt tỉa alpha-beta, các bạn xem trên Wikipedia.
Bài tiếp theo chúng ta làm project cuối của serie: ứng dụng chat client-server qua socket, nhiều người chat cùng lúc nhờ đa luồng. Nếu thấy bài viết có ích, hãy chia sẻ cho bạn bè nhé.
