Cắt tỉa alpha beta là một kỹ thuật được sử dụng rộng rãi trong lĩnh vực trí tuệ nhân tạo AI. Thuật toán này ứng dụng nhiều đối với các thể loại game phổ biến như caro, cờ vua, cờ tướng…Các ứng dụng chơi game với máy như vậy thông thường sẽ sử dụng alpha beta để lập trình và cài đặt. Thế nhưng, việc áp dụng thuật toán này có khó hay không? Làm thế nào để hiểu chi tiết cách áp dụng?…. Hãy cùng thegioibongda.com.vn đi tìm câu trả lời nhé.
Kỹ thuật cắt tỉa alpha beta là gì?
Cắt tỉa alpha beta là một thuật toán sử dụng những quy ước, định dạng riêng nhằm tạo ra những giải pháp cho một vấn đề. Nói một cách dễ hiểu hơn, ví dụ đối với những trò chơi đối kháng như cờ vua, alpha beta được áp dụng để lập trình sẵn các đường đi nước bước trong trò chơi nhằm dẫn người chơi đến kết quả mong muốn. Cụ thể, kết quả có thể là thắng, thua hoặc hòa tùy thuộc vào từng tình huống mà người chơi gặp phải trong quá trình chơi đối kháng.
Thế nhưng mỗi một đường đi, nước bước trong game đều đã được đánh giá và lập trình sẵn dựa trên thuật cắt tỉa của alpha beta. Kỹ thuật này được áp dụng rộng rãi trong trí tuệ nhân tạo, giúp tạo ra một số phần mềm thông minh hay các trò chơi đối kháng người chơi với máy. Thuật toán này đi từ đơn giản đến phức tạp, tùy thuộc vào số giai thừa ban đầu mà chúng được cài đặt. Việc của con người là tính toán và lập trình những số liệu theo quy ước alpha beta.
Cơ sở của thuật alpha beta
Kỹ thuật alpha beta ra đời dựa trên một thuật toán khác đã có từ rất lâu, đó là thuật toán minimax. Đây chắc hẳn là thuật toán quá quen thuộc đối với chúng ta hiện nay, đặc biệt là những ai theo học ngành công nghệ thông tin. Minimax đơn giản là tìm được những con số lớn nhất và nhỏ nhất trong một dãy số đã cho sẵn trước đó. Thuật toán này khá đơn giản thế nhưng lại có một khuyết điểm duy nhất là dài dòng và khó khăn trong khâu tìm nghiệm.
Đây cũng là lý do vì sao thuật toán alpha beta ra đời và dần thay thế được minimax trong bối cảnh hiện nay. Một trong số những ưu điểm đáng chú ý của alpha beta đó là tinh giản được quá trình tìm nghiệm, loại trừ được một số trường hợp không thích hợp phát sinh nhưng vẫn đảm bảo không ảnh hưởng đến kết quả sau cùng. Nói cách khác, Alpha beta giúp cây trò chơi ban đầu tạo ra được nhiều giải pháp với độ sâu được tăng lên đáng kể.
Áp dụng kỹ thuật alpha beta vào trò chơi caro
Để hiểu rõ hơn về thuật toán này, chúng ta cùng áp dụng vào một trò chơi đối kháng phổ biến hiện nay, cụ thể là thuật toán cắt tỉa alpha beta cờ caro. Ban đầu, cây trò chơi gồm một ô vuông lớn với 9 ô vuông nhỏ tương ứng với 9 nước đi của hai người chơi. Chúng ta đặt người chơi 1 là X, người chơi 2 là O. Như hình bên dưới:
Với lượt đi đầu tiên, X có được 9 sự lựa chọn cho mình, X có thể chọn 1 trong 9 ô trống ban đầu để đi. Khi này, O sẽ còn lại 8 sự lựa chọn, cứ liên tục như thế cho đến khi một trong hai xuất hiện nước đi có thể kết thúc trò chơi. Cụ thể khi một bên có kết quả thắng, một bên có kết quả thua hoặc cả hai không thể đi được thì sẽ kết thúc trò chơi với tỷ số hòa.
Lúc này thuật toán alpha beta được áp dụng để tính toán ra được những kết quả có thể xảy ra. Với càng nhiều ô lựa chọn được đưa ra trong cây trò chơi ban đầu thì số lượng nhánh lá về sau cũng sẽ tăng theo giai thừa. Cụ thể trong bài toán này là 9 giai thừa.
Alpha beta sẽ được gán cho X là những số dương (Nếu X thắng thì sẽ là số dương cao nhất). Ngược lại O sẽ là những số âm (nếu O thắng thì sẽ là số âm nhỏ nhất). Ví dụ, X thắng ở những bước đầu tiên sẽ là 30, nếu hết 9 ô lựa chọn mới thắng thì là 20. Đối với O, nếu thắng ở bước đầu tiên là -30 và nếu hết 9 ô lựa chọn mới thắng thì là -20.
Các trường hợp cắt tỉa phổ biến
Với các con số đã được gán ghép từ ban đầu theo âm dương như ví dụ alpha beta caro kể trên, thuật cắt tỉa được thực hiện dựa trên hai trường hợp cơ bản nhất. Đó là cắt tỉa alpha và cắt tỉa beta.
Đối với trường hợp cắt tỉa alpha, người lập trình sẽ xác định con số max trong nhánh đầu tiên, ví dụ là 20. Tiếp đến, họ sẽ rà soát đến nhánh thứ 2, nếu phát hiện con số nhỏ hơn 20, ví dụ như 15 sẽ tiến hành dừng rà soát. Bởi vì 15<20 và 20 là max ít nhất nên sẽ dừng lại.
Đối với trường hợp cắt tỉa beta, người lập trình sẽ xác định con số min trong nhánh đầu tiên, ví dụ là 10. Tiếp đến, họ sẽ rà soát đến nhánh thứ 2, nếu phát hiện con số lớn hơn 10, ví dụ như 15 sẽ tiến hành dừng rà soát. Bởi vì 15>10 và min tại nút 1 chắc chắn <= 10 nên sẽ bắt đầu cắt bỏ các nhánh lá liên quan từ 15 trở xuống.
Vai trò của thuật toán cắt tỉa trong lĩnh vực AI
Như thegioibongda đã đề cập, thuật toán alpha beta được sử dụng rộng rãi trong nhiều lĩnh vực hiện nay như chế tạo robot, xe không người lái hay đơn giản nhất là những trò chơi đối kháng giữa người và máy.
Thuật toán này được tiến hành và ra đời đã tạo ra một kỷ nguyên mới cho nhân loại, giúp phát triển và giải quyết nhiều bất cập trong xã hội hiện nay. Không chỉ dừng lại ở đó, đối với y học, thuật toán này cũng đang dần được áp dụng để phát minh ra những máy móc, thiết bị hỗ trợ phẫu thuật và điều trị bệnh lý cho con người.
Để giúp các bạn hiểu rõ hơn, xin mời tham khảo ngay video mà chúng tôi chia sẻ chi tiết dưới đây nhé!
Trên đây thegioibongda.com đã chia sẻ những thông tin cơ bản nhất về kỹ thuật cắt tỉa alpha beta được áp dụng trong lĩnh vực trí tuệ nhân tạo hiện nay. Hy vọng với những thông tin trong bài viết sẽ giúp bạn có thêm thật nhiều kiến thức bổ ích và thú vị.
