Apa arti sebuah game sudah terpecahkan
Sebuah game terpecahkan ketika hasil yang diperoleh dari posisi awal diketahui kalau kedua pemain bermain sempurna. Ada tiga tingkat yang lazim. Pada solusi «ultra lemah», hanya diketahui siapa yang menang atau seri, tanpa mengetahui strateginya. Pada yang «lemah», diketahui juga sebuah strategi yang menjamin hasil itu sejak awal. Pada yang «kuat», diketahui hasil terbaik dari posisi mana pun yang mungkin.
Untuk Connect Four pada papan klasik 7 kolom kali 6 baris, hasilnya jelas: dengan permainan sempurna, pemain yang mulai duluan menang. Itu tidak berarti ia selalu menang dalam praktik, karena untuk itu ia harus menemukan langkah yang tepat di setiap giliran, dan permainan antarmanusia penuh kesalahan.
Siapa yang memecahkannya dan kapan
Ceritanya punya dua tokoh yang sampai pada kesimpulan yang sama secara independen pada Oktober 1988. Yang pertama adalah James Dow Allen, yang mengumumkan solusinya pada 1 Oktober 1988 lewat pesan ke grup diskusi rec.games.programmer. Lima belas hari kemudian, pada 16 Oktober, peneliti Belanda Victor Allis mempresentasikan solusinya sendiri, yang dijelaskan dalam karyanya «A Knowledge-based Approach of Connect-Four», dari Vrije Universiteit.
Metode Allis «berbasis pengetahuan»: alih-alih memeriksa semua posisi, ia merumuskan aturan strategis, seperti kotak mana yang sebaiknya dikuasai dan ancaman mana yang penting, lalu menggabungkannya dengan pencarian untuk membuktikan bahwa pemain pertama bisa memaksakan kemenangan. Belakangan hasil yang sama dicapai dengan cara brute force, memakai basis data posisi dan komputer yang kuat; programmer John Tromp, misalnya, menyusun basis data semua posisi 8 keping yang menjadi titik awal. Kedua jalur itu sepakat.
Kunci pembukaan: kolom tengah
Tidak semua langkah pertama cukup. Hasilnya bergantung pada kolom tempat pemain pertama memulai:
| Langkah pertama | Hasil dengan permainan sempurna |
|---|---|
| Kolom tengah (kolom 4) | Pemain pertama menang |
| Kolom di sebelah tengah (kolom 3 dan 5) | Seri |
| Kolom luar (1, 2, 6, dan 7) | Pemain kedua menang |
Apa arti «pemain pertama menang» dalam praktik
Bahwa teori mengatakan pemain pertama menang tidak menjamin apa pun kalau lawan bermain baik: keunggulannya nyata, tetapi menuntut ketepatan. Meski begitu, mulai duluan memberimu dua hal konkret. Yang pertama adalah inisiatif: kamu jalan lebih dulu dan lawan biasanya harus menanggapi ancamanmu. Yang kedua adalah paritas, aturan praktis yang luas dikenal di kalangan pemain: karena papan punya 6 baris, jumlah genap, dan permainan berjalan bergiliran, kotak di baris ganjil (baris 1, 3, dan 5, dihitung dari bawah) cenderung jatuh ke pemain yang mulai duluan, dan kotak di baris genap ke pemain kedua. Karena itu ancaman di baris ganjil biasanya lebih berharga bagi pemain pertama.
Kenapa tengah begitu berharga
Keping di kolom tengah ikut dalam lebih banyak garis yang mungkin daripada keping di kolom lain mana pun. Dari tengah, empat sejajar bisa dibentuk secara mendatar, tegak, dan pada kedua diagonal dengan banyak kombinasi berbeda; keping di tepi hampir hanya berguna untuk satu atau dua arah. Karena itu program yang kuat mengurutkan langkahnya dari tengah ke luar, dan karena itu buku pembukaan dimulai dari kolom 4.
Bagimu, aturan praktisnya sederhana: kalau tidak ada langkah yang jelas lebih baik, pilih kolom yang dekat dengan tengah. Dan kalau lawan menempati tengah lebih dulu, jangan putus asa: kolom di sebelahnya tetap sangat bagus.
Tips untuk lebih sering menang melawan manusia
- Kalau kamu mulai duluan, buka di kolom tengah. Itu satu-satunya pembukaan yang, dengan permainan sempurna, menang.
- Cari ancaman ganda: dua garis berisi tiga dengan kotak penutup yang sama-sama tersedia. Lawan hanya bisa memblokir satu. Itu cara paling umum untuk menang melawan manusia.
- Pikirkan ancaman «di udara»: garis berisi tiga yang kotak terakhirnya belum bisa dijangkau karena masih kurang satu keping di bawahnya. Kalau kotak itu ada di baris yang menguntungkanmu karena paritas, cepat atau lambat lawan harus bermain di bawahnya dan memberikannya padamu.
- Sebelum menjatuhkan keping, lihat kotak mana yang terbuka tepat di atasnya. Kalau kamu memberi lawan kotak yang menutup sebuah garis, kamu kalah.
- Blokir garis berisi tiga yang terbuka di kedua sisi sebelum terbentuk: itu kekalahan pasti. Antisipasi satu giliran lebih awal.
- Di tahap akhir, yang penting adalah siapa yang kehabisan langkah aman: jaga kolom yang masih bisa kamu mainkan tanpa bahaya.
- Kalau kamu pemain kedua, incar kotak di baris genap dan blokir tanpa tergesa setiap ancaman di baris ganjil: itu jalan terbaikmu menuju seri atau agar lawan melakukan kesalahan.
Jadi komputer tidak bisa kalah?
Program yang bermain sempurna sejak awal dan mulai duluan tidak akan pernah kalah, tetapi itu pernyataan tentang solusi teoretis game ini, bukan tentang program mana pun. Memecahkan seluruh permainan dari posisi awal membutuhkan perhitungan yang sangat banyak, dan di browser, dengan hanya satu setengah detik per langkah, itu tidak tercapai.
Karena itu tingkat «Tak terkalahkan» di Connect Four kami ditampilkan apa adanya: tingkat terkuat. Ia memakai pencarian alfa-beta dengan pendalaman iteratif, tabel yang mengingat posisi yang sudah pernah dilihat, urutan kolom yang dimulai dari tengah, dan buku pembukaan yang sangat pendek. Ia menganalisis banyak langkah ke depan dan hampir tidak melewatkan kesalahan, tetapi kami tidak menjanjikan bahwa ia mustahil dikalahkan. Kalau kamu berhasil menaklukkannya, kamu menang dengan sungguh-sungguh.
Cara berlatih
Cara bagus untuk meningkat adalah bermain melawan komputer di tingkat Sulit lalu melawan Tak terkalahkan, bergantian siapa yang mulai. Saat kalah, tinjau kembali permainannya dan temukan di giliran mana ancaman ganda muncul: hampir selalu bisa ditelusuri ke sebuah langkah tenang sebelumnya. Sebaiknya coba juga varian, seperti papan yang lebih besar atau mode PopOut, yang memaksa berpikir dengan cara berbeda dan melatih penglihatan terhadap papan.
Pertanyaan umum
Siapa yang membuktikan Connect Four sudah terpecahkan?
James Dow Allen mengumumkannya pada 1 Oktober 1988 dan, secara independen, Victor Allis mempresentasikan solusinya pada 16 Oktober 1988. Setelah itu ada konfirmasi dengan cara brute force.
Siapa yang menang di Connect Four dengan permainan sempurna?
Pemain yang mulai duluan, asalkan keping pertamanya masuk ke kolom tengah papan klasik 7×6. Kalau ia mulai di kolom di sebelah tengah, permainan seri secara teoretis, dan kalau ia mulai di salah satu dari empat kolom tepi, pemain kedua menang.
Apakah itu berarti yang mulai duluan selalu menang?
Tidak. Itu hasilnya kalau tidak ada yang membuat kesalahan. Dalam praktik kamu harus terus tepat di setiap giliran, dan manusia bisa salah. Mulai duluan adalah keunggulan, bukan jaminan.
Apakah ukuran papan lain juga sudah terpecahkan?
Banyak yang sudah, tetapi hasilnya berubah menurut ukuran. Misalnya, John Tromp melaporkan bahwa papan 8×8 dimenangkan pemain kedua. Panduan ini hanya membahas papan klasik 7 kolom kali 6 baris.
Apakah tingkat Tak terkalahkan tidak pernah kalah?
Tidak kami janjikan. Itu tingkat terkuat yang kami tawarkan, dengan pencarian dalam dan banyak perhitungan per langkah, tetapi tidak memecahkan seluruh permainan dalam waktu yang tersedia. Hanya tersedia di papan klasik 7×6.
Berapa banyak posisi di Connect Four?
Telah dihitung 4.531.985.219.092 posisi sah pada papan 7×6, angka yang dikonfirmasi secara independen pada 2008 oleh Stefan Edelkamp dan Peter Kissmann.