Finate State Machine & Finate State Automata

A.FSM (Finite State Machine)

Mesin finite-state adalah model yang digunakan untuk merepresentasikan dan mengendalikan aliran eksekusi. Ini sangat cocok untuk menerapkan AI (kecerdasan buatan) dalam game, menghasilkan hasil yang bagus tanpa kode yang rumit. Tutorial ini menjelaskan teori, implementasi dan penggunaan mesin finite-state secara sederhana dan berbasis stack.

Mesin finite-state, atau disingkat FSM, adalah model perhitungan berdasarkan mesin hipotetis yang dibuat dari satu atau lebih kedudukan. Hanya satu kedudukan yang bisa aktif pada saat bersamaan, sehingga mesin harus berpindah dari kedudukan ke kedudukan lain agar bisa melakukan tindakan yang berbeda.

FSM biasanya digunakan untuk mengatur dan merepresentasikan aliran eksekusi, yang berguna untuk menerapkan AI dalam permainan. "Otak" musuh, misalnya, dapat diimplementasikan dengan menggunakan FSM: setiap kedudukan mewakili sebuah tindakan, seperti serangan dan menghindar .

              FSM dapat diwakili oleh grafik, di mana simpulnya adalah suatu kedudukan dan ujungnya adalah transisi. Setiap tepi memiliki label yang menginformasikan kapan transisi harus terjadi, seperti ketika pemain berada di dekat (player is near  ) label pada gambar di atas, yang mengindikasikan bahwa mesin akan beralih dari pengembaraan (wander) menjadi menyerang (attack) jika pemainnya berada di dekatnya.

Finite State Machine di dunia AI Game Programming, merupakan salah satu teknik yang paling sering digunakan. Alasannya yaitu:

´  1. Implementasinya mudah dan cepat

´  2. Memudahkan proses debugging. Karena telah dipecah menjadi kepingan yang lebih kecil, proses debugging kalau terjadi behavoiur yang tidak semestinya, menjadi lebih mudah

´  3. Proses komputasi yg minimal, karena sejatinya FSM hanyalah conditional statement yang dikemas dalam bentuk yang lebih elegan.

´  4. Fleksibel, dapat dikombinasikan dengan teknik AI lain misalnya fuzzy logic dan neural network

     Kekurangannya:

´  1. Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut

´  2. Karena mudah diimplementasi, kadang programmer langsung tembak di eksekusi tanpa melakukan desain FSM terlebih dahulu. Biasanya akan terjadi FSM yang terfragmentasi

´  3. Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis

FSA (Finite state automata )

´  Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

´  Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

´  Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Karakteristik Finite Automata

1.Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
2.Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
3.Setiap Finite Automata selalu memiliki keadaan awal.
4.Finite Automata dapat memiliki lebih dari satu keadaan akhir.
jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.

Setiap FSA memiliki:
1.Himpunan berhingga (finite) status (state)
•Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.
•Beberapa buah status sebagai status akhir (final state).
2.Himpunan berhingga simbol masukan
3.Fungsi transisi
Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.

cara Kerja Finite State Automata

´  Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.

´  Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).