VBA & Cờ vua!

[HongViet]

Tôi có 1 ít kiến thức về cờ vua & không nhiều lắm về VBA;
Và hôm qua tôi có 1 í tưởng xin nhờ các cao thủ chỉ vẽ về thuật toán (cái này tôi thua cả thằng chột) để giải quyết vấn đề sau:
Trên 64 ô bàn cờ vua ta nên đặt 1 con ngựa ở nơi nào để nó tới được nhiều nơi nhất trên bàn cờ mà không lặp lại!
Rất mong các bạn chỉ giáo!:wall: :friend: :wall:

 

[IChiNoVa]

Cái này... , nhà em nói lý thuyết nhé: (hì hì..., chỉ được cái mồm)
Bạn có thể dùng thuật toán "quay lui, vét cạn", có người còn gọi là "thử và sai"
Theo cách nhà em làm thì nó vầy nè:

Bạn cho con mã đi đến ô tiếp theo, nếu ô đó thỏa điều kiện là chưa đi qua thì chấp nhận ô đó và tiếp tục tìm ô tiếp theo để đi, còn nếu ô đó không thỏa thì quay lại ô cũ để tìm nước đi mới.

Để biết 1 ô nào đó đã đi qua hay chưa thì khi con mã đi qua ô nào, bạn phải đánh dấu vào ô đó.

Bạn chỉ cần dùng mảng [1...8] mà không cần mảng 2 chiều.
Để quay lui bạn dùng lệnh nhảy Go to (chẳng biết trong VB lệnh Go to nó như thế nào), hay đệ quy.

 

[Bình_OverAC]

Nhớ quá. Hồi xưa em từng làm cái này trên Pascal. Gồm 2 bài:
- Bài 8 con hậu: Xếp sao có thể đặt 8 con hậu trên một bàn cờ sao cho cả 8 con này không con nào ăn được con nào.
- Bài con mã đi tuần: tức là bài mà bác Hongviet nói em đã làm nhưng mà Pascal nó chạy không nổi. Nghe đồn là trên lý thuyết có thì có chổ để con mã có thể đi được tất cả các ô từ bất kỳ vị trí nào trên bàn cờ.

Còn thuật toán thì như Ichinova nói. Em đã dùng phương pháp vét cạn

 

[adam_tran]

Tôi cũng góp "mồm" vào:
Tôi đọc ở đâu đó là nếu dùng thuật toán tính toán để thực hiện các bước đi của các quân cờ trên bàn cờ thì chẳng ăn thua, vì như thế là người tính chứ không phải máy tính. Làm sao có thể vét cạn hay đặt ra tất cả các khả năng được khi mỗi nước cờ có cả nghỉn khả năng và rất nhiều điều kiện ràng buộc, kiểm tra! Có 1 thuật toán dựa trên cách làm việc của con kiến: Tất cả các con kiến đều đi kiếm ăn, con nào đi xa tìm được ít mồi thì chết. Con nào kiếm nhiều mồi, đường ngắn thì sống. Trên cơ sở đó để xây dựng 1 hàm tự nhân những khả năng có thể xảy ra lên, sau đó trả về 1 kết quả. Các hàm này sẽ loại trừ lẫn nhau sau 1 thời gian nào đó. Cách xây dựng level của phần mềm đánh cờ cũng vậy. Đơn giản nó chỉ hạn chế số lần nhân bản của hàm đó trong 1 đơn vị thời gian và khoảng tối ưu rộng hơn, giải thuật tìm ra kết quả ít có khả năng tối ưu hơn, kết quả là level thấp hơn.
Tóm lại, để dùng VBA làm trò chơi cờ vua thì... Bill Gate cũng bó tay.

Xếp sao có thể đặt 8 con hậu trên một bàn cờ sao cho cả 8 con này không con nào ăn được con nào

Có lẽ là 7 con thì đúng hơn, 8 làm sao mà xếp nhĩ?

 

[IChiNoVa]

Có lẽ là 7 con thì đúng hơn, 8 làm sao mà xếp nhĩ?

À, cái này nhà em làm rồi, đúng 8 quân hậu, chạy tốt, kết quả tốt. Nhà em dùng mảng 1 chiều
Còn bài con mã đi tuần đi qua tất cả các ô, mỗi ô chỉ một lần, Pascal chạy cũng tốt luôn, không ì ạch tẹo nào, kết quả tốt.

 

[HongViet]

. . . .Tóm lại, để dùng VBA làm trò chơi cờ vua thì... Bill Gate cũng bó tay

Chắc vậy, nhưng 1 con ngựa thì có thể?! & mình thấy rằng trong excel có thuận tiện là các ô sẵn có rồi nên định phát triển lúc rỗi. Vậy các bạn giúp mình thêm nữa nha!
:dzo:

 

[hai2hai]

Tôi cũng góp "mồm" vào:

Tóm lại, để dùng VBA làm trò chơi cờ vua thì... Bill Gate cũng bó tay.

Rất rất nhiều sourcecode viết bằng VB (nghĩa là người làm VBA có thể vận dụng được code đó nếu đủ trình độ) viết hẳn một game chơi cờ vua (người chơi với người (có thể chơi qua mạng), người chơi với máy (AI - Artificial Intelligent ở dạng giản đơn). Vì thế ko có cái gì là ko thể cả. Bill G bây giờ ko coding chứ ko phải ko làm được.

Thế giới còn rộng lớn lắm!

Cheers!

 

[Bình_OverAC]

Rất rất nhiều sourcecode viết bằng VB (nghĩa là người làm VBA có thể vận dụng được code đó nếu đủ trình độ) viết hẳn một game chơi cờ vua (người chơi với người (có thể chơi qua mạng), người chơi với máy (AI - Artificial Intelligent ở dạng giản đơn). Vì thế ko có cái gì là ko thể cả. Bill G bây giờ ko coding chứ ko phải ko làm được.

Thế giới còn rộng lớn lắm!

Cheers!

Anh hiểu nhầm ý của anh Adam rùi.
Ý của anh Adam là nói về cái vụ. Một phần mềm chơi cờ vua hoàn hảo nhất. Để có thể đưa ra một quyết định về con đường thằng thua ngay từ bước đầu, hay nếu phần mềm này đấu lẩn nhau thì kô biết ai thắng ai thua. Cái này em nghĩ cũng làm được. Nhưng chắc là phải mạnh gấp nhiều lần Deep Blue II.

 

[hai2hai]

Anh hiểu nhầm ý của anh Adam rùi.
Ý của anh Adam là nói về cái vụ. Một phần mềm chơi cờ vua hoàn hảo nhất. Để có thể đưa ra một quyết định về con đường thằng thua ngay từ bước đầu, hay nếu phần mềm này đấu lẩn nhau thì kô biết ai thắng ai thua. Cái này em nghĩ cũng làm được. Nhưng chắc là phải mạnh gấp nhiều lần Deep Blue II.

Cái này bàn ở đây làm cái gì nhỉ?

Viết được 1 phần mềm chơi cờ là tốt rồi. Thế mọi người định làm Deep Blue III à? Cái đó liên quan nhiều đến cả 1 chiến lược lẫn ti tỷ các thuật toán chứ bàn với VBA làm gì.

Nhưng với 1 phần mềm để cho phép 2 người chơi cờ qua mạng hay một phần mềm chơi cờ với máy tính cỡ đơn giản thì ko có gì đâu. Nhiều người làm lắm rồi. Chúng ta bàn đến cái đơn giản thôi, Deep Blue làm gì cho mệt mà :error:

Mọi người toàn bàn chuyện giống kiểu...viết ERP trên pascal for DOS ấy. Làm cái giản đơn nhưng thực thi đã.

Ví dụ về một kế hoạch phát triển cờ vua sơ bộ

Giai đoạn 1: Xây dựng môi trường chơi cờ trên .... VBA chẳng hạn
- Vẽ 1 bàn cờ cùng các quân cờ (cái này cần đồ họa thật đẹp)
- Thiết lập thư viện hỗ trợ di chuyển quân cờ theo đúng luật cờ
- Thiết lập cơ chế cho nhiều người chơi qua mạng và cơ chế người chơi với máy
- Thiết lập các công cụ ghi lại các nước cờ, v.v....
- Thiết lập các KB (thế cờ) trong thư viện
- ....

Giai đoạn 2: Áp dụng các thuật toán, giải thuật trí tuệ nhân tạo vào khi tính toán nước cờ cho máy tính
- Xây dựng engine ......
- Các giải thuật: Neural Network , ...
- ... Chắc phải hỏi bọn IBM xem họ làm gì chứ mình ko đủ trình độ cái này.

Giai đoạn 3: Turning, optimize....
- Chả biết làm gì với giai đoạn này nhưng chắc chắn còn nhiều việc, nhiều việc lắm lắm.... để làm ra cái gọi là "Một phần mềm chơi cờ vua" (chứ ko dám nói là "hoàn hảo nhất." )
- ....

Làm cái gì cũng phải vạch kế hoạch ra từ đơn giản đến phức tạp chứ chưa gì cứ vét cạn với deep blue thì bao giờ ra 1 phần mềm?

Ví dụ: (Cờ vua thì nhiều rồi (thậm chí thằng Borland nó có cả sample source code), thôi thì cờ tướng cho ...lạc đề tý nhé

1. Chinese Chess
2. Multi-Players (over net) Chinese Chess

 

[Tuanktcdcn]

Mình có sourcecode của Hẵng Borland nhưng đọc chẳng hiểu gì cả. Nếu chúng ta bàn thì chỉ bàn về giải thuật thôi.

 

[hai2hai]

Trên 64 ô bàn cờ vua ta nên đặt 1 con ngựa ở nơi nào để nó tới được nhiều nơi nhất trên bàn cờ mà không lặp lại!
Rất mong các bạn chỉ giáo!:wall: :friend: :wall:

Tớ thì lại baby về món cờ này nên chỉ có thể kiếm sourcecode cho Hongviet tham khảo thôi.

Title: Horse Move - Chess Game
Description: This is a nice game using the 64 unique horse moves in the chess board. I have used very limited coding and given a good gaming software. Enjoy!!

Đúng ý của tác giả của topic này nhé

 

[HongViet]

Cảm ơn B. 2Hai2, nhưng chưa đủ TrĐộ để hiểu!

Mà tôi làm như vầy (theo kiểu thô sơ nhất hạng):
Khai báo biến DaDi(64) As Boolean để loại ~ ô đã đi qua
Viết hàm NuocKeTiep ( ViTri As String) As String để chọn nước kế tiếp. Tuỳ thuộc hoàn toàn vô ViTri mà có thể có tối đa 2(4 ô), 3 (8 ô), 4 (20 ô) , 6 (16 ô) hay 8 (16 ô) phương án ngẫu nhiên;
(Tất nhiên với 8 nước đi ngẫu nhiên có thể là khó nhất! tại C3 & 15 ô tương tự. Nên rất cần các bạn giúp cho ~ í kiến chỗ này)
Mong các bác giúp hay ngăn chặn nếu tôi đi không đúng hướng; Rất cảm ơn!:dance2:

 

[IChiNoVa]

Tiếp theo cái Horse Move của anh Hải to Hải, nhà em vừa viết xong bài xắp xếp 8 quân hậu rồi đây.

Thuật toán: quay lui vét cạn hay thử sai và lần ngược.

Nhà em dùng 2 mảng để đánh dấu các đường chéo mà các quân hậu đi qua.

1. Cheotong(16): đây là đường chéo xiên lên từ trái sang phải, ở đường chéo này, các ô cùng đường chéo thì có tổng của cột và dòng đều bằng nhau.

2. Cheohieu(16): đây là đường chéo đi xuống từ trái sang phải, các ô trên cùng 1 đường chéo này thì có hiệu của dòng và cột đều bằng nhau.

 

[HongViet]

Vầy: Khai biến DDi(64) để ghi ~ ô đã đi
Viết hàm NuocTiep ( ViTri ) để chọn nước kế tiếp. Tuỳ vô ViTri mà có thể có tối đa 2(4 ô), 3 (8 ô), 4 (20 ô) , 6 (16 ô) hay 8 (16 ô) phương án ngẫu nhiên;

 

[SA_DQ]

Mình mới tìm ra chổ này:

Thuật toán Láng giềng gần nhất là một trong những thuật toán đầu tiên được dùng để tìm lời giải cho bài toán người bán hàng, và thường cho kết quả chênh lệch trong phạm vi 20% so với đường đi tối ưu. Nó chạy nhanh hơn rất nhiều so với việc kiểm tra mọi tuyến đường và một số thuật toán khác.

Các bước của thuật toán:

Chọn một nút bất kỳ làm nút xuất phát và đây là nút hiện hành
Đánh dấu nút hiện hành là đã được đi qua
Tìm một nút chưa đi qua có khoảng cách đến nút hiện hành là ngắn nhất, đánh dấu nút này là nút hiện hành mới
Nếu chưa đi qua tất cả các nút thì quay lại bước 2
Thứ tự mà các nút được đi qua chính là kết quả của thuật toán.

Thuật toán láng giềng gần nhất dễ cài đặt và chạy nhanh, nhưng đôi khi nó có thể bỏ qua các tuyến đường ngắn hơn mà mắt thường dễ nhận ra. Kết quả của thuật toán này cần được kiểm tra trước khi sử dụng để phòng trường hợp một tuyến đường ngắn hơn bị bỏ qua.

Trong trường hợp xấu nhất, thuật toán này có thể tính toán ra các tuyến đường dài gấp r lần tuyến đường tối ưu. Trong đó, r là một tỷ lệ tùy ý, nghĩa là, với mỗi hằng số r, tồn tại một bài toán người bán hàng sao cho độ dài của tuyến đường là kết quả của thuật toán láng giềng gần nhất lớn hơn hoặc bằng r lần độ dài tuyến đường tối ưu.

Lấy từ “http://vi.wikipedia.org/:wall:

 

[HongViet]

Con ngựa này còn ngù ngờ lắm, mong các bác chỉ thêm

Sau gần 2 tháng nhọc công, cũng xong bước đầu tác phẩm về con ngựa; Tất nhiên còn nhiều khiếm khuyết mong bà con cô bác gần xa chỉ giáo!
Trong nữa đầu của năm, mật khẩu là gì cũng được!
Hẹn khi có nhiều góp ý sẽ có những phiên bản khác tinh tuý hơn!. Xin chân thành cảm ơn ~ người đã & đang quan tâm!

 

[Bình_OverAC]

Bác ơi, em load lên giúp bác rồi nhưng em không mở ra xem được.

 

[IChiNoVa]

Gõ ô bắt đầu là A1 thì đi được đến ô thứ 36 là hết, nhảy luôn sang ô thứ 63

Không cho xem code thì ... biết đâu mà lần.

 

[HongViet]

Sẽ gởi khoá cho ~ ai có nhu cầu!

Mình sẽ gởi khoá cho IchiNoVa & Bình_OverAC; Nhưng ngược lại IChi_ & Bình_ cho mình vài góp í đấy nha! :friend:
PC: Các bạn không nên dùng fím SHIFT để vô hiệu hoá Autpen(); Vì như vậy sẽ cắt đoạn đầu của CTrình! :dzo:

 

[Bình_OverAC]

Thưa bác HongViet, sau khi xem con ngựa của bác chạy em thấy nó chạy chưa đạt yêu cầu, em chỉ nói về mặt thể hiện chứ còn thực sự xem code xong em chẳng biết là trong đó có gì nữa. (Em xem qua và bị tá hỏa tam tinh luôn. :alcon: )
vậy nên em viết lên connguaB này, bề ngòai giống con ngựa A của bác, nhưng bên trong thì có khác tí.
1. Ý tưởng:
- Biến bàn hình vuông (2 chiều) thành một chuổi các vị trí (1 chiều)
- Lưu dữ vị trí của các bước đi trong một mãng một chiều.
- Dùng vòng lặp để nếu như con ngựa đi hết đường mà vẫn chưa đi xong thì quay trở lại tìm đường khác.
2. Triển khai:
- Xác lập các bước có thể đi được --> tạo ra hàm vitriden(vitri, buocdi), có 2 đối số là vitri và buocdi:
+ vitri: vị trí hiện tại của con ngựa
+ Buocdi: các hướng đi của con ngựa có thể đi được (tối đa 8 hướng xung quanh)
+ giá trị trả về: Nếu buocdi của con ngựa đi về hướng ra ngoài bàn cờ thì nó trả ra giá trị là -1, ngược lại trả ra một giá trị là một vị trí khác trên bàn cờ

- Lập câu lệnh đi: --> Sub nuocdi(vitriden, thehien)
+ vitriden: là điểm mà con ngựa đi đến
+ thehien: là cách mà nó thể hiện ở vị trí mà nó đến. (có thể là một ký tự hoặc chính là số thứ tự của nuocdi đi)

- Lập câu lệnh tính nước đi --> Sub gogo(vitridau)
+ Dùng vòng lặp đề tính qua tất cả các vị trí mà con ngựa có thể đi được, thể hiện qua biến i (biến này chính là số thức tự của nước đi) nếu nó không đi được nó sẽ đi lùi (i giảm) nếu nó đi được i tăng
+ Dùng mãng CB(a) để lưu giữ các hướng đã đi từ vị trí a để khi quay lại vị trí a thì biết đường mà đi hướng khác.
+ vitridau là giá trị của vị trí đầu tiên mà chúng ta nhập vào để cho con ngựa bắt đầu chạy.

3. Giao tiếp người và máy:
- Tạo ra để khởi động (lấy vị trí đầu) --> Sub khoidong()
- Quá trình chạy của con mã được thể hiện qua sub nuocdi() để có thể cho người xem mõi mắt. :biggrin:

Kết luận: nếu bạn thực sự muốn xem con mã đã đi như thế nào thì bạn nên tắt hết các chương trình khác, cho con mã khởi động, sau đó bạn tắc màn hình đi chơi vài tiếng sau quay lại :biggrin: Nếu bạn không có kiên nhẫn chờ thì nhớ nhấn Ctrl + Break để cho nó dừng lại nhé.