Games worth discovering

Banner of Thử thách tự động hóa trạng thái hữu hạn

Screenshot 1 of Thử thách tự động hóa trạng thái hữu hạn

Screenshot 2 of Thử thách tự động hóa trạng thái hữu hạn

Screenshot 3 of Thử thách tự động hóa trạng thái hữu hạn

Screenshot 4 of Thử thách tự động hóa trạng thái hữu hạn

Thử thách tự động hóa trạng thái hữu hạn

Want

Automaton là một cỗ máy trả lời một câu hỏi cụ thể mà không cần sự can thiệp của con người sau khi nó được bật, chẳng hạn như: 1. Liệu a + b = c? 2. Chuỗi ký tự có chứa “a” không? 3. Câu "Có lẽ chúng ta có thể đi uống cà phê" có nghĩa là "Tôi phải lòng bạn" không? (Tôi không nghĩ máy tự động cho câu hỏi này đã được thiết kế.) Trong trò chơi này, chúng ta sẽ chơi với mô hình máy tự động đơn giản nhất, Máy tự động trạng thái hữu hạn và sử dụng nó để đối phó với 40 thử thách. Chúng đến từ thao tác chuỗi ký tự, số nhị phân và cuộc sống hàng ngày. Đừng lo lắng nếu bạn chưa quen với Finite State Automaton vì trò chơi này có hướng dẫn để bắt đầu nhanh chóng. Ngoài ra, bạn có thể đọc phần giới thiệu sau đây và tìm kiếm trực tuyến Finite State Automaton để làm quen với nó. Automaton trạng thái hữu hạn Finite State Automaton (FSA) là loại automaton đơn giản nhất. Một máy tự động trạng thái hữu hạn bao gồm một số trạng thái và quy tắc chuyển tiếp. Quy tắc chuyển tiếp mô tả khi một trạng thái chuyển sang trạng thái khác. Vì vậy, nó trông giống như một bản đồ tàu điện ngầm. Các máy khách của máy tự động trạng thái hữu hạn là các chuỗi ký tự. Nó quyết định chuỗi nào được chấp nhận và chuỗi nào bị từ chối. Ví dụ: FSA có thể chấp nhận email, số điện thoại hợp lệ, v.v. Bây giờ, hãy đi sâu vào ví dụ đầu tiên: Nó có hai trạng thái: trạng thái bên trái là "1" và trạng thái bên phải là "2". "1" được đánh dấu bằng màu xanh lục có nghĩa là máy tự động bắt đầu ở đây. "2" được đánh dấu bằng màu xanh lam có nghĩa là máy tự động chỉ chấp nhận chuỗi đầu vào nếu nó dừng ở đây và đọc tất cả các ký tự theo thứ tự của chuỗi. Do đó, máy tự động này phải chấp nhận "a" và từ chối bất kỳ chuỗi nào khác. Câu hỏi: cố gắng tự mình thiết kế một FSA chấp nhận "ab" và một FSA chấp nhận "a" hoặc "b" (abbr., "a|b") (Đây là hai thử thách trong trò chơi). Không xác định Khái niệm cơ bản nhất của FSA (và các loại máy tự động khác) được gọi là Không xác định. Để giới thiệu khái niệm này, đây là ví dụ thứ hai về máy tự động. Nó chấp nhận tất cả các chuỗi (chỉ bao gồm 'a' và 'b') kết thúc bằng 'b': Chạy máy tự động này qua "b" trong đầu bạn: (1) Nó bắt đầu ở "1", chạy vòng lặp tự động của " 1", sau đó đọc tất cả "b" và dừng ở "1", vì vậy hãy từ chối "b"; (2) Nó bắt đầu từ "1" và chuyển sang "2", sau đó đọc tất cả "b" và dừng ở "2", vì vậy hãy chấp nhận "b". Máy tự động trạng thái hữu hạn không xác định (NFA) chấp nhận một chuỗi nếu ít nhất một dấu vết kết thúc ở trạng thái được đánh dấu bằng màu xanh lam. Chạy máy tự động này qua "ab" trong đầu bạn: (1) Nó bắt đầu ở "1", chạy vòng lặp tự động của "1" hai lần, sau đó đọc tất cả "ab" cũng như dừng ở "1", vì vậy hãy từ chối "ab"; (2) Nó bắt đầu ở "1", chạy tự vòng lặp của "1" một lần và chuyển sang "2", sau đó đọc tất cả "b" cũng như dừng ở "2", vì vậy hãy chấp nhận "ab." Tính không xác định là cần thiết vì nó cho phép FSA đoán, điều này cho phép chúng ta thiết kế một máy tự động một cách tự nhiên (vì chúng ta, con người, thích đoán) và nhanh chóng. Một số ứng dụng của Automaton trạng thái hữu hạn Học Automate trạng thái hữu hạn có thể giúp bạn bước vào thế giới khoa học máy tính. Ngoài ra, nó có thể cho phép bạn xây dựng nhiều ứng dụng, chẳng hạn như: Triển khai NPC (nhân vật không phải người chơi). Để cải thiện trải nghiệm người dùng, nhiều trò chơi có NPC lặp lại logic cố định của chúng. Ví dụ: một nhân viên bán hàng đi từ tây sang đông, rồi từ đông sang tây và yêu cầu một người chơi thực sự mua một số thứ khi họ đến gần. Logic đơn giản đến mức FSA có thể thực hiện được. Lợi ích của việc sử dụng FSA thay vì ngôn ngữ lập trình chung (như C và JAVA) là FSA dễ đọc hơn và tốn ít nhân lực hơn để kiểm tra, sửa đổi và bảo trì.

Additional information

Provider

Tramolly Game

Last Updated on

03/19/2024