Thuật toán để chọn các chữ cái ngẫu nhiên cho trò chơi tìm kiếm chữ cho phép nhiều từ được viết chính tả

Question

Tôi đang tạo một trò chơi từ giống như boggle. Người dùng được cung cấp một mạng lưới các chữ cái như thế này:

O V Z W X 
S T A C K 
Y R F L Q 

Người dùng chọn một từ sử dụng bất kỳ chuỗi chữ liền kề nào, như từ "STACK" trên đường giữa. Các chữ cái được sử dụng sau đó được thay thế bằng máy, ví dụ: (các chữ cái mới trong chữ thường):

O V Z W X 
z e x o p 
Y R F L Q 

Lưu ý bây giờ bạn có thể đánh vần "OVeRFLoW" bằng cách sử dụng các chữ cái mới. Vấn đề của tôi là: Tôi có thể sử dụng thuật toán nào để chọn các chữ cái mới tối đa hóa số từ dài mà người dùng có thể đánh vần? Tôi muốn trò chơi trở nên thú vị và liên quan đến chính tả, ví dụ: 6 chữ cái đôi khi nhưng, nếu bạn chọn chữ cái xấu, trò chơi liên quan đến người dùng chỉ cần đánh vần 3 chữ cái và không nhận được cơ hội tìm những từ lớn hơn.

Ví dụ:

• Bạn chỉ có thể chọn một cách ngẫu nhiên chữ mới từ bảng chữ cái. Điều này không hoạt động tốt.

• Tương tự như vậy, tôi tìm thấy chọn ngẫu nhiên nhưng sử dụng tần số thư từ Scrabble không hoạt động tốt. Điều này hoạt động tốt hơn trong Scrabble Tôi nghĩ rằng khi bạn ít bị ràng buộc về thứ tự bạn sử dụng các chữ cái.

• Tôi đã thử một tập hợp danh sách, mỗi danh sách đại diện cho một trong số những người chết từ trò chơi Boggle. chọn từ một mặt chết ngẫu nhiên (tôi cũng tự hỏi liệu tôi có thể sử dụng hợp pháp dữ liệu này trong một sản phẩm) hay không. Tôi đã không nhận thấy điều này làm việc tốt. Tôi tưởng tượng các mặt xúc xắc Boggle đã được chọn theo một cách hợp lý nào đó, nhưng tôi không thể tìm ra cách thức này được thực hiện.

Một số ý tưởng tôi đã xem xét:

• Thực hiện một bảng của mức độ thường xuyên cặp thư xuất hiện cùng nhau trong từ điển. Vì lợi ích của lập luận, nói rằng E được nhìn thấy bên cạnh A 30% thời gian. Khi chọn một chữ cái mới, tôi sẽ chọn ngẫu nhiên một chữ cái dựa trên tần số của lá thư này xuất hiện bên cạnh một chữ cái liền kề được chọn ngẫu nhiên trên lưới. Ví dụ: nếu thư bên cạnh là E, chữ cái mới sẽ là "A" 30% thời gian. Có nghĩa là có rất nhiều cặp phong nha để sử dụng rải rác xung quanh bản đồ. Tôi có thể cải thiện điều này bằng cách làm cho các bảng xác suất của một lá thư xuất hiện giữa hai chữ cái khác.

• Bằng cách nào đó, tìm kiếm những từ nào có thể được viết trên lưới hiện tại, lấy các chữ cái mới làm ký tự đại diện. Sau đó tôi sẽ thay thế các ký tự đại diện bằng các chữ cái cho phép các từ lớn nhất được viết. Tôi không chắc chắn làm thế nào bạn sẽ làm điều này một cách hiệu quả tuy nhiên.

Bất kỳ ý tưởng nào khác đều được đánh giá cao. Tôi tự hỏi nếu có một cách phổ biến để giải quyết vấn đề này và những trò chơi chữ khác sử dụng.

Chỉnh sửa: Cảm ơn câu trả lời tuyệt vời cho đến nay! Tôi quên đề cập đến, tôi thực sự nhắm đến các yêu cầu bộ nhớ/CPU thấp nếu có thể, tôi có thể sử dụng từ điển SOWPODS (khoảng 250.000) và lưới của tôi sẽ có thể 6 x 6.

Answer 1

Tôi không biết về một thuật toán được đặt trước cho điều này, nhưng ...

Có một tập tin từ điển trong UNIX, và tôi tưởng tượng có một cái gì đó tương tự có sẵn trên các nền tảng khác (thậm chí có thể trong các thư viện java? - google nó). Dù sao, sử dụng các tập tin kiểm tra chính tả sử dụng.

Sau khi đánh vần một từ khi từ đó rơi ra, bạn có các chữ cái hiện có và khoảng trống.

1) Từ mỗi chữ cái hiện có, chuyển sang phải, sang trái, lên, xuống (bạn sẽ cần phải hiểu các thuật toán đệ quy). Miễn là chuỗi bạn đã xây dựng cho đến nay được tìm thấy ở đầu từ hoặc ngược từ cuối của các từ trong tệp từ điển, hãy tiếp tục. Khi bạn bắt gặp một khoảng trống, hãy đếm tần suất của các chữ cái bạn cần tiếp theo. Sử dụng các chữ cái thường xuyên nhất.

Nó sẽ không đảm bảo một từ khi bạn chưa kiểm tra kết thúc hoặc bắt đầu tương ứng, nhưng tôi nghĩ nó sẽ dễ thực hiện hơn nhiều so với tìm kiếm toàn diện và nhận được kết quả khá tốt.

Answer 2

Tôi nghĩ rằng điều này sẽ giúp bạn có được một bước gần hơn đến đích của bạn: http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

Dưới đây là một phương pháp đơn giản:

Viết một người giải quyết nhanh chóng cho các trò chơi bằng cách sử dụng danh sách từ tương tự mà người chơi sẽ sử dụng. Tạo ra 100 bảng có thể khác nhau một cách ngẫu nhiên (sử dụng tần số chữ có lẽ là một ý tưởng hay ở đây, nhưng không cần thiết). Đối với mỗi bảng tính toán tất cả các từ có thể được tạo ra và ghi bàn dựa trên số lượng từ được tìm thấy hoặc số đếm theo độ dài từ (nghĩa là tổng số độ dài của tất cả các từ được tìm thấy). Sau đó, chỉ cần chọn bảng điểm tốt nhất từ ​​100 khả năng và đưa nó cho người chơi.

Cũng thay vì luôn chọn bảng điểm cao nhất (tức là bảng dễ nhất), bạn có thể có các ngưỡng điểm khác nhau để làm cho trò chơi trở nên khó khăn hơn cho các chuyên gia.

Answer 4

Một biến thể nhỏ trên phương pháp tiếp cận cặp chữ cái: sử dụng tần suất của các cặp thư trong các từ dài - nói 6 chữ cái hoặc lâu hơn - vì đó là mục tiêu của bạn. Bạn cũng có thể phát triển một trọng số bao gồm tất cả các chữ cái liền kề, không chỉ là một chữ cái ngẫu nhiên.

Answer 5

This wordgame Tôi đã sử dụng bảng tần số tiếng Anh để chọn các chữ cái, nhưng quyết định đầu tiên có tạo nguyên âm hay phụ âm hay không, cho phép tôi đảm bảo tỷ lệ nguyên âm nhất định hội đồng quản trị. Điều này có vẻ hoạt động khá tốt.

Answer 6

Bạn nên tìm kiếm các mô hình ngữ pháp và Markovian.

Ý tưởng đầu tiên của bạn rất có liên quan đến thuật toán Markovian. Về cơ bản, nếu bạn có một văn bản lớn, nói 1000 từ. Những gì bạn có thể làm là phân tích từng chữ cái và tạo một bảng để biết xác suất của một chữ cái nào đó sau chữ cái hiện tại.

Ví dụ: tôi biết rằng chữ Q từ 1000 từ của tôi (tổng cộng 4000 chữ cái) chỉ được sử dụng 40 lần. Sau đó, tôi tính toán những chữ cái có thể xảy ra theo cách sử dụng bảng băm markov của tôi.

Ví dụ: QU xảy ra 100% thời gian nên tôi biết rằng Q nên được ứng dụng của bạn chọn ngẫu nhiên mà tôi cần đảm bảo rằng chữ U cũng được bao gồm. Sau đó, chữ "I" được sử dụng 50% thời gian và "A" 25% số lần và "O" 25% thời gian.

Nó thực sự thực sự phức tạp để giải thích và tôi đặt cược có những giải thích khác ra khỏi đó tốt hơn nhiều sau đó này. Tuy nhiên, ý tưởng là đưa ra một văn bản lớn hợp pháp, bạn có thể tạo một chuỗi các chữ cái X có thể phù hợp với ngôn ngữ tiếng Anh và do đó sẽ dễ dàng cho người dùng để làm cho lời nói ra khỏi. Bạn có thể chọn để mong đợi một giá trị của n-gram, số cao nhất mà bạn có thể tạo ra trò chơi của mình càng dễ dàng. Ví dụ, một n-gam của hai có lẽ sẽ làm cho nó rất khó để tạo ra từ trên 6, nhưng một n-gram của 4 sẽ rất dễ dàng.

Wikipedia giải thích nó thực sự tồi tệ, vì vậy tôi sẽ không theo dõi điều đó.

Hãy nhìn vào máy phát điện Markov này:

http://www.haykranen.nl/projects/markov/demo/

Answer 7

Bạn có thể nhìn vào Java implementation này của Jumble algorithm để tìm bộ chữ cái hoán vị để nhiều từ điển:

 
$ java -jar dist/jumble.jar | sort -nr | head 
11 Orang Ronga angor argon goran grano groan nagor orang organ rogan 
10 Elaps Lepas Pales lapse salep saple sepal slape spale speal 
9 ester estre reest reset steer stere stree terse tsere 
9 caret carte cater crate creat creta react recta trace 
9 Easter Eastre asteer easter reseat saeter seater staree teaser 
9 Canari Carian Crania acinar arnica canari carina crania narica 
8 leapt palet patel pelta petal plate pleat tepal 
8 laster lastre rastle relast resalt salter slater stelar 
8 Trias arist astir sitar stair stria tarsi tisar 
8 Trema armet mater metra ramet tamer terma trame 
...