Bài 11: Chơi Wordle tối ưu bằng lý thuyết thông tin: entropy và thuật toán tìm kiếm

Đầu năm 2022, cả thế giới chia sẻ những ô vuông xanh vàng của trò Wordle. Đoán một từ tiếng Anh 5 chữ cái trong 6 lượt – nghe như trò may rủi. Nhưng các nhà khoa học đã chứng minh: chơi tối ưu, trung bình chỉ cần khoảng 3,42 lượt. Công cụ để làm điều đó là lý thuyết thông tin của Claude Shannon.

Bài thứ mười một của chuyên mục "Thuật toán trong đời sống". Bài này cho thấy một khái niệm toán học – entropy – biến một trò chơi đoán chữ thành bài toán tìm kiếm tối ưu.

1. Wordle là gì?

Wordle được lập trình viên Josh Wardle ở Brooklyn tạo ra và phát hành công khai vào tháng 10/2021. Theo Nieman Lab, ngày 1/11/2021 trò chơi có chưa tới 100 người chơi mỗi ngày, vài tuần sau đã lên 300.000. Tháng 1/2022, báo The New York Times mua lại Wordle với giá "mức thấp của hàng triệu USD (bảy chữ số)".

Luật chơi: đoán một từ 5 chữ cái. Sau mỗi lượt, mỗi chữ được tô màu:

• Xanh lá: đúng chữ, đúng vị trí.
• Vàng: có chữ này trong đáp án nhưng sai vị trí.
• Xám: không có trong đáp án.

Danh sách đáp án ban đầu gồm 2.315 từ, còn danh sách từ được phép đoán lớn hơn nhiều: 12.972 từ.

2. Một lượt đoán "đáng giá" bao nhiêu?

Mỗi lượt đoán chia các từ còn khả năng thành nhiều nhóm theo kiểu phản hồi màu. Lượt đoán tốt là lượt chia ra nhiều nhóm nhỏ, đều nhau – vì dù phản hồi là gì, số từ còn lại cũng ít.

Năm 1948, Claude Shannon định nghĩa đại lượng entropy để đo lượng thông tin:

H = Σ p_i × log₂(1 / p_i), với p_i là xác suất rơi vào nhóm thứ i. Đơn vị là bit – theo bài báo của Shannon, đây là từ do nhà toán học John Tukey gợi ý.

Mỗi bit thông tin chia đôi số khả năng. Nếu còn 32 từ, cần log₂(32) = 5 bit để chắc chắn tìm ra đáp án. Một lượt đoán mang lại 4,32 bit nghĩa là trung bình chỉ còn khoảng 32 / 2^4,32 ≈ 1,6 từ.

3. Code: chọn lượt đoán có entropy cao nhất

Ta thử với một từ điển nhỏ 32 từ. Với mỗi từ đoán, tính phản hồi màu cho từng đáp án có thể, gom nhóm và tính entropy:

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// Mã hóa phản hồi thành số hệ 3: 2 = xanh, 1 = vàng, 0 = xám
int pattern(const string& g, const string& a){
    int res[5] = {0}, left[26] = {0};
    for(int i = 0; i < 5; i++){ if(g[i] == a[i]) res[i] = 2; else left[a[i]-'a']++; }
    for(int i = 0; i < 5; i++) if(!res[i] && left[g[i]-'a'] > 0){ res[i] = 1; left[g[i]-'a']--; }
    int code = 0; for(int i = 0; i < 5; i++) code = code * 3 + res[i];
    return code;
}
double entropy(const string& g, const vector<string>& cand){
    map<int,int> groups; for(auto& w : cand) groups[pattern(g, w)]++;
    double n = cand.size(), H = 0;
    for(auto [p, k] : groups) H += k / n * log2(n / k);
    return H;
}
int main(){
    vector<string> words = {"crane","slate","trace","crate","react","heart","earth","stare",
        "share","shore","store","stone","phone","prone","drone","grape","graph","light","night",
        "might","sight","tight","fight","eight","plant","plane","place","space","spice","price","pride","bride"};
    for(string g : {"trace", "crane", "might"})
        printf("%s: %.2f bit\n", g.c_str(), entropy(g, words));
}

from collections import Counter
from math import log2

def pattern(guess, answer):
    # 2 = xanh (đúng chữ, đúng chỗ), 1 = vàng (có chữ, sai chỗ), 0 = xám
    res = [0] * 5
    left = Counter()
    for i in range(5):
        if guess[i] == answer[i]: res[i] = 2
        else: left[answer[i]] += 1
    for i in range(5):
        if res[i] == 0 and left[guess[i]] > 0:
            res[i] = 1; left[guess[i]] -= 1
    return tuple(res)

def entropy(guess, candidates):
    # lượng thông tin kỳ vọng (bit) mà lượt đoán này mang lại
    groups = Counter(pattern(guess, w) for w in candidates)
    n = len(candidates)
    return sum(k / n * log2(n / k) for k in groups.values())

words = ["crane", "slate", "trace", "crate", "react", "heart", "earth", "stare",
         "share", "shore", "store", "stone", "phone", "prone", "drone", "grape",
         "graph", "light", "night", "might", "sight", "tight", "fight", "eight",
         "plant", "plane", "place", "space", "spice", "price", "pride", "bride"]
rank = sorted(words, key=lambda g: -entropy(g, words))
for g in rank[:3] + rank[-2:]:
    print(g, round(entropy(g, words), 2), "bit")

# Mô phỏng: luôn đoán từ có entropy cao nhất trong số từ còn khả năng
answer, cand, turn = "plant", words[:], 0
while True:
    turn += 1
    g = max(cand, key=lambda x: entropy(x, cand))
    p = pattern(g, answer)
    print(f"Luot {turn}: con {len(cand)} tu kha nang, doan {g} -> {p}")
    if g == answer: break
    cand = [w for w in cand if pattern(g, w) == p]

Từ đoán	Entropy
trace	4,32 bit
crane	4,26 bit
crate	4,20 bit
…	…
might	3,08 bit
fight	3,08 bit

"might" và "fight" kém vì chúng giống quá nhiều từ khác (light, night, sight, tight…) – phản hồi thường giống nhau nên ít thông tin. Mô phỏng với đáp án "plant":

TRACE
PLANT

Lượt 1 đoán TRACE: chữ T vàng, chữ A xanh, các chữ khác xám → trong 32 từ chỉ còn đúng 1 từ khớp. Lượt 2: PLANT – thắng!

Lưu ý chữ cái lặp: khi tính màu, phải đánh dấu xanh trước, rồi mới xét vàng với số lượng chữ còn lại – nếu không, từ đoán có hai chữ giống nhau sẽ bị tô sai. Code ở trên dùng mảng đếm left để xử lý trường hợp này.

4. Lời giải tối ưu thực sự

• Chọn từ có entropy cao nhất ở mỗi lượt là chiến lược tham lam – rất tốt nhưng chưa chắc tối ưu tuyệt đối. Kênh 3Blue1Brown có bài giảng nổi tiếng "Solving Wordle using information theory" giải thích chi tiết cách tiếp cận này.
• Năm 2025, Dimitris Bertsimas và Alex Paskov (MIT) công bố trên tạp chí Operations Research lời giải tối ưu chính xác bằng quy hoạch động: từ mở màn tốt nhất là SALET, trung bình 3,421 lượt, và luôn tìm ra đáp án trong tối đa 5 lượt. Alex Selby cũng tìm ra kết quả tương tự bằng tìm kiếm vét cạn.

5. Entropy ở đâu ngoài Wordle?

• Nén dữ liệu: entropy là giới hạn dưới cho số bit trung bình mỗi ký hiệu – mã Huffman (bài trước của chuyên mục) tiến rất gần giới hạn này.
• Cây quyết định trong học máy: chọn câu hỏi phân loại có "độ tăng thông tin" lớn nhất – y hệt cách chọn từ đoán.
• Trò chơi 20 câu hỏi, bài toán tìm đồng xu giả bằng cân thăng bằng: mỗi câu hỏi tốt nên chia các khả năng thật đều.
• Chặt nhị phân: mỗi lần hỏi lấy đúng 1 bit, nên tìm trong n phần tử cần log₂ n bước.

6. Bạn học được gì từ đây?

• Một câu hỏi tốt là câu hỏi chia đều các khả năng – tư duy này dùng được cả trong thuật toán lẫn đời sống.
• Logarit cơ số 2 xuất hiện khắp nơi trong tin học: chặt nhị phân, cây, độ phức tạp, thông tin.
• Tham lam cho lời giải tốt; quy hoạch động cho lời giải tối ưu nhưng tốn tính toán hơn.

Bài tập luyện tập

• Codeforces 1807E – Interview (bài tương tác: tìm phần tử bằng chặt nhị phân)
• CSES – Array Division (chặt nhị phân trên đáp án)

Thử thách: thêm 10 từ bất kỳ vào danh sách words và chạy lại. Từ mở màn tốt nhất có thay đổi không? Chia sẻ trong phần bình luận nhé!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 12: Máy tính chơi cờ giỏi hơn người thế nào? Minimax, cắt tỉa alpha–beta và AlphaZero

Đọc tiếp: máy tính chơi cờ →

← Bài trước: Sudoku & quay luiXem tất cả 27 bài →

Nguồn tham khảo

• Nieman Lab (2022) – The New York Times buys Wordle
• arXiv 2408.11730 – Phân tích danh sách từ của Wordle
• Bertsimas & Paskov (2025) – lời giải tối ưu chính xác cho Wordle, tạp chí Operations Research
• Claude Shannon (1948) – A Mathematical Theory of Communication
• 3Blue1Brown – Solving Wordle using information theory