PDA

View Full Version : cờ caro, heuristic nào cho tốt?



Xmen
09-12-2004, 01:06
các bác, tui đang làm chương trình đánh cờ caro, cho máy đánh với người, 5con trên 1 dòng(dòng ngang, dọc,chéo) là thắng, kể cả chặn 2 đầu, tui áp dụng Heuristic min-max với hàm ước lượng là: "số con cờ đã đạt được trên 1 dòng".
Nhưng trước khi áp dụng heuristic tui phải xét đến các hàm đặc biệt với độ ưu tiên như sau ( với giả sử X là chương trình của mình, O là người chơi)
1. X đạt 5 con trước tại 1 vị trí -> đánh X vào cái ô đó.
2. Chặn O đạt 5 con.
3. X đạt 4 con.
4. Chặn O đạt 4 con.
5. X đạt 2 hàng 3.
6. Chặn O đạt 2 hàng 3.
Sau đó mới áp dụng heuristic.
Tui thấy với cách làm này, heuristic chỉ áp dụng cho các trường hợp trên bàn cờ chỉ có các con liền mạch 2 con hoặc 3 con hoặc...1 con, và phải kiểm tra nhiều lần. Nhưng nếu không đi chặn truớc thì phải làm sao ?
Nếu ta áp dụng heuristic với hàm ước lượng là số dòng còn lại có thể đi được như kiểu tic tac toe 3x3 thì có khi nó sẽ không chặn được.
Bác nào có kinh nghiệm chỉ giúp, xin cảm ơn nhiều.

htbn_hoang
19-12-2004, 21:07
Bạn đã biết thủ tục min-max, do đó tui chỉ nói về cách cài đặt Heuristic. Tôi đã làm bài này và đánh khá hay.
Trước tiên chúng ta giả sử cả min và max dùng cùng thật toán, cung một hàm Heuristic.
Giả sử max dánh vào (x,y), chúng ta chạy ngược lên trên, đến khi chạm biên hoặc đủ năm ô(có khả năng ăn), chúng ta đếm xuống lại đến khi (chạm quân thù || chạm biên || đến ô thứ 5 kể từ (x,y) ), h(hàm heuristic)+= tổng (bình phương số quân liên tục)
Chẳng hạn trên một đường chạy có 2 2 4 quân liên tục thì h+=2*2+2*2+4*4
Tương tự cho ba phương còn lại.
Tôi thêm vào một chút heuistic nữa, nếu có 4 com liên tục thì h+=100*100, nếu 5 con thì h+=200*200 -> giúp biết nguy cơ thua hay thắng cao
Thêm heuristic chặn, (xét đường ngang, bạn tự làm các đương khác)
nếu x+1 < m (nằm trong) và (x+1,y) quân thù h+=1;
nếu x+2 < m và (x+2,y) quân thù h+=1.5;
Luôn giả sử máy là max
bạn tìm hiệu max-min và lấy giá trị lớn nhất
Heuristic trên chỉ đánh với những người đánh dở, nhưng nó đủ hay đối với thủ tục min-max

stuuns
22-12-2004, 22:10
that su khi doc cac dong cua Hoang tui that su ko the hinh dung nhu the nao....co the chua hieu cu the lam...nhung tui thay neu chi dung Heuristic ko thi ko the nao danh hay hon duoc...chi co the vet can het cac nuoc di theo tung buoc cua nguoi choi...nhung khi tui tinh thi ko du bo nho neu lam nhu the...=>bo tay...danh cho may ngu mot ti vay....

darkmagician
23-12-2004, 11:51
chỉ có mấy thằng ngu mới có khả năng "áp dụng" vét cạn cho caro nói riêng, cờ quạt nói chung. Không biết thì im đi cho người khác nhờ.

monkeyvu
24-12-2004, 16:05
Mấy bác chắc đang làm bài TTNT , darkmagician là ai mà chửi người khác nặng quá dzậy ? :angel_not

htbn_hoang
24-12-2004, 16:25
Đừng nói nhau nặng vậy chứ. Bạn Stuuns không hiểu heuistic của tui à. Vậy thì bạn hãy làm từng bước thôi. Tức là đầu tiên bạn xét cột trước, áp dụng heuistic đó cho cột, sau đó thêm dần vào. Bạn hãy cố đọc lại một lần nữa và đi từ từ xem, có thẻ bạn sẽ có heuistic tốt hơn của tui thì sao.
Còn bạn đừng bao giờ làm chương trình trò chơi bằng cách vét cạn, trừ khi bạn chắc là nó không có quá nhiều trường hợp. Lập trình trò chơi chỉ có hai cách là heuistic và dạng cây có kèm theo việc "tỉa cành". Cái sau khó hơn nhiều nhưng hiệu quả thì hơn hẳn.
Thầy tui có cho heuistic rất dỏm là h()=số đường mở đối với max-soos đường mở đối với min, trong đó đường mở là là đường còn ăn được
Bạn có thể bắt đầu từ đó. Chúc bạn làm được

khanh_phunhuan
04-02-2005, 15:06
Viết chương trình caro mà sử dụng min-max là quá xoàng. Tôi từng viết một chương trình theo thuật giải đó . Nó có nhược điểm nếu người chơi đã đánh thắng máy thif sau đó cứ việc lặp lại trình tự đi như trước , người chơi sẽ tiếp tục thắng máy . Máy không biết rút kinh nghiệm cho những lần thua . Ai có thể viết một chương trình caro có khả năng rút kinh nghiệm tui gọi người đó là sư phụ luôn .

trungdx
11-03-2005, 14:30
Sao mọi người đang bàn về viết chương trình mà có bạn lại vào đây chủi vậy, không biết thì thôi sao cứ tinh vi thế có giỏi thì làm 1 chương trình hay hơn xem nào.
Nói chung thì mình chưa làm trò chơi caro bao giờ nhưng xem các bạn nói thì cũng hơi xoàng, mình có làm chương trình chơi cờ vua có sử dụng mạng newral nên máy có thể tự học và cải tiến cách chơi được, mình nghĩ là áp dụng kĩ thuật này vào trò caro thì không khó lắm, chúc các bạn thành công.

shuto_uke
17-03-2005, 12:46
Trước tôi cũng có viết chương trình chơi cờ caro máy đánh với người. Chả có thuật toán gì ở đó cả, tôi viết thủ tục ước lượng cho mỗi ô trống ( nơi máy có thể đánh vào ). Thủ tục cũng tương đối đơn giản, tôi nhớ mình làm 8 thang điểm để đánh giá, với mỗi ô trống xét theo 8 hướng. Chương trình viết bằng Pascal (!) chỉ với độ sâu là 1 nhưng được cái nó chơi cũng khá, đấy là tôi thấy mọi người bảo vậy chứ tôi wánh cờ kém lém ! :)

anhlavodoinb1
23-07-2012, 15:56
Bạn đã biết thủ tục min-max, do đó tui chỉ nói về cách cài đặt Heuristic. Tôi đã làm bài này và đánh khá hay.
Trước tiên chúng ta giả sử cả min và max dùng cùng thật toán, cung một hàm Heuristic.
Giả sử max dánh vào (x,y), chúng ta chạy ngược lên trên, đến khi chạm biên hoặc đủ năm ô(có khả năng ăn), chúng ta đếm xuống lại đến khi (chạm quân thù || chạm biên || đến ô thứ 5 kể từ (x,y) ), h(hàm heuristic)+= tổng (bình phương số quân liên tục)
Chẳng hạn trên một đường chạy có 2 2 4 quân liên tục thì h+=2*2+2*2+4*4
Tương tự cho ba phương còn lại.
Tôi thêm vào một chút heuistic nữa, nếu có 4 com liên tục thì h+=100*100, nếu 5 con thì h+=200*200 -> giúp biết nguy cơ thua hay thắng cao
Thêm heuristic chặn, (xét đường ngang, bạn tự làm các đương khác)
nếu x+1 < m (nằm trong) và (x+1,y) quân thù h+=1;
nếu x+2 < m và (x+2,y) quân thù h+=1.5;
Luôn giả sử máy là max
bạn tìm hiệu max-min và lấy giá trị lớn nhất
Heuristic trên chỉ đánh với những người đánh dở, nhưng nó đủ hay đối với thủ tục min-max

có thể cho mình xin tài liệu về vấn đề này được không, mình cũng định phát triển 1 game