DauTranh.comĐấu Tranh
Lượt đi và tính trước

Cây quyết định nhiều lượt: cách vẽ, tỉa nhánh và chọn nước khi có đối phương

Vẽ cây lựa chọn khi hai người lần lượt quyết, tỉa nhánh vô ích và chọn nước đầu đúng. Ví dụ hai bạn cùng phòng chia bốn món đồ, chọn tham lam thua chọn có tính.

Two Vietnamese roommates in their twenties stand in a half-packed apartment beside a fridge, a fan and a rice cooker, one pointing, shot from the doorway, cool daylight

Cây quyết định nhiều lượt là hình vẽ tất cả các cách một cuộc đấu có thể diễn ra: mỗi chỗ rẽ là một lượt quyết của một bên, mỗi nhánh là một lựa chọn, và cuối mỗi nhánh ghi mỗi bên được gì. Khi có cây, bạn giải từ ngọn về gốc để biết nước đầu nên đi đâu.

Điểm khác với cây quyết định một mình là ở các chỗ rẽ của đối phương, bạn không được chọn nhánh mình thích; đối phương sẽ chọn nhánh có lợi cho họ. Bài này hướng dẫn vẽ cây trên giấy, tỉa những nhánh không cần xét, và đi qua một ví dụ cho thấy cách chọn "thấy gì tốt lấy ngay" thua cách chọn có tính trước một nước đáp.

Đề bài: hai bạn cùng phòng chia bốn món đồ

Hùng và Lan thuê chung phòng, nay chuyển đi mỗi người một nơi. Có bốn món đồ mua chung cần chia: tủ lạnh nhỏ (A), quạt đứng (B), nồi cơm điện (C), bàn học gấp (D). Hai người bốc thăm, Hùng được chọn trước. Thứ tự chọn: Hùng, Lan, Hùng, Lan — mỗi người hai món. Mỗi người tự chấm mức cần từng món (càng cao càng cần):

  • Hùng chấm: tủ lạnh 6, quạt 5, nồi cơm 2, bàn học 1.
  • Lan chấm: tủ lạnh 1, quạt 6, nồi cơm 5, bàn học 2.
  • Mỗi người biết bảng chấm của người kia (ở chung lâu, đoán được). Ai cũng muốn tổng điểm mình nhận được cao nhất.

Phản xạ đầu tiên của Hùng: chọn tủ lạnh vì đó là món mình chấm cao nhất. Câu hỏi là phản xạ đó có đúng không. Để trả lời, cần vẽ cây, và ở mỗi chỗ rẽ phải ghi rõ ai đang quyết.

Lưu ý rằng điểm chấm của hai người không cộng hay so với nhau được: 6 điểm của Hùng và 6 điểm của Lan là hai thước đo khác nhau. Mỗi người chỉ cố làm tổng điểm của mình cao nhất theo thước đo của mình.

Vẽ cây và giải từ ngọn về gốc

Không cần vẽ hết mọi nhánh. Chỉ cần xét hai nước đầu đáng cân nhắc của Hùng (tủ lạnh và quạt), vì nồi cơm và bàn học Hùng chấm quá thấp.

  1. Nhánh Hùng chọn tủ lạnh (A). Còn quạt, nồi cơm, bàn học. Lan chọn: nếu Lan lấy quạt (6), Hùng sẽ lấy nồi cơm (2, hơn bàn học 1), Lan nhận bàn học (2): Lan được 6 + 2 = 8. Nếu Lan lấy nồi cơm (5), Hùng lấy quạt (5), Lan nhận bàn học: Lan được 5 + 2 = 7. Nếu Lan lấy bàn học, Hùng lấy quạt, Lan nhận nồi cơm: Lan được 2 + 5 = 7. Lan chọn quạt vì 8 lớn nhất.
  2. Kết quả nhánh A: Hùng có tủ lạnh và nồi cơm, tổng 6 + 2 = 8. Lan có quạt và bàn học, tổng 8.
  3. Nhánh Hùng chọn quạt (B). Còn tủ lạnh, nồi cơm, bàn học. Nếu Lan lấy nồi cơm (5), Hùng lấy tủ lạnh (6), Lan nhận bàn học (2): Lan được 7. Nếu Lan lấy tủ lạnh (1), Hùng lấy nồi cơm (2, hơn bàn học), Lan nhận bàn học: Lan được 3. Nếu Lan lấy bàn học (2), Hùng lấy tủ lạnh, Lan nhận nồi cơm: Lan được 7. Lan chọn nồi cơm hoặc bàn học, cả hai đều cho Lan 7.
  4. Kết quả nhánh B: dù Lan chọn nồi cơm hay bàn học, Hùng vẫn lấy được tủ lạnh. Hùng có quạt và tủ lạnh, tổng 5 + 6 = 11. Lan được 7.
  5. So sánh ở gốc: chọn tủ lạnh trước cho Hùng 8 điểm, chọn quạt trước cho Hùng 11 điểm. Nước đầu đúng là quạt, không phải món Hùng thích nhất.

Kiểm lại nhánh B bằng lời: Lan gần như không cần tủ lạnh (chấm 1), nên tủ lạnh "để đó vẫn còn". Quạt thì Lan cần nhất (chấm 6), Hùng không lấy ngay thì mất. Lấy trước thứ đối phương sắp lấy, để dành thứ đối phương không thèm — đó là bài học cây quyết định chỉ ra.

Bảng kết quả cả cây

Đặt các nhánh cạnh nhau để thấy rõ. Cột cuối là tổng điểm mỗi người theo bảng chấm của chính họ.

Nước đầu của HùngLan đáp tốt nhấtHùng nhậnLan nhậnĐiểm Hùng – Lan
Tủ lạnhQuạtTủ lạnh, nồi cơmQuạt, bàn học8 – 8
QuạtNồi cơm (hoặc bàn học)Quạt, tủ lạnhNồi cơm, bàn học11 – 7
Nồi cơmQuạtNồi cơm, tủ lạnhQuạt, bàn học8 – 8
Bàn họcQuạtBàn học, tủ lạnhQuạt, nồi cơm7 – 11

Hai dòng cuối được đưa vào để bảng đủ, và cũng xác nhận việc tỉa chúng từ đầu là đúng: không nhánh nào cho Hùng hơn 11. Với nước đầu là nồi cơm, Lan lấy quạt, Hùng lấy tủ lạnh, Lan nhận bàn học. Với nước đầu là bàn học, Lan lấy quạt, Hùng lấy tủ lạnh, Lan nhận nồi cơm.

Tỉa nhánh: vì sao không cần vẽ hết

Tỉa theo giá trị thấp hiển nhiên. Nếu một nước đầu cho bạn ít hơn mức bạn chắc chắn có ở nhánh khác ngay cả khi đối phương đáp dở nhất, bỏ nó đi. Hùng chọn bàn học trước thì tối đa cũng chỉ được 1 + 6 = 7, ít hơn 11 đã có ở nhánh quạt.

Tỉa theo nước đáp của đối phương. Khi đang xét một nhánh, chỉ cần tìm được một nước đáp của đối phương làm nhánh đó tệ hơn phương án tốt nhất bạn đã có, là bỏ được cả nhánh, không cần xét các nước đáp còn lại. Đây là cách máy tính tỉa cây khi tính cờ, và người cũng dùng được trên giấy.

Gộp những nhánh giống nhau. Nhiều đường đi khác thứ tự nhưng dẫn tới cùng một thế. Ở thế đó, ai cũng đã có món gì và còn món gì, thì kết quả từ đó trở đi như nhau. Gộp lại để khỏi tính hai lần.

Dừng ở độ sâu vừa đủ. Với cây lớn, không vẽ đến tận ngọn được. Vẽ vài lượt rồi chấm điểm thế đứng tạm, miễn là chấm theo cùng một cách cho mọi nhánh. Nếu hai nhánh có điểm tạm sát nhau, đó là chỗ đáng vẽ sâu thêm; nhánh nào hơn kém rõ thì dừng sớm được.

Áp dụng vào công việc: chọn ca trực, chọn đề tài, chọn tuyến

Bất cứ khi nào có nhiều người lần lượt chọn trong một danh sách chung, cây quyết định cho cùng bài học như chia đồ. Hai nhân viên chọn ca trực dịp Tết theo lượt: người chọn trước thường lấy ngay ca mình thích nhất, nhưng nếu ca đó người kia không muốn thì nó vẫn sẽ còn đó. Nước đúng là lấy ca mà cả hai đều muốn và mình cũng cần.

Trong một nhóm học phải chia đề tài lần lượt cho các thành viên, người hiểu cây sẽ hỏi trước ai thích đề tài nào. Không cần ép ai nói thật; chỉ cần đoán đúng thứ tự ưu tiên của người kế tiếp là đủ để quyết nước đầu.

Với tài xế giao hàng chia tuyến trong một khu: ai cũng muốn tuyến gần, nhưng có tuyến chỉ một người muốn vì gần nhà người đó. Người chọn trước khôn ngoan sẽ lấy tuyến bị tranh nhiều nhất trong số tuyến mình thấy ổn, rồi để dành tuyến ít người tranh cho lượt sau.

Khi cần ghi chép, vẽ cây bằng bút chì trên một tờ giấy ngang: gốc bên trái, mỗi lượt là một cột, nhánh của mình tô một màu, nhánh của đối phương tô màu khác. Nhìn hai màu xen kẽ giúp nhớ rằng ở cột đối phương, bạn không được chọn.

Đổi thứ tự chọn thì sao: kiểm lại bằng cây

Một cách hay được đề nghị để bớt lợi thế cho người chọn trước là thứ tự một – hai – một: Hùng chọn một món, Lan chọn liền hai món, Hùng nhận món cuối. Nghe có vẻ công bằng hơn, nhưng chỉ cây mới cho biết thật sự có công bằng hơn không với hai bảng chấm cụ thể này.

Tính nhanh: nếu Hùng chọn tủ lạnh trước, Lan lấy liền hai món mình cần nhất trong ba món còn lại là quạt (6) và nồi cơm (5), Hùng nhận bàn học. Hùng được 6 + 1 = 7, Lan được 11. Nếu Hùng chọn quạt trước, Lan lấy nồi cơm (5) và bàn học (2) vì tủ lạnh Lan chỉ chấm 1, Hùng nhận tủ lạnh. Hùng được 5 + 6 = 11, Lan được 7. Nếu Hùng chọn nồi cơm trước, Lan lấy quạt và bàn học, Hùng nhận tủ lạnh: 8 và 8.

Vậy với thứ tự mới, Hùng vẫn chọn quạt trước và vẫn được 11. Đổi thứ tự không làm thay đổi gì ở đây, vì hai người cần những món khác nhau: thứ Hùng cần nhất (tủ lạnh) lại là thứ Lan không cần. Bài học: một quy tắc chia nghe công bằng chưa chắc công bằng trong từng trường hợp; muốn biết, phải vẽ cây với đúng nhu cầu của những người trong cuộc.

Những nhầm lẫn hay gặp khi dùng cây

Chọn nhánh mình thích ở chỗ rẽ của đối phương. Đây là lỗi phổ biến nhất. Người vẽ cây vô thức đi theo nhánh đẹp cho mình, quên rằng ở lượt đó người quyết là bên kia. Mỗi lần tới cột đối phương, tự nhắc: họ sẽ chọn gì nếu họ muốn điều tốt cho họ.

Dùng bảng chấm của mình cho đối phương. Lan không cần tủ lạnh, nhưng nếu Hùng tưởng Lan cũng mê tủ lạnh như mình thì Hùng sẽ vội lấy tủ lạnh và mất quạt. Đoán sai bảng chấm của đối phương làm sai cả cây.

Tin cây khi bảng chấm chỉ là đoán mò. Cây chỉ đúng bằng các con số ở ngọn. Nếu bạn không biết đối phương muốn gì, hãy vẽ hai ba cây ứng với vài khả năng, rồi chọn nước đầu tốt ở hầu hết các cây.

Vẽ quá sâu rồi bỏ cuộc. Cây nở rất nhanh. Bốn món đồ, chọn lần lượt, đã có 4 × 3 × 2 × 1 = 24 cách sắp. Mười món thì không vẽ tay được. Hãy tỉa từ đầu và dừng ở độ sâu đủ dùng.

Câu hỏi thường gặp

Cây quyết định nhiều lượt khác cây quyết định thông thường thế nào?

Cây thông thường chỉ có một người quyết, các chỗ rẽ còn lại là may rủi như thời tiết. Cây nhiều lượt có chỗ rẽ thuộc về đối phương, và ở đó bạn phải đoán đối phương chọn nhánh nào có lợi cho họ, không phải nhánh có lợi cho bạn.

Vì sao Hùng không nên chọn tủ lạnh trước dù chấm nó cao nhất?

Vì Lan gần như không cần tủ lạnh nên nó sẽ còn đến lượt sau của Hùng. Quạt thì Lan cần nhất, Hùng không lấy ngay sẽ mất. Chọn quạt trước, Hùng được cả quạt lẫn tủ lạnh, tổng 11 điểm thay vì 8.

Không biết đối phương chấm thế nào thì vẽ cây ra sao?

Vẽ vài phiên bản cây ứng với vài cách chấm có khả năng nhất của đối phương. Nước đầu nào cho kết quả khá ở hầu hết các phiên bản thì an toàn hơn nước đầu chỉ tốt ở một phiên bản.

Có cần vẽ hết mọi nhánh không?

Không. Bỏ những nước đầu rõ ràng kém, bỏ nhánh khi đã thấy một nước đáp của đối phương làm nó tệ hơn phương án bạn đang có, và gộp những đường dẫn tới cùng một thế. Phần còn lại thường đủ nhỏ để vẽ tay.

Cách chọn này có bất công với người chọn sau không?

Thứ tự chọn đã cho người chọn trước một lợi thế, cây quyết định chỉ giúp dùng lợi thế đó cho đúng. Nếu muốn công bằng hơn, có thể chọn theo thứ tự một – hai – hai – một, hoặc đổi người chọn trước giữa các lần chia.

Cần tư vấn cụ thể cho trường hợp của bạn?

Chúng tôi sẽ liên hệ trong vòng 24 giờ.

Đăng ký tư vấn ngay

Bài viết liên quan

Bạn cần hỗ trợ thêm?

Để lại thông tin, chúng tôi sẽ liên hệ trong 24 giờ.

hoặc
Gọi ngay 0926 138 138