Bài viết sưu tầm

Thủ tục Alpha – Beta

Các giá trị ước lượng phát sinh tương ứng với các đỉnh Và, Hoặc được gọi là các a-giá trị và b-giá trị tương ứng. Thủ tục alpha-beta bắt đầu từ nút gốc với giá trị alpha là -¥và beta là +¥. Thủ tục alpha-beta gọi đệ quy với dãy số giữa alpha và beta. Để thực hiện tìm kiếm minimax bằng thủ tục alpha – beta, có các bước sau:

1)            Nếu mức của cây là gốc, lấy giá trị alpha là -¥  và gia trị beta là +¥.

2)            Nếu đã đến bước kết thúc tìm kiếm, tính giá trị hàm ước lượng của vị trí hiện tại cho đấu thủ tương ứng. Cho ra kết quả.

3)            Nếu mức ứng với đấu thủ min:

i)              Cho đến khi các nút con được kiểm tra bằng thủ tục alpha – beta hoặc cho đến khi alpha >= beta, thực hiện các bước sau:

+ Dùng thủ tục alpha – beta với các giá trị alpha – beta hiện có trên các nút con. Ghi lại giá trị do thủ tục đưa ra.

+ So sánh giá trị thu được với beta, nếu giá trị thu được nhỏ hơn beta thì cho beta nhận giá trị này.

ii)            Cho ra giá trị beta.

4)            Ngược lại, mức này ứng với đấu thủ beta, thực hiện:

i)              Cho đến khi các nút con được kiểm tra bằng thủ tục alpha – beta hoặc cho đến khi alpha >= beta, thực hiện các bước sau:

+ Dùng thủ tục alpha – beta với các giá trị alpha – beta hiện có trên các nút con. Ghi lại giá trị do thủ tục đưa ra.

+ So sánh giá trị thu được với alpha, nếu giá trị thu được lớn hơn alpha thì cho alpha nhận giá trị này.

ii)            Cho ra giá trị alpha.