Tui viết game ô ăn quan, kẹt ngay chỗ trí tuệ nhân tạo.
Tui nghĩ hàm heur như sau
cho x(i) là số quân trong ô x(i)
for i=1 to n
heur=heur+(x(i)-avg)^2
avg là trung bình.
Ô càng ít quân càng dễ lộ ô trống
xin ý kiến các boss.

Tui nghĩ lại rùi, hàm heur phải vầy
đếm số ô 0,1,2
nếu nước đi ăn thì trừ 1
kq càng nhỏ càng tốt
xin ý kiến các boss

Chào bạn. Mình cũng đang có bài tập lớn về bài toán ô ăn quan này. Bạn viết code được rồi share cho mình được hok? mail của mình là acount300@yahoo.com.vn. Mong sớm nhận được tin từ bạn. Cám ơn bạn trước nhé!

Không biết chủ nhân topic còn quan tâm đến AI trò ô ăn quan không, cho mình học hỏi với. Mình viết AI ô ăn quan bằng phương pháp tối ưu cục bộ Minimax (có tối ưu nhánh trên trường hợp cây con bằng nhau) thì kết quả cũng tàm tạm, nhưng vẫn bị chưa đưa toàn bộ các phương án về trường hợp tối ưu thật sự. Nên mình muốn quan tâm heuristic để cải thiện nó. Có gì thì đàm đạo trên topic này luôn nhé (nếu chủ topic muốn bàn luận)

Cho mình xem hàm heuristic đó đi.

Mình định viết lại AI cho ô ăn quan bằng Genetic Algorithm thì mình vướng hàm thích nghi (heuristic)

hàm đánh giá trên GA (heuristic)

Với mỗi lượt đi (bao gồm đi trước và đi sau) vì mình phát sinh một chuỗi gen các lượt đi khoảng 5 lượt
i := Lượt đi thứ 1 --> 5

heur += [trước[i] - max(Sau[i])] / [max(trước[i])+1] + Sau[i] / [max(sau[i]) + 1]

trước [i] : là số quân người đi trước ăn tại lượt i
sau [i]: số quân người đi sau ăn tại lượt i
max(trước[i]) : số quân ăn tối đa người đi trước tại lượt i
max(sau[i]): số quân ăn tối đa người đi sau tại lượt i

Mình muốn hàm thích nghi cho GA sao cho nó đảm bảo được tính chất:
+ Chêch lệch ăn thua luôn có lợi cho người đi trước.
+ Người đi sau luôn tìm cách ăn quân nhiều nhất

Heur+=A*(truoc[i]-sau[i])-B*(sau[i]-max_sau)
// A và B là 2 trọng số

Cảm ơn bạn bigbelly vì đưa ra gợi ý cho heur cho mình nhưng mình cũng có ý kiến về công thức của bạn

+ Hàm heuristic của mình ở đây dùng trong thuật giải di truyền. Do đó nó sẽ có phần chọn lọc cá thể với heur cao nhất (dù mang tính chất ngẫu nhiên)

Heur+=A*(truoc[i]-sau[i])-B*(sau[i]-max_sau)

Mình nghĩ sẽ xuất hiện tình trạng với các cá thể có chỉ số sau[i] càng thấp dẫn tới càng làm tăng chỉ số Heur. Như vậy sau quá trình di truyền của thuật giải sẽ tiếp cận các lượt chơi mà người đi sau sẽ đi với số quân ăn càng thấp nên dẫn tới quyết định bước đi người chơi đi trước sẽ sai xót.

Sửa lại
heur+=A*(truoc[i]-sau[i])-B*(sau[i]-max_sau[i])
vấn đề là điều chỉnh A, B.
Bạn có thể cho mình xem cấu trúc gen k0?

Cấu trúc gen trên GA mình mã hóa theo dạng cổ điển [nhị phân] mỗi cá thể là một đoạn gen đựợc chia thành các phần nhỏ. Mỗi phần nhỏ của gen biểu diễn cho một nước đi của người chơi hoặc máy tính.
Mỗi phần nhỏ bao gồm 4 bit. [4 bit để mã hóa tất cả 10 cách đi có phát sinh trong một nước đi].

Trong đó
+ bit_đầu tiên : xác định hướng đi qua trái hay phải.
+ các bit còn lại kết hợp để xác định ô đi.
[0100][1011][1010]...

Lai tạo và đột biến thực hiện trên những ràng buộc mà phần gen mới phải tồn tại cách đi vì mã hóa 4 bit cho 10 cách đi nên dư 6 cách. Bao gồm 2 quá trình chọn phần gen để lai tạo hoặc đột biến và chọn bit lai tạo hoặc đột biến.

Ví dụ như phần [0100] mà đột biến thành [0101] thì phần [0101] sẽ được chuyển lại [0001] (vì [0101] không tồn tại cách đi)

Ngoài ra, khi tạo xong một đoạn gen mới nhưng khi đi theo lần lượt theo các cách đi trên đoạn gen đó mà tồn tại 1 cách đi không thực hiện được do quân tại ô đó bằng 0 thì trong trừ đi điểm thích nghi.