Teori permainan kombinatorial

Teori permainan kombinatorial, juga dikenal sebagai CGT adalah cabang matematika terapan dan ilmu komputer teoretis yang mempelajari permainan kombinatorial, dan berbeda dari teori permainan "tradisional" atau "ekonomi". CGT muncul dalam kaitannya dengan teori permainan yang tidak memihak, khususnya permainan dua pemain Nim, dengan penekanan pada "pemecahan" jenis permainan kombinatorial tertentu.

Sebuah permainan harus memenuhi beberapa kondisi untuk menjadi permainan kombinatorial. Ini adalah:

Permainan harus memiliki setidaknya dua pemain.
Permainan harus berurutan (yaitu, pemain bergiliran secara bergantian.)
Permainan harus memiliki informasi yang sempurna (yaitu tidak ada informasi yang disembunyikan, seperti dalam Poker.)
Permainan harus deterministik (yaitu tanpa peluang). Keberuntungan bukanlah bagian dari permainan.
Permainan harus memiliki jumlah kemungkinan gerakan yang ditentukan.
Permainan pada akhirnya harus berakhir.
Permainan harus diakhiri ketika salah satu pemain tidak bisa lagi bergerak.

Teori Permainan Kombinatorial sebagian besar terbatas pada studi tentang subset permainan kombinatorial yang terdiri dari dua pemain, terbatas, dan memiliki pemenang dan pecundang (yaitu, tidak berakhir seri.).

Permainan-permainan kombinatorial ini dapat direpresentasikan oleh pohon, yang setiap simpulnya adalah permainan yang dihasilkan dari pergerakan tertentu dari permainan yang berada tepat di bawahnya pada pohon. Permainan-permainan ini dapat diberi nilai permainan. Menemukan nilai-nilai permainan ini sangat menarik bagi para ahli teori CG, seperti halnya konsep teoritis dari penjumlahan permainan. Penjumlahan dua permainan adalah permainan di mana setiap pemain pada gilirannya harus bergerak hanya pada salah satu dari dua permainan, dan membiarkan permainan lainnya tetap seperti semula.

Elwyn Berlekamp, John Conway dan Richard Guy adalah pendiri teori ini. Mereka bekerja sama pada tahun 1960-an. Karya mereka yang diterbitkan berjudul Winning Ways for Your Mathematical Plays.

Definisi

Dalam teori tersebut, ada dua pemain yang disebut kiri dan kanan. Permainan adalah sesuatu yang memungkinkan kiri dan kanan untuk melakukan gerakan ke permainan lain. Misalnya, dalam permainan catur, ada pengaturan awal yang biasa. Namun, seseorang juga bisa menganggap permainan catur setelah langkah pertama sebagai permainan yang berbeda, dengan pengaturan yang berbeda. Jadi, setiap posisi juga disebut permainan.

Permainan-permainan memiliki notasi {L|R}. L {\displaystyle L} $L$ adalah permainan-permainan yang dapat dipindahkan oleh pemain kiri. R {\displaystyle R} $R$ adalah permainan-permainan yang dapat dipindahkan oleh pemain kanan. Jika Anda tahu notasi catur, maka setup catur yang biasa adalah permainan

{a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Titik-titik "...." berarti ada banyak gerakan, jadi tidak semua ditampilkan.

Catur sangat kompleks. Lebih baik memikirkan permainan yang lebih mudah. Nim, misalnya, jauh lebih sederhana untuk dipikirkan. Nim dimainkan seperti ini:

Terdapat nol atau lebih tumpukan counter.
Pada gilirannya, seorang pemain dapat mengambil sebanyak mungkin counter dari satu tumpukan yang diinginkan pemain tersebut.
Pemain yang tidak bisa bergerak akan kalah.

Permainan Nim yang paling mudah dimulai tanpa penghitung sama sekali! Dalam kasus seperti itu, tidak ada pemain yang bisa bergerak. Itu ditunjukkan sebagai {|}. Kedua sisi kosong, karena tidak ada pemain yang bisa bergerak. Pemain pertama yang maju tidak bisa bergerak, dan karenanya akan kalah. Dalam CGT, orang sering menulis {|} sebagai simbol 0 (nol).

Permainan termudah berikutnya hanya memiliki satu tumpukan, dengan hanya satu penghitung. Jika pemain kiri bergerak lebih dulu, pemain itu harus mengambil penghitung, meninggalkan kanan tanpa gerakan ({|}, atau 0). Jika sebaliknya, pemain kanan yang bergerak lebih dulu, tidak akan ada lagi gerakan untuk pemain kiri. Jadi, baik kiri maupun kanan dapat membuat langkah ke 0. Itu ditunjukkan sebagai {{|}|{|}}, atau {0|0}. Pemain pertama yang bergerak akan menang. Permainan yang sama dengan {0|0} sangat penting. Mereka ditulis dengan simbol, * (bintang).

Pertanyaan dan Jawaban

T: Apa itu Teori Permainan Kombinatorial?

J: Teori Permainan Kombinatorial (CGT) adalah cabang matematika terapan dan ilmu komputer teoretis yang mempelajari permainan kombinatorial, dan berbeda dari teori permainan "tradisional" atau "ekonomi".

T: Kondisi apa yang harus dipenuhi oleh sebuah permainan untuk dianggap sebagai permainan kombinatorial?

J: Agar sebuah permainan dapat dianggap sebagai permainan kombinatorial, permainan tersebut harus memiliki setidaknya dua pemain, permainan tersebut harus berurutan (yaitu Pemain bergantian giliran), permainan tersebut harus memiliki informasi yang sempurna (yaitu tidak ada informasi yang disembunyikan), permainan tersebut harus deterministik (yaitu tidak ada peluang), keberuntungan tidak dapat menjadi bagian dari permainan, harus ada jumlah kemungkinan gerakan yang ditentukan, permainan pada akhirnya harus berakhir, dan permainan harus berakhir ketika salah satu pemain tidak bisa lagi bergerak.

T: Jenis permainan apa yang menjadi fokus Teori Permainan Kombinatorial?

J: Teori Permainan Kombinatorial sebagian besar berfokus pada permainan terbatas dua pemain yang memiliki pemenang dan pecundang (yaitu, tidak berakhir seri).

T: Bagaimana jenis-jenis permainan ini direpresentasikan?

J: Jenis-jenis permainan ini dapat direpresentasikan oleh pohon dengan setiap simpul mewakili permainan yang dihasilkan dari gerakan tertentu dari bawahnya pada pohon.

T: Apa saja tujuan dari para ahli teori CG?

J: Beberapa tujuan bagi para ahli teori CG termasuk menemukan nilai untuk jenis permainan ini serta memahami konsep "penambahan permainan" yang melibatkan setiap pemain yang hanya membuat satu gerakan dalam dua permainan yang berbeda sehingga yang lain tidak berubah selama giliran mereka.

T: Siapa yang mendirikan CGT?

J: Elwyn Berlekamp, John Conway, dan Richard Guy dikreditkan sebagai pendiri CGT dalam karya mereka yang diterbitkan berjudul Winning Ways for Your Mathematical Plays pada tahun 1960-an.