Pada sebuah posisi papan othello tertentu, mula-mula intuisi kita akan segera mengenali pola susunan keping di saat itu, ini adalah kemampuan pattern recognition yang inheren dimiliki oleh setiap manusia. Beberapa langkah yang jelas-jelas buruk atau 'dianggap' buruk segera dapat dikenali dan dihilangkan dari daftar langkah yang mungkin dilakukan (disebut possible moves, legal moves atau valid moves). Setelah itu barulah kita menghitung langkah-langkah sisanya yang 'terlihat' baik, dengan melakukan simulasi permainan di dalam kepala kita untuk setiap langkah, kemudian membandingkan untung-ruginya untuk menentukan langkah terbaik.
Misalnya di dalam sebuah posisi papan, ada 10 valid moves. Mula-mula intuisi kita akan menghapus 3 langkah yang jelas-jelas buruk, lalu 2 langkah lagi yang 'kelihatannya' buruk, dari daftar valid moves. Dengan demikian, hanya tinggal tersisa 5 langkah yang perlu diperhitungkan. Di sini, barulah kita melakukan simulasi permainan, ketika langkah 1 dilakukan maka lawan akan menjawab dengan langkah 1-1, 1-2, 1-3, ... Kalau kita melangkah dengan langkah 2 maka lawan akan menjawab dengan langkah 2-1, 2-2, 2-3, ... dst, sampai beberapa langkah ke depan (kedalaman tertentu) tergantung daya ingat kita.
Di sinipun intuisi manusia selalu berperan besar dalam mengenali pola-pola yang muncul di setiap kedalaman simulasi permainan untuk menghilangkan langkah-langkah yang 'dianggap' buruk dari perhitungan. Sehingga kita manusia dapat memilih hanya satu atau dua langkah tertentu saja yang 'dianggap' baik untuk ditelusuri sampai kedalaman cukup jauh, sementara langkah-langkah lain yang 'dianggap' tidak menjanjikan hanya diperhitungkan seperlunya saja. Dari hasil simulasi ini, kita membandingkan untung-rugi setiap langkah yang disimulasikan, dan menentukan langkah mana yang terbaik.
Komputer berpikir hanya dengan perhitungan
Nah.. di sisi lain, berbeda dengan manusia, komputer tidak mempunyai intuisi yang menggunakan perasaan. Sebagai gantinya, komputer mempunyai daya perhitungan yang jauh lebih besar daripada manusia. Ketika diberikan sebuah posisi papan othello tertentu, sama seperti manusia komputer juga melakukan perhitungan simulasi permainan untuk valid moves yang tersedia. Tetapi berbeda dengan manusia, dia tidak mempunyai intuisi untuk mengenali langkah-langkah yang jelas-jelas buruk lalu menghilangkannya dari daftar perhitungan. Sehingga komputer harus memperhitungkan semua valid moves, di sinilah daya perhitungan yang besar sangat diperlukan.
Pada dasarnya ketika diberikan sebuah susunan posisi papan tertentu, komputer menghitung nilai posisi tersebut menggunakan fitur-fitur yang dijelaskan pada artikel Strategi bermain othello, seperti jumlah keping, penguasaan sudut/x-quare/c-square, jumlah keping stabil, mobility, jumlah keping tepi, parity, dan pola sisi/sudut. Di setiap posisi papan yang sedang dipertimbangkan, mula-mula komputer menghitung nilai dari setiap fitur. Misalnya ketika dilakukan simulasi langkah 1, maka jumlah keping (discs) ada 30, sudut yang dikuasai (corners) ada 2, jumlah keping stabil (stables) ada 5, mobility ada 15, jumlah keping tepi (frontiers) ada 10, parity yang dimenangkan ada 3, dan nilai pola sisi/sudut (pattern) adalah 20.
Selanjutnya nilai dari masing-masing fitur ini digabungkan secara linier dengan bobot-bobot tertentu yang dianggap tepat. Misalnya nilai total dari posisi papan ini adalah:
score = w_d * discs + w_c * corners + w_s * stables + w_m * mobility + w_f * frontiers + w_p * parity + w_t * pattern
= -3 * 30 + 5 * 2 + 9 * 5 + 7 * 15 - 5 * 10 + 8 * 3 + 6 * 20
= 164
Dengan asumsi bahwa bobot-bobot untuk setiap fitur yang dianggap tepat adalah:
w_d = -3 (bobot untuk discs)
w_c = 5 (bobot untuk corners)
w_s = 9 (bobot untuk stables)
w_m = 7 (bobot untuk mobility)
w_f = -5 (bobot untuk frontiers)
w_p = 8 (bobot untuk parity)
w_t = 6 (bobot untuk pattern)
Ini adalah nilai papan untuk simulasi langkah 1. Berikutnya dilakukan simulasi untuk langkah 2, dihitung lagi berapa nilainya, langkah 3 berapa nilainya.. dst. Dan ini baru berpikir sampai kedalaman satu, disebut juga 1-ply dalam istilah kecerdasan buatan untuk permainan komputer. Untuk berpikir sampai kedalaman 2, maka di setiap posisi papan (hasil simulasi kedalaman 1) belum dihitung dulu nilainya, tetapi harus dilakukan lagi simulasi kedalaman 2 untuk setiap langkah di posisi tersebut, baru kemudian dilakukan perhitungan di atas.
Jadi kalau di kedalaman 1 ada 3 valid moves, yang membawa ke 3 posisi papan berbeda, dan di setiap posisi papan rata-rata ada 3 valid moves yang dimiliki lawan kita, maka untuk berpikir sampai kedalaman 2 kita perlu memperhitungkan sebanyak 3 x 3 = 9 posisi papan. Tetapi rata-rata jumlah valid moves pada othello diperkirakan sekitar 8, sehingga 'berpikir' sampai kedalaman 2 perlu menghitung 8^2 = 64 posisi, kedalaman 3 perlu 8^3 = 512 posisi.. dan kedalaman 10 perlu menghitung lebih dari 1 milyar posisi!
Algoritma Minimax
Untuk melakukan perhitungan simulasi permainan inilah, digunakan algoritma standar di dalam bidang kecerdasan buatan (artificial intelligence, AI) yang sudah dikembangkan sejak lama, yaitu Game Theory, terutama algoritma yang disebut Minimax. Sesuai namanya, algoritma minimax adalah aturan untuk permainan zero-sum 2 pemain, yang berusaha meminimalkan kemungkinan kalah sambil memaksimalkan kemungkinan menang untuk pemain yang akan melangkah.Di kedalaman 1 (dan kedalaman ganjil lainya), posisi papan akan menentukan nilai untuk pemain yang akan melangkah saat ini (current player), sehingga di kedalaman ganjil ini algoritma minimax memilih langkah bernilai maksimal sebagai langkah terbaik. Sebaliknya di kedalaman 2 (dan kedalaman genap lainnya), posisi papan akan menentukan nilai untuk pemain lawan yang akan melangkah berikutnya (opponent player), sehingga di kedalaman genap ini algoritma minimax memilih langkah bernilai minimal sebagai langkah terbaik.
Sebagai ilustrasi sampai kedalaman dua bisa digambarkan dengan tabel berikut:
|
B memilih
B1
|
B memilih
B2
|
B memilih
B3
|
|
|
A memilih
A1
|
+3
|
−2
|
+2
|
|
A memilih
A2
|
−1
|
0
|
+4
|
|
A memilih
A3
|
−4
|
−3
|
+1
|
Ketika A memilih langkah A1 dilanjutkan dengan B memilih langkah B1, posisi papan yang terbentuk bernilai +3. Demikian pula untuk A1 → B2 nilainya -2, A1 → B3 nilainya +2 dst. Sekarang mari kita coba aplikasikan algoritma minimax untuk menghitung langkah terbaik bagi pemain A.
Terhadap langkah A1 (kedalaman 1) misalnya valid moves pemain B adalah B1, B2 dan B3 (kedalaman 2), dan langkah terbaik menurut algoritma minimax didapat dengan mencari langkah bernilai minimal (karena di kedalaman 2), yaitu B2 (bernilai -2). Demikian pula terhadap langkah A2 yang terbaik bagi B adalah B1 (bernilai -1), dan terhadap A3 adalah B1 juga (bernilai -4). Selanjutnya, nilai untuk langkah pemain A (kedalaman 1) adalah nilai yang 'dikembalikan' dari pemain B di kedalaman 2, yaitu A1 adalah -2, A2 adalah -1, dan A3 adalah -4. Kemudian untuk kedalaman 1 ini algoritma minimax mencari nilai maksimal sebagai langkah terbaik, yaitu A2 (bernilai -1).
Untuk kedalaman lebih dari dua, cara 'berpikir' algoritma minimax dapat digambarkan sebagai pohon permainan (game tree) seperti pada gambar di atas. Di lokasi paling dalam (disebut lokasi node daun atau leaf node), dalam hal ini kedalaman 4, dilakukanlah perhitungan nilai posisi papan yang selanjutnya 'dikembalikan' ke node pada kedalaman di atasnya terus hingga sampai lokasi paling atas (di sebut akar atau root). Panah merah menunjukkan nilai yang dikembalikan dari langkah terbaik pilihan algoritma minimax ke kedalaman di atasnya. Demikianlah, kita dapat melihat algoritma minimax bergantian memilih langkah dengan nilai minimal dan maksimal sebagai langkah terbaik sesuai dengan kedalamannya. Dengan algoritma ini komputer dapat 'berpikir' sampai kedalaman tertentu untuk menentukan langkah terbaik untuk memenangkan permainan.
Tetapi pada prakteknya, algoritma minimax kini tidak pernah digunakan lagi, karena algoritma ini harus memperhitungkan semua valid moves, sehingga memerlukan waktu yang sangat lama. Sebagai gantinya telah dikembangkan beberapa improvisasi dari minimax seperti algoritma AlphaBeta, NegaScout dll. yang dapat melakukan pemangkasan game tree supaya tidak perlu memperhitungkan semua valid moves, sehingga dapat 'berpikir' dalam waktu jauh lebih cepat.
No comments:
Post a Comment