Chương 313: Thuật Toán Dung Sai Byzantine ________________________________________ Thái Chí Viễn tiếp tục giải thích: "Ví dụ, bây giờ có tổng cộng năm vị tướng, trong đó hai vị tướng cho rằng nên tấn công, và hai vị tướng khác cho rằng nên rút lui. Lúc này, vị tướng thứ năm là một kẻ phản bội, anh ta nói với vị tướng muốn tấn công rằng 'tôi cũng sẽ tấn công', và lại nói với vị tướng muốn rút lui rằng 'tôi cũng sẽ rút lui'. "Kết quả là, vị tướng muốn tấn công nghĩ rằng bây giờ có ba đội quân đồng ý tấn công, vượt quá một nửa, nên ngày mai nên tấn công. Còn vị tướng muốn rút lui lại nghĩ rằng ngày mai nên rút lui. "Kết quả cuối cùng là hai vị tướng tấn công, hai vị tướng rút lui, dẫn đến chiến tranh thất bại. "Đây chính là vấn đề mà sự phi tập trung mang lại, bởi vì năm vị tướng này có cấp bậc ngang nhau, không có một chỉ huy có quyền lực tuyệt đối, nên trong quá trình thương lượng chiến lược với nhau, sẽ phát sinh vấn đề như vậy." Trịnh Kiệt chợt hiểu ra gật đầu: "Thì ra là vậy! Vậy làm thế nào để giải quyết vấn đề này? Cũng không có cách nào để xác minh cụ thể vị tướng nào đang nói dối đúng không?" Thái Chí Viễn giải thích: "Thực ra để giải quyết vấn đề này rất đơn giản: chỉ cần hỏi thêm vài lần nữa là được." "Giả sử tôi là một trong các tướng quân (A), và tướng quân B nói với tôi rằng anh ta sẽ tấn công cùng tôi. "Nếu tôi tin, thì có khả năng sẽ bị lừa, bởi vì tướng quân B có thể là kẻ phản bội, anh ta có thể chỉ nói với tôi là tấn công, nhưng lại nói với người khác là rút lui. "Vì vậy, lúc này tôi nên hỏi lại tướng quân C, tôi hỏi anh ta: 'Tướng quân B nói với anh là tấn công hay rút lui?' "Sau đó tôi đi hỏi lần lượt tất cả các tướng quân khác, tổng hợp tất cả thông tin mà tướng quân B đã nói với họ. "Thông tin mà các tướng quân khác nói với tôi về tướng quân B cũng không nhất thiết là sự thật, bởi vì trong số các tướng quân khác cũng có thể có kẻ phản bội, có thể xảy ra trường hợp tướng quân B nói với họ là tấn công, nhưng họ lại nói với tôi rằng tướng quân B nói rút lui. "Vì vậy, tôi lần lượt hỏi 'tướng quân B đã nói gì với các anh', nếu tấn công nhiều hơn, thì tôi sẽ ghi ý kiến của tướng quân B là tấn công; "Rồi lại lần lượt hỏi 'tướng quân C đã nói gì với các anh', nếu rút lui nhiều hơn, thì tôi sẽ ghi ý kiến của tướng quân C là rút lui. "Cứ như vậy, tôi thông qua phương thức lồng nhau lặp đi lặp lại, không ngừng loại trừ các đáp án thiểu số, và kết luận cuối cùng rút ra sẽ là đáp án đa số chính xác hơn. "Trong điều kiện đạt được Dung sai Byzantine, chúng ta buộc tất cả các tướng quân phải tuân thủ chiến lược này, và phải kiên quyết thực hiện kết luận cuối cùng. "Như vậy chúng ta có thể đảm bảo mọi người cùng tấn công hoặc cùng rút lui." Trịnh Kiệt có chút bối rối: "Trong điều kiện đạt được Dung sai Byzantine? Tức là như anh Thái đã nói trước đó, số lượng kẻ phản bội phải ít hơn một phần ba?" Thái Chí Viễn gật đầu: "Đúng vậy. "Chúng ta lấy trường hợp 3 vị tướng làm ví dụ: "Giả sử trong 3 vị tướng, tướng quân C là kẻ phản bội, cố ý truyền đạt thông tin sai lệch. "Tướng quân A sẽ nói với tướng quân B và C là tấn công. "Nhưng tướng quân B sau khi nhận lệnh không thể xác nhận tướng quân A có phải là kẻ phản bội hay không, nên anh ta phải hỏi tướng quân C: 'Lệnh mà tướng quân A đưa cho anh là gì?' Trong khi tướng quân C là kẻ phản bội, nên sẽ cố ý nói: 'Lệnh mà tướng quân A đưa cho tôi là rút lui'. "Vì chỉ có ba vị tướng, nên tướng quân B không thể phán đoán được tướng quân A và tướng quân C, ai mới là kẻ phản bội, bởi vì lệnh tấn công và rút lui mỗi bên có một phiếu, không thể hình thành đa số. "Tương tự, tướng quân B khi thực hiện chiến lược này, cũng không thể phán đoán được tướng quân A và tướng quân C ai là kẻ phản bội. "Đây là tình huống đơn giản nhất, nếu số lượng tướng quân tăng lên, ví dụ đồng thời có 7 vị tướng, trong đó có 2 kẻ phản bội (2/7 < 1/3), tình hình sẽ trở nên phức tạp hơn rất nhiều, phải lặp lại nhiều lần mới có thể đưa ra kết luận cuối cùng. "Vì vậy tôi mới nói, vấn đề này không cần tự mình suy tính, chỉ cần nhớ kết luận là được. "Kết luận là, khi số lượng kẻ phản bội đạt đến một phần ba hoặc nhiều hơn, vấn đề này không thể giải quyết được. "Ngược lại, muốn vấn đề này có thể giải quyết được, phải kiểm soát số lượng kẻ phản bội ở mức ít hơn một phần ba. "Áp dụng vào số lượng người của ba phòng, sẽ rõ ràng ngay lập tức. "Phòng 4 người, 3 người trả lời, nên chỉ cần có 1 Tự Do Nhân độc hại (1/3), vấn đề này không thể giải quyết được (không thể đảm bảo nhất trí). "Phòng 8 người, 7 người trả lời, trong phòng có 3 Tự Do Nhân độc hại (3/7 > 1/3), vấn đề không thể giải quyết được. "Phòng 13 người, 12 người trả lời, trong phòng có 4 Tự Do Nhân độc hại (4/12 = 1/3), vấn đề không thể giải quyết được." Trịnh Kiệt chợt hiểu ra: "Thì ra là vậy! "Vậy nên anh Thái đã áp dụng công thức này, nhận ra ngay lập tức phòng 8 người thực ra là an toàn nhất, bởi vì chúng ta chỉ cần đưa 1 Tự Do Nhân phe mình vào để chiếm vị trí, vấn đề này chắc chắn có thể giải quyết được." Tần Dao vẫn chưa hiểu: "Khoan đã, mặc dù tôi vẫn chưa hiểu lắm, nhưng tôi đã nhớ công thức này rồi. "Thắc mắc của tôi bây giờ là, vấn đề Byzantine này áp dụng cụ thể vào quy tắc trò chơi như thế nào?" Trịnh Kiệt xung phong giải thích: "Để tôi giải thích! "Sau khi vào phòng ở giai đoạn hai, thực chất là sự đối đầu giữa người trả lời và Người Ra Đề. "Ví dụ, chúng ta mở 'tiệm đen' trong phòng 8 người, tức là chúng ta đóng vai người trả lời, còn người chơi Cộng đồng khác vào phòng sau đóng vai Người Ra Đề. "Mục tiêu của phe người trả lời chúng ta là, đạt được lựa chọn nhất trí, như vậy có thể nhận được phần thưởng thêm, kiếm thời gian thị thực từ Người Ra Đề; "Ngược lại, mục tiêu của phe Người Ra Đề là, không cho chúng ta đạt được lựa chọn nhất trí. "Phương pháp đơn giản hơn là, người chơi bình thường phe Người Ra Đề chỉ cần cố ý chọn lựa chọn khác với chúng ta là được. "Vì vậy, chúng ta mới cần thiết lập quy tắc phòng, buộc những người chơi này phải nộp lựa chọn đa số. "Chức năng 'Gửi đề xuất' thực chất là mô phỏng quá trình tính toán của Thuật toán Dung sai Byzantine, mỗi người chơi đều bị buộc phải gửi đề xuất đa số hiện tại, nhưng sẽ có một khoảng thời gian nhất định. "Vì vậy, sau khi gửi đi gửi lại nhiều lần, tất cả người trả lời bình thường (trừ Tự Do Nhân) sẽ gửi đề xuất cùng một lựa chọn. "Sau đó, quy tắc trò chơi sẽ buộc những người chơi này nộp lựa chọn này, đạt được mục tiêu nhất trí toàn bộ. ḳyhuyen.Com"Nhưng như anh Thái nói, quá trình mô phỏng 'Gửi đề xuất', bản thân nó cần đề xuất đa số đạt đến một số lượng nhất định mới có thể thành lập (tức là thỏa mãn Byzantine). "Người chơi Tự Do Nhân, thực chất đóng vai 'Nút độc hại' và 'Kẻ phản bội', họ sẽ liên tục gửi đề xuất thiểu số, để gây rối quá trình tính toán. "Giả sử có nhiều Tự Do Nhân độc hại, có thể xảy ra tình huống như thế này: "Lúc này vốn dĩ đề xuất lựa chọn A đang nhiều hơn, nhưng đột nhiên xuất hiện rất nhiều đề xuất lựa chọn B vượt lên, khiến một số người chơi chuyển sang đề xuất lựa chọn B, rồi lại đột nhiên xuất hiện một số đề xuất lựa chọn A... "Điều này sẽ khiến đề xuất mà người chơi gửi đi liên tục thay đổi, không thể cố định lại được, như vậy khi chức năng 'Gửi đề xuất' kết thúc, có người chơi nộp A, có người chơi nộp B, mọi người sẽ không thể đạt được sự nhất trí. "Phe người trả lời không thể ổn định buộc Người Ra Đề tiếp tục ra đề, không thể ổn định thu được lợi nhuận, điều đó tương đương với việc 'tiệm đen' bị phá hủy." Thái Chí Viễn gật đầu: "Đúng vậy, vì vậy chỉ cần thông qua công thức xác định điều kiện thành lập của Dung sai Byzantine, rồi so sánh với số lượng Tự Do Nhân có thể vào từng phòng, là có thể xác định được chiến lược vào phòng. •"Phòng 8 người" cho phép 3 Tự Do Nhân vào, vấn đề này sẽ không giải quyết được khi xuất hiện 3 kẻ phản bội. Vì vậy, chúng ta chỉ cần đảm bảo trong phòng có 1 Tự Do Nhân phe mình chiếm vị trí, là an toàn. •"Đương nhiên, Tự Do Nhân phe mình này phải là người thiện ý, tức là anh ta sẽ chủ động thực hiện chiến lược gửi đề xuất đa số. •"Phòng 13 người" cho phép 6 Tự Do Nhân vào, vấn đề này sẽ không giải quyết được khi xuất hiện 4 kẻ phản bội. Vì vậy Vương Vệ Đông phải đảm bảo số lượng Tự Do Nhân độc hại vào phòng 13 người cuối cùng thấp hơn 4 người. •"Vì vậy, họ cần nhiều Tự Do Nhân thiện ý hơn để chiếm vị trí. •"Nếu họ không nhận ra điểm này, chúng ta có thể chọn chủ động tấn công. Nhưng vì Vương Vệ Đông đã nhận ra, và thực hiện phòng thủ, việc cố gắng tấn công mạnh sẽ không còn nhiều ý nghĩa. •"Vì vậy tôi đã thay đổi một hướng suy nghĩ, tức là lợi dụng hình phạt trái lòng của trò chơi, nhắm vào đặc điểm của Vương Vệ Đông để đưa ra những câu hỏi có thể khiến anh ta thân bại danh liệt trong Cộng đồng, từ đó buộc anh ta phải hủy bỏ quy tắc phòng."