Manusia
Berpikir dengan Intuisi dan Perhitungan
Ketika bermain othello, demikian juga
permainan-permainan lain seperti catur, shogi, igo dll., kita manusia berpikir
dengan menggabungkan intuisi yang menggunakan perasaan dan perhitungan yang menggunakan
otak.
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
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 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 =
16
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.
0 komentar:
Posting Komentar