Thuật toán AI dựa trên mảng Gomoku?

Question

Cách quay lại (suy nghĩ hơn 20 năm) Tôi gặp phải một mã nguồn trò chơi Gomoku trong một tạp chí mà tôi đã nhập vào cho máy tính của mình và có rất nhiều niềm vui với.

Trò chơi rất khó để giành chiến thắng, nhưng thuật toán cốt lõi cho AI máy tính thực sự đơn giản và không chiếm nhiều mã. Tôi tự hỏi nếu có ai biết thuật toán này và có một số liên kết đến một số nguồn hoặc lý thuyết về nó.

Những điều tôi nhớ là về cơ bản nó đã phân bổ một mảng bao phủ toàn bộ bảng. Sau đó, bất cứ khi nào tôi, hoặc nó, đặt một mảnh, nó sẽ thêm một số trọng lượng cho tất cả các vị trí trên diễn đàn mà các mảnh có thể sẽ tác động.

Ví dụ (lưu ý rằng các trọng chắc chắn sai như tôi không nhớ những):

1 1 1 
2 2 2 
    3 3 3 
    444 
1234X4321 
    3 3 3 
2 2 2 
1 1 1 

Sau đó, nó chỉ đơn giản là quét mảng cho một vị trí mở với giá trị thấp nhất hoặc cao nhất.

Những điều tôi mờ trên:

• Có lẽ nó có hai mảng, một cho tôi và một cho bản thân và đã có một phút/trọng lượng tối đa?
• Có thể đã hơn đối với thuật toán, nhưng cốt lõi của nó là cơ bản một mảng và số gia quyền

Liệu chiếc nhẫn này một cái chuông với bất cứ ai ở tất cả? Bất cứ ai có bất cứ điều gì có thể giúp đỡ?

Answer 1

Đọc mô tả của bạn, và suy nghĩ một chút về nó, tôi nghĩ rằng nó có thể làm việc với một mảng duy nhất, chính xác cách bạn mô tả.

Để thực hiện mục tiêu nhận được năm-trong-một-hàng, bạn phải (a) ngăn chặn các đối thủ từ thành công và (b) thành công cho mình.

Để thành công, bạn phải đặt đá gần những viên đá khác bạn đã có trên bảng, do đó, bạn nên thêm điểm tích cực cho các trường bên cạnh đá của bạn có thể tham gia vào một hàng. Hoặc là ví dụ tuyến tính bạn đã cung cấp, hoặc một cái gì đó bậc hai có thể sẽ hoạt động tốt.

Để ngăn đối thủ của bạn thành công, bạn phải đặt đá bên cạnh /đá của cô ấy. Nó đặc biệt tốt nếu bạn tấn công hai con chim với một viên đá duy nhất, vì vậy đá của đối phương sẽ tăng giá trị của các cánh đồng xung quanh giống như cách bạn làm - càng nhiều đá anh ta xếp hàng, điểm càng cao, và càng có nhiều khả năng thuật toán sẽ cố gắng cắt đối thủ ra.

Điều quan trọng nhất ở đây là trọng số của các trường khác nhau, và liệu đá của đối phương có trọng số khác với của bạn hay không. Thật không may tôi không thể giúp với điều đó, nhưng các giá trị nên được hợp lý đơn giản để tìm ra thông qua thử và sai khi bản thân trò chơi được viết.

Tuy nhiên đây là một cách tiếp cận rất cơ bản và sẽ được thực hiện tốt hơn bằng thuật toán tìm kiếm cây. Tìm kiếm trên Google, có một số liên quan paper on Threat search, có vẻ hoạt động tốt với Gomoku.Giấy phía sau một bức tường trả tiền mặc dù:/

Answer 2

Tôi chưa đọc bài báo, nhưng từ mô tả tôi đoán sẽ là một số hình thức của Minimax algorithm

Answer 3

Đó là một trò chơi cổ - Tôi tìm thấy mã trên Planet Source Code. Tôi chơi trò chơi này trong đại học và trong 286 ngày có phiên bản BASIC của nó.

Answer 4

Tôi thấy thuật toán này bạn đã đề cập - nó khá đơn giản và nhanh chóng (không có backtracking :-)) và nó phát rất tốt :-) Tôi phải có nguồn ở đâu đó nhưng đó là rất nhiều năm trước ... trọng lượng cho đá của bạn tùy thuộc vào số lượng đá khác ở gần, và trọng lượng của đá viên. Chúng thấp hơn nên thuật toán ưa thích chiến lược tấn công.

Nhưng điều này tất nhiên là thuật toán rất nhỏ. Chiến lược chiến thắng đã được tìm thấy. Xem bài báo này: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens. Go-Moku and Threat-Space Search. Nó đã giúp tôi rất nhiều khi tôi viết chương trình của riêng mình. Bằng cách này bạn sẽ có thể viết chương trình đó là rất tốt trong việc tấn công đối thủ và tìm kiếm các kết hợp chiến thắng.

Answer 5

Làm việc trên phiên bản nguồn mở dành cho iPhone.

Nhấn tôi nếu muốn tham gia!

https://github.com/kigster/kigomoku

Answer 6

Dưới đây là chương trình mà bạn đang tìm kiếm ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw/gomoku.c

Nó gần như là 40 tuổi