Pages: [1] 2 Go Down
  Print  
Author Topic: Có ai biết thuật toán trong Cờ Caro không ?? (Read 15176 times)
0 Members and 1 Guest are viewing this topic.
CTBer quen thuộc
***

MSN Messenger - duongtran_vl Yahoo Instant Messenger - strangevirus2000
Email
Đánh giá: +1/-0
Offline Offline
Posts: 285
« on: February 21, 2004, 10:28:21 am »

Có bác nào biết thuật toán trong Cờ caro không ạ ? Chỉ bảo em với .
Không rõ mấy người viết cái trò XO hay BKro họ có thuật toán như thế nào . Mong các bác chơi caro giỏi  chỉ bảo giúp.Nêu 1 số bài hay cũng được ạ .
                                            Thank advance.
V.I.P
******



Đánh giá: +47/-11
Offline Offline
Posts: 336
« Reply #1 on: February 26, 2004, 06:39:50 am »

Chào đồng chí Dương Trần,

Theo tớ biết, có nhiều cách tiếp cận để giải quyết bài toán cờ ca rô hay cờ nói chung. Ở đây tớ nêu ra 2 cách:

- Xây dựng một hệ thống dựa trên tập luật (giống như hệ chuyên gia).

- Sử dụng các giải thuật tìm kiếm để tìm ra nước đi tối ưu (Duyệt với một độ sâu nào đó)

Theo cách tiếp cận thứ nhất, ta phải xây dựng được tập luật, mỗi luật được biểu diễn dưới dạng sau:
If(State = A) then Move(A,x,B)
-   Trong đó A là trạng thái hiện tại của bàn cờ
-   Move(A,x,B) thực hiện nước đi tốt nhất x (dựa trên kinh nghiệm) tại trạng thái A của bàn cờ; B là trạng thái tiếp theo của bàn cờ sau khi thực hiện nước đi x
Tuy nhiên, cách tiếp cận này gặp phải một số vấn đề sau:
-   Số trạng thái của bàn cờ quá lớn, do đó không thể liệt kê hoặc lưu trữ được toàn bộ tập luật
-   Việc xác định nước đi tốt nhất tại trạng thái cho trước của bàn cờ là rất khó
Do đó, người ta thường giải quyết bài toán theo cách tiếp cận thứ 2: coi bài toán chơi cờ như trường hợp đặc biệt của lớp các bài toán tìm kiếm
(phần tiếp: biểu diễn trạng thái bàn cờ, hàm lượng giá và giải thuật min-max, anpha-beta)
V.I.P
******



Đánh giá: +47/-11
Offline Offline
Posts: 336
« Reply #2 on: February 26, 2004, 07:14:24 pm »

Biểu diễn không gian trạng thái bàn cờ

Như đã nói ở trên, bài toán cờ ca rô có thể mô tả như một trường hợp đặc biệt của lớp các bài toán tìm kiếm. Đối với lớp các bài toán này, giải thuật tìm kiếm sẽ duyệt trên không gian trạng thái của bài toán, bắt đầu từ trạng thái khởi đầu cho đến khi tìm được trạng thái biểu diễn lời giải. Nếu ta mô phỏng không gian trạng thái của bàn toán như một cây (tree) thì giải thuật tìm kiếm sẽ bắt đầu từ gốc, theo một "strategy" nào đó, duyệt trên các node trung gian cho đến khi tìm được lời giải trên node lá của cây.

Như vậy, vấn đề đầu tiên cần phải giải quyết là biều diễn không gian trạng thái của bàn cờ như thế nào. Với cờ ca rô, bạn có thể đơn giản biểu diễn bàn cờ như 1 mảng 2 chiều, phần tử của mảng mang giá trị 0 nếu ô trống, 1 nếu ô chứa nước đi của bạn, -1 nếu ô chứa nước đi của đối thủ. Tuy nhiên, đối với một số loại cờ khác như cờ vua, cờ tướng thì việc biêu diễn sẽ phức tạp hơn. Trạng thái của bàn cờ phải mô tả được tất cả các khả năng có thể có của bàn cờ.

Bước tiếp theo là mô tả tất cả cái nước đi có thể đối với một trạng thái bất kỳ của bạn cờ. Tại mỗi trạng thái của bàn cờ, bạn (hay đối thủ có thể thực hiện được một số nước đi hợp lệ. Khi thực hiện các nước đi này, bàn cờ sẽ chuyển sang trạng thái mới. Một lần đi có thể biểu diễn như sau:
If(State==A, move(A,x,B)) then State = B
Trong đó:
A là trạng thái hiện tại
move(A,x,B) là thực hiện nước đi x tại trạng thái A
B là trạng thái bàn cờ sau đi đi nước đi x

Khi đã biểu diễn được trạng thái của bàn cờ và các nước đi hợp lệ ứng với từng trạng thái, không gian trạng thái của bàn cờ có thể được biểu diễn như một cây, với node gốc (roof) là bàn cờ ca rô lúc ban đầu (không có quân cờ nào), một node B ở mức i (level i-child) đuợc xây dựng từ một node A ở mức i - 1 (parent) ứng với một nước đi hợp lệ move(A,x,B). Cuối cùng là các node lá. Các node này tương ứng với các trạng thái kết thúc của ván cờ (bạn thua, thắng, hoặc hòa). Lời giải cho bài toán chính là các node lá ứng với trạng thái "thắng" (mức ưu tiên 1) hoặc hòa (ưu tiên 2).

Đến đây, ta có thể thấy giải thuật này chính là một trường hợp của bài toán tìm kiếm. Nếu bạn có một máy tính với tài nguyên "đủ lớn", bạn có thể tìm ra trình tự các nước đi (đuờng đi từ gốc tới lá) sao cho kết thúc của ván cờ là "tốt nhất" với bạn.

Tuy nhiên, các thuật toán cờ cũng có nhiều điểm khác biệt. Ví dụ:
- Bạn không thể biết trước được nước đi của đối thủ
- Kích thước không gian trạng thái bàn cờ là rất lớn (khoảng 15 mũ 80 nodes với cờ vua, 200 mũ 300 với cờ vây,...). Đặc biệt với những loại cờ đơn giản như cờ ca rô, cờ vây thì không gian trạng thái thường lớn hơn do không có nhiều ràng buộc giữa các quân cờ.
- Việc đánh giá so sánh giữa các trạng thái bàn cờ (hay các nước đi) là rất khó (một nước đi có thể có lợi tại thời điềm hiện tại nhưng chưa chắc đã tốt ở các nước tiếp theo)

Do vậy, đối với các loại cờ thì cần các kỹ thuật tìm kiếm khác thay vì các phương pháp tìm kiếm thông thường.
(phần tiếp: hàm lượng giá và các giải thuật min-max, anpha-beta)
CTBer quen thuộc
***

MSN Messenger - duongtran_vl Yahoo Instant Messenger - strangevirus2000
Email
Đánh giá: +1/-0
Offline Offline
Posts: 285
« Reply #3 on: March 01, 2004, 05:32:44 pm »

Mong bác post tiếp em vẫn đang lắng nghe đây.
V.I.P
******



Đánh giá: +47/-11
Offline Offline
Posts: 336
« Reply #4 on: March 01, 2004, 11:45:45 pm »

Xin lỗi đ/c Dương Trần, tôi dạo này bận quá nên không post một mạnh được!  0:)

Hàm lượng giá và các giải thuật min-max, anpha-beta

Như đã nói ở trên, vì không gian trạng thái của bàn cờ là rất lớn và đặc tính đối kháng trong trò chơi, ta không thể sử dụng các phương pháp tìm kiếm thông thường (e.g. vét cạn) để tìm kiếm lời giải tối ưu. Các giải thuật áp dụng trong các trò cờ chỉ có thể tìm kiếm trong một không gian con các trạng thái của bàn cờ để cho "lời giải tốt tương đối" ứng với thời gian cho trước (2 phút với cờ vua). Giải pháp được thường được sử dụng trong cờ ca rô cũng như các loại cờ khác là tìm kiếm tới một độ sâu định trước (search up to certain level) hoặc tìm kiếm cho tới khi đạt tới thời gian cho phép (a wellknown methode: iterative deepening search).

Một vấn đề đặt ra ở đây là: làm sao có thể biết là trạng thái bàn cờ tìm được là tốt, làm sao so sánh giữa các trạng thái bàn cờ? Nói một cách khác là sao lượng giá trạng thái bàn cờ như thế nào. Bạn có thể nói: rất dễ, chỉ việc cho mỗi trạng thái của bàn cờ một giá trị! Nhưng có 2 vấn đề phát sinh là:

1. Không thể liệt kê cũng như đánh giá hết các trạng thái bàn cờ
2. Việc đánh giá này cũng không dễ dàng

Đây là vấn đề khó nhất gặp phải khi thiết kế một chương trình đánh cờ. Nó cũng đúng với người chơi cờ: Người chơi cờ giỏi là người có thể đánh giá thế cờ tốt hơn người khác!
Một giải pháp là dùng một hàm lượng giá (hay hàm mục tiêu) để lượng giá trạng thái của bàn cờ. Với hàm mục tiêu này mỗi trạng của bàn cờ sẽ tương ứng với một giá trị thực. Ví dụ, trong cờ vua, người ta có thể lượng giá bạn cờ bàng tổng (có trọng số) của các quân đen - tổng số các quân trắng. Việc lựa chọn các hàm mục tiêu như thế nào là tùy thưộc vào sự "nhạy cảm" của bạn. Trên thực tế, trong các trò cờ nổi tiếng như Deepblue, C3000, người ta dùng nhiều kỹ thuật khác nhau; eg. Machine learning, Artificial Neural Nets để tính giá trị cho các trạng thái của bàn cờ.

Sau khi đã xây dựng được hàm mục tiêu, mỗi node trên cây trạng thái sẽ có một giá trị nào đó. Vấn đề bây giờ là tìm một nút lá với giá trị "lớn nhất có thể" và tìm kiếm một đường đi từ nút gốc tới nút lá đó.

Vì tính chất đối kháng của trò chơi, bạn không thể biết trước nước đi của đối thủ, và việc tìm kiếm cũng hơi khác một chút. Giải thuật min-max được dùng phổ biết cho hầu hết các chương trình cờ (thậm chí cả Deepblue). Ý tường của giải thuật này là:
1. Gán người chơi nhãn MIN, Máy nhãn MAX
3. Xây dựng cây tới một độ sâu nào đó, trên mỗi level của cây, gán MAX nếu MAX đi, MIN nếu MIN đi.
4. Tính toán giá trị cho các nút lá (dùng hàm lượng giá),
5. Sau đó tính ngược từ dưới lên giá trị của các nút trung gian+nút gốc theo (1) SCORE(parent-MAX) = MAX (SCORE(all children))
       (2) SCORE(parent-MIN) = MIN(SCORE(all children))

Theo cách này, tới lân máy đi, máy sẽ chọn đi node có giá trị lớn nhất, khi lân người đi, anh ta có xu hướng chọn node có giá trị nhỏ nhất (để giảm thiệt hại). Kết quả là, cuối cùng trạng thái bàn có 'giá trị đối kháng" tốt nhất.

Thuật toán apha-beta có được trình bày dưới đây:

Initialise depthbound;
   Minimax (board, depth) =
   IF depth = depthbound
   THEN return static_evaluation(board);
   ELSE IF maximizing_level(depth)
           THEN FOR EACH child child of board
                                   compute Minimax(child, depth+1);
                    return maximum over all children;
           ELSE IF minimizing_level(depth)
                   THEN FOR EACH child child of board
                                           compute Minimax(child, depth+1);
                           return minimum over all children;

Call: Minimax(current_board, 0)

Ngoài ra, để làm giảm các nhánh duyệt người ta còn áp dụng nhiều ký thuật khác như: constraint processing, Backtracking, Backjumping, Backmarking, ..., Một thuật toán khác  được cải tiến từ thuật toán MIN-MAX là thuật toán Alpha-Beta.

Để tìm hiểu thêm, bạn có thể tham khảo "Trí tuệ nhân tạo" của Nguyễn Thanh Thủy.
Chúc thành công!

Thắng



Đánh giá: +0/-0
Offline Offline
Posts: 1
« Reply #5 on: April 27, 2004, 02:18:51 pm »

Khâm phục
CTBer quen thuộc
***

MSN Messenger - duongtran_vl Yahoo Instant Messenger - strangevirus2000
Email
Đánh giá: +1/-0
Offline Offline
Posts: 285
« Reply #6 on: December 16, 2005, 09:41:36 pm »

Đọc thì biết là thế nhưng viết chương trình thế nào thì vẫn chưa thử. Hôm nay có đứa hỏi đưa cho nó thuật toán này nhưng vẫn kô được.
Ai có chương trình viết trong C++ rồi không share cho em cái.
Admin
******




Đánh giá: +156/-23
Offline Offline
Gender: Male
Posts: 2220
« Reply #7 on: December 16, 2005, 10:08:14 pm »

Có chú deepsea viết rồi đấy.
CTBer quen thuộc
***

MSN Messenger - duongtran_vl Yahoo Instant Messenger - strangevirus2000
Email
Đánh giá: +1/-0
Offline Offline
Posts: 285
« Reply #8 on: December 16, 2005, 10:13:22 pm »

Không biết  liên lạc với deepsea thế nào? Nếu tiện xin cho tớ ngay được không?  :D
Thanks!
V.I.P
******


Yahoo Instant Messenger - ideepc
WWW Email
Đánh giá: +0/-1
Offline Offline
Gender: Male
Posts: 333
« Reply #9 on: December 16, 2005, 11:00:40 pm »

Thực ra thì thuật toán minimax hay alphabeta có độ phức tạp thuật toán rất lớn. deepsea muốn phát triển caro trên mobile nên tự xây dựng một thuật toán có độ phức tạp thấp hơn nhiều lần. Ứng với bàn cờ kích thước n*n thì độ phức tạp chỉ cỡ n^3 (tất nhiên chỉ áp dụng được cho cờ caro, các nước đi cũng không thể tốt như minimax hay alpha beta được).

Chị Dương có thể download tại www.ideepc.info. Có cả file nguồn và file chạy.

P/S: Mọi người ai có xem cũng đừng cười nhá. Tâm huyết của deepsea đấy :D. Mong nhận được ý kiến đóng góp của mọi người.
CTBer quen thuộc
***

MSN Messenger - duongtran_vl Yahoo Instant Messenger - strangevirus2000
Email
Đánh giá: +1/-0
Offline Offline
Posts: 285
« Reply #10 on: December 16, 2005, 11:28:27 pm »

Thanks!
Có  thể nói tóm tắt qua thuật toán của em kô? Tâm huyết mà
CTBer chăm chỉ
**




Đánh giá: +0/-0
Offline Offline
Posts: 121
« Reply #11 on: December 16, 2005, 11:52:58 pm »







deepsea viết:

Thực ra thì thuật toán minimax hay alphabeta có độ phức tạp thuật toán rất lớn. deepsea muốn phát triển caro trên mobile nên tự xây dựng một thuật toán có độ phức tạp thấp hơn nhiều lần. Ứng với bàn cờ kích thước n*n thì độ phức tạp chỉ cỡ n^3 (tất nhiên chỉ áp dụng được cho cờ caro, các nước đi cũng không thể tốt như minimax hay alpha beta được). Chị Dương có thể download tại http://www.ideepc.info." target="_blank">www.ideepc.info. Có cả file nguồn và file chạy.

P/S: Mọi người ai có xem cũng đừng cười nhá. Tâm huyết của deepsea đấy "4.gif". Mong nhận được ý kiến đóng góp của mọi người.

Chơi câu cuối khó nghĩ quá "4.gif" Ý kiến đóng góp nhé "10.gif"

 

- Chương trình viết hơi tồi

- Giải thuật không rõ ràng hay thể hiện giải thuật kém "10.gif"

.....

 

Khen này:

- Kiên nhẫn kinh hoàng :-S

 

 

Tạm thế đã
CTBer
*




Đánh giá: +0/-0
Offline Offline
Posts: 12
« Reply #12 on: December 17, 2005, 06:01:28 am »

Quote

Thực ra thì thuật toán minimax hay alphabeta có độ phức tạp thuật toán rất lớn. deepsea muốn phát triển caro trên mobile nên tự xây dựng một thuật toán có độ phức tạp thấp hơn nhiều lần. Ứng với bàn cờ kích thước n*n thì độ phức tạp chỉ cỡ n^3 (tất nhiên chỉ áp dụng được cho cờ caro, các nước đi cũng không thể tốt như minimax hay alpha beta được).

Chị Dương có thể download tại www.ideepc.info. Có cả file nguồn và file chạy.

P/S: Mọi người ai có xem cũng đừng cười nhá. Tâm huyết của deepsea đấy . Mong nhận được ý kiến đóng góp của mọi người.


 Hiệp ơi , tao đánh ván nào thắng ván đấy , mày viết sao cho máy nó đánh giỏi 1 tí chứ .:D
V.I.P
******


Yahoo Instant Messenger - ideepc
WWW Email
Đánh giá: +0/-1
Offline Offline
Gender: Male
Posts: 333
« Reply #13 on: December 17, 2005, 04:37:27 pm »

To Zoso: Em viết toàn bộ phần thuật toán mất một buổi tối. Đúng là AI của máy còn kém lắm, được cái độ phức tạp thuật toán thấp :D (nếu như tương minimax hay apha-beta vào thì khả năng chạy trên mobile là hơi bị khó). Thể hiện thuật toán rối vì thời gian viết code và hiệu chỉnh không có nhiều.

To duongtran: Em nghĩ nếu chị muốn máy chơi hay thì chị làm bằng minimax hay Alpha-beta đi. Chương trình của em viết chủ yếu là để thử nghiệm giải thuật với độ phức tạp thuật toán thấp thôi mà. Chứ chơi thì còn thua chương trình sử dụng hai thuật toán trên nhiều lắm. Nếu chị muốn biết cụ thể hơn về thuật toán thì liên lạc với em qua nick Yahoo: deepseatb. Em ko dám post thuật toán lên đây ( sợ múa rìu qua mắt thợ mà :D).
CTBer
*



Đánh giá: +0/-0
Offline Offline
Posts: 71
« Reply #14 on: December 26, 2005, 05:10:16 pm »

Lâu lâu mới gặp chị Dương, chị em đấy (tự hào). Đọc chẳng hiểu tí nào, kiểu này phải nghiên cứu thêm về Trí tuệ nhân tạo mới được.Bái phục.
Pages: [1] 2 Go Up
  Print  
 

SMF 2.0.2 | SMF © 2011, Simple Machines
Theme designed by CTBers