Teorya ng larong kombinatoryal

Ang teorya ng larong kombinatoryal ay isang sangay ng matematika at teoretikal na agham pangkompyuter na tipikal na sinisiyasat ang mga larong sekwensiyal na may perpektong impormasyon. Ang pag-aaral ay karaniwang kinukulong sa mga larong dalawang manlalaro na may isang posisyon na ang mga manlalaro ay naghahalinhinan sa pagbabago. Kinabibilangan ng itong mga pagbabago ang mga tiyak na paraan o tira para makagawa ng isang tiyak na panalong kondisyon. Tradisyunal na, ang teorya ng larong kombinatoryal ay hindi nag-aral ng mga laro ng tsansa o na gumagamit ng imperpektong o inkumpletong impormasyon, kundi sa halip, ng mga laro na may perpektong impormasyon kung saan ang kondisyon ng laro at ang pangkat ng magagamit na mga tira ay laging alam sa parehong mga manlalaro. Gayunman, habang umaabante ang mga matematikal na teknik, gayon din lumalawak ang mga uri ng laro na nasusuri, kaya laging bumabago ang mga hangganan ng sangay. Nasa simula ng isang papel, heneral na ipapaliwanag ng mga iskolar kung ano ang ibig sabihin ng isang "laro", at madalas na nagkakaiba ang itong mga katuturan, na espesipiko sa larong sinusuri at hindi kinakatawan ang buong saklaw ng sangay.

Ang kombinatoryal na mga laro ay sumasaklaw ng mga kilalang laro tulad ng ahedres, dama, at Go, na itinuturing na di-tribiyal, at tic-tac-toe, na itinuturing na tribiyal, sa kahulugan ng "madaling malutas". Ang mga ilang larong kombinatoryal ay may isang lugar ng paglalaro na walang hangganan, tulad ng impinitong ahedres. Sa teorya ng larong kombinatoryal, ang mga tira sa itong at ibang mga laro ay kinakatawan bilang isang punong laro.

Ang mga larong kombinatoryal ay sumasaklaw rin ng mga kombinatoryal na palaisipang isang manlalaro tulad ng Sudoku, at mga automata tulad ng Laro ng Buhay ni Conway (ngunit sa pinamahigpit na katuturan, nasasabihan na kailangan ng isang "laro" ay dalawang o mas manlalaro, kaya mga designasyon ng "palaisipan" at "automata").

Sa heneral ang teorya ng laro ay sumasaklaw ng mga laro ng tsansa, mga laro ng imperpektong kaalaman, at mga laro kung saan sabay-sabay na nakagagalaw ang mga manlalaro. Madalas kumakatawan ang mga ganyang laro, at mga pasiyang ginagawa sa kanila, sa mga sitwasyon sa totoong buhay.

Ang teorya ng larong kombinatoryal ay may magkaibang pagdidiin kaysa sa "tradisyunal" o "ekonomikong" teorya ng laro, na noong una nabuo para mag-aral ng mga laro na may simpleng kombinatoryal istruktura, pero na may mga elemento ng tsansa (ngunit ikinokonsidera rin ang mga sekwensiyal na tira, tingnan ang larong malawak na porma, Ingles: extensive-form game). Sa esensya, ang teorya ng larong kombinatoryal ay nag-ambag ng mga bagong paraan para analisahin ang mga punong laro, halimbawa sa pamamagitan ng mga surreal na bilang, isang subklase ng lahat ng mga laro na may dalawang manlalaro at perpektong impormasyon. Nagkaiinteres din ang artipisyal na katalinuhan sa uri ng mga larong inaaral ng teorya ng larong kombinatoryal, lalo na para sa awtomatikong pagpaplano (Automated planning and scheduling). Sa teorya ng larong kombinatoryal may menos pagdidiin sa pagpapabuti ng mga praktikal na algoritmo ng paghahanap (tulad ng heuristikang pagtatabas na alpha-beta na sinasaklaw sa karamihan ng mga aklat-pampaaralan tungkol sa artipisyal na katalinuhan) kundi mas pagdidiin sa mga deskriptibong teoretikal na resulta (tulad ng mga sukat ng kompleksidad ng laro, o mga pruweba, ng eksistensiya ng isang pinakamainam na solusyon, na hindi nila kinakailangang tukuyin ang isang algoritmo, tulad ng argumento ng pagnanakaw ng estratehiya, Strategy-stealing argument).

Ang isang mahalagang nosyon sa teorya ng larong kombinatorya ay nalutas na laro. Halimbawa, ang tic-tac-toe ay itinuturing na isang lutas na laro, dahil napatutunayan na tatabla ang anumang laro kung pinakamainam na naglalaro ang parehong mga manlalaro. Mahirap makuha ang tulad na mga resulta para sa mga laro na may mayayamang kombinatoryal na istruktura. Halimbawa, noong 2007 inihayag na mahinang nalutas ang dama—ang pinakamainam na paglalaro ng parehong mga manlalaro ay nagdulot ng isang tabla—pero ang itong resulta ay pruwebang tinulungan ng isang kompyuter (Computer-assisted proof). Ang ibang mga laro ng tunay na mundo ay napakamasalimuot kaya hindi ngayong inaatim ang buong pagsusuri, ngunit nakagawa ng teorya ang mga ilang tagumpay sa pagsusuri ng mga endgame ng Go. Ang paggamit ng teorya ng larong kombinatoryal para sa isang posisyon ay nagtatangkang alamin ang pinakamainam na sekwensiya ng mga tira para parehong mga manlalaro hanggang sa matapos ang laro, at gayong alamin ang pinakamainam na tira sa anumang posisyon. Sa praktika, hirap-hirap ang itong proseso, maliban kung napakasimple ang laro.

Nakakatulong itangi ang mga kombinatoryal "laro ng matematika" na interesante para sa mga matematiko at siyentipiko, at mga kombinatoryal "totoong mga laro" na interesante para sa heneral na populasyon bilang isang porma ng paglilibang at paligsahan. Gayunman, ang mararaming laro ay sinasaklaw sa parehong mga kategorya. Ang nim, halimbawa, ay isang totoong laro na gumanap ng isang papel sa pundasyon ng teorya ng larong kombinatoryal, at isa sa unang mga larong iniangkop para sa isang kompyuter. Ginagamit pa ang tic-tac-toe para ituro ang mga simulain ng AI ng pagdidisenyo ng laro sa mga mag-aaral ng agham pangkompyuter.

Kasaysayan

Lumitaw ang teorya ng larong kombinatoryal sa kaugnayan sa teorya ng mga imparsiyal na laro, kung saan anumang galaw na nagagamit sa isang manlalaro dapat magamit din sa ibang. Ang isang halimbawa ay nim, na puspusan nasosolusyonan. Ang nim ay imparsiyal na laro para sa dalawang manlalaro, at napapailalim sa kondisyon ng normal na laro, na nangangahulugan na nagpapatalo ang isang manlalaro na hindi puwedeng gumawa ng isang tira. Noong dekada 1930, nagpatunay ang teorema ni Sprague–Grundy na ang lahat ng imparsiyal na laro ay katumbas sa mga tambak sa nim, na kaya ipinakita na posible ang mga pangunahing pag-iisa o pagkakasundo sa mga laro na ikinokonsidera sa isang kombinatoryal na antas, kung saan mahahalaga ang mga detalyadong estratehiya, hindi lang mga gantimpala.

Noong dekada 1960, ipinakilala nina Elwyn Berlekamp, John Horton Conway, at Richard K. Guy ang teorya ng isang partisanong laro, kung saan binibitawan ang hingi na ang isang tira, na nagagamit sa isang manlalaro, ay nagagamit din sa iba. Inilathala ang kanilang mga resulta sa kanilang aklat na Winning Ways for Your Mathematical Plays noong 1982. Gayunman, ang unang obrang inilathala tungkol sa paksa ay On Numbers and Games (Conway, 1976, kilala rin bilang ONAG) na ipinakilala ang konsepto ng mga surreal na bilang at paglalahat sa mga laro. Ang On Numbers and Games ay rin bunga ng kolaborasyon nina Berlekamp, Conway, at Guy.

Ayon sa kombensyon, tipikal na inilalagay ang mga larong kombinatoryal sa isang porma kung saan nananalo ang isang manlalaro kung kailan ang iba ay walang tirang nalalabi. Madali ang palit ng anumang pinitong laro, na may lang dalawang posibleng resulta, sa katumbas kung saan magagamit ang itong kombensyon. Ang isa sa mga pinakamahahalagang konsepto sa teorya ng larong kombinatoryal ay sumang dishuntibo (Ingles: disjunctive sum) ng dalawang laro. Ito ay laro kung saan ang kada manlalaro ay maaaring gumawa ng isang tira sa alinmang laro sa anumang punto sa total na laro (kumbaga, suma) at nananalo ang isang manlalaro kung kailan ang kalaban ay walang galaw sa alinmang laro. Ang ganiyang kombinasyon ng mga laro ay nagdudulot ng isang mayamang at makapangyarihang matematikal na istruktura.

Nagsabi si Conway sa On Numbers and Games na ang inspirasyon para sa teorya ng mga partisanong laro ay batay sa kaniyang obserbasyon ng mga endgame ng Go, na madalas na puwedeng maisip bilang mga suma ng mas simpleng mga endgame na nahihiwalay sa magkaibang mga bahagi ng tabla.

Balangkas

Ang isang laro, sa pinakasimpleng mga termino, ay isang talaan ng mga posibleng "galaw" na magagamit sa dalawang manlalarong tinatawag na kaliwa at kanan. Ang posisyon ng laro na kinahihinathan mula sa anumang galaw, o tira, maaaring ikonsidera bilang ibang laro. Ang itong ideya ng panonood ng mga laro sa mga tuntunin ng kanilang mga posibleng lipat sa ibang mga laro ay nagdudulot ng isang rekursibong matematikal na katuturan ng mga laro na ay pamantayan sa teorya ng larong kombinatoryal. Sa itong katuturan, ang kada laro ay may notasyong {L|R}. Ang L ay pangkat ng mga posisyon ng laro na nagagamit, at gayon din para sa R at kanang manlalaro. Ipinapaliwanag ang kada posisyon sa L at R bilang isang laro sa pamamagitan ng parehong notasyon.

Para gamitin ang Domineering bilang halimbawa, mag-label ng bawa't isa sa labing anim na parisukat sa 4x4 na tabla sa pamamagitan ng isang sistema ng koordinado: (A1, A2, A3, A4, B1, ...), atbp. Tapos, naiilarawan ang inisyal na posisyon sa notasyon ng teorya ng larong kombinatoryal nang ganito:

$\{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \}.$

Sa pamantayang larong Cross-Cram, ang mga manlalaro ay naghahalinhinan, pero ang itong alternasyon ay implisitong inaatupag ng mga katuturan ng teorya ng larong kombinatoryal imbes na pag-encode sa mga katayuan ng laro:

$\{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.$

Inilalarawan ng laro sa itaas ang isang senaryo kung saan natitira ang lang isang tira para sa kada manlalaro, at nananalo ang manlalaro na gumawa ang galaw na iyon. (Mula sa diyagrama nilisan ang isang di-makabuluhang bukas na parisukat sa C3.) Ang {|} (na tinutukoy ang nag-iisang parisukat na nanatili pagkatapos ng tira) sa talaan ng galaw ng kada manlalaro ay tinatawag na larong sero, at maaaring daglatin bilang 0. Sa larong sero, walang balidong galaw para sa alinmang manlalaro, kaya awtomatikong nagpapatalo ang kasalukuyang manlalaro (kung kailan lumitaw ang larong sero).

Ang uri ng laro sa diyagrama sa itaas ay may simpleng pangalan: tinatawag na larong bituin, na maaaring daglatin bilang ∗. Sa larong bituin, ang nag-iisang balidong galaw ay nagdudulot ng larong sero, kaya awtomatikong nananalo ang kasalukuyang manlalaro (kung kailan lumitaw ang larong bituin).

Ang ibang uri ng laro, na hindi natatagpuan sa Domineering, ay isang laro na may pag-iikid, kung saan ang isang balidong tira ng L (kaliwa) o R (kanan) ay nagdudulot ng isang laro na nagdudulot naman (sa huli) sa unang laro. Nabubuo ng dama, halimbawa, ang isang pag-iikid pagkatapos ng promosyon ng isang piraso, dahil tapos puwede gumalaw nang pabalik-balik magpakailanman sa pagitan ng dalawang parisukat.

Mga daglat panlaro

Mga bilang

Kinakatawan ng mga bilang ang dami ng libreng galaw, o ang bentahe ng isang partikular na manlalaro. Sa kombensyon kinakatawan ng mga positibong bilang ang bentahe para sa L (Kaniwa), yamang kinakatawan ng mga negatibong bilang ang bentahe para sa R (Kanan). Rekursibong ipinapaliwanag, kung saan ang 0 ay base:

0 = {|}

1 = {0|}, 2 = {1|}, 3 = {2|}

−1 = {|0}, −2 = {|−1}, −3 = {|−2}

Ang larong sero ay isang pagkatalo para sa unang manlalaro.

Kumikilos ang suma ng mga bilang nang katulad ng mga buumbilang, halimbawa 3 + −2 = 1.

Bituin

Ang bituin, na sinusulat bilang ∗ o {0|0}, ay isang wagi para sa unang manlalaro dahil dapat gumawa ang itong manlalaro ng isang tira sa isang larong sero, at kaya manalo.

∗ + ∗ = 0, dahil dapat palitan ng unang manlalaro ang isang kopya ng ∗ sa 0, at tapos dapat palitan ng ibang manlalaro ang ibang kopya ng ∗ sa 0. Sa itong punto magpapatalo ang unang manlalaro, dahil inaatim ng 0 + 0 ang walang tira.

Ang larong ∗ hindi ay ni positibo ni negatibo. Ang anumang laro kung saan naging nananalo ang unang manlalaro ay tinatawag na malabo sa (tingnan din ang malabong lohika) o lito sa 0. Sa mga simbolo sumusulat tayo ng ∗ || 0.

Pataas

Ang pataas, na sinusulat bilang ↑, ay isang posisyon sa teorya ng larong kombinatoryal. Sa pamantayang notasyon, ↑ = {0|∗}.

−↑ = ↓ (pababa)

Ang pataas ay mahigpit na positibo (↑ > 0), pero impinitesimal.

Pababa

Ang pababa, na sinusulat bilang ↑, ay isang posisyon sa teorya ng larong kombinatoryal. Sa pamantayang notasyon, ↑ = {0|∗}.

−↑ = ↓ (pataas)

Ang pababa ay mahigpit na negatibo (↑ < 0), pero impinitesimal.

"Maininit" na laro

Ikonsidera ang larong {1|−1}. Ang parehong galaw sa itong laro ay bentahe para sa manlalaro na gumawa nila, kaya sinasabi na "mainit" ang laro. Ang ganitong laro ay mas mataas kaysa sa anumang bilang na mababa kaysa sa −1, mababa kaysa sa anumang bilang na mataas kaysa sa 1, at malabo para sa anumang bilang sa pagitan. Sinusulat bilang ±1. Nadadagdagan sa mga bilang, o pinaparami sa mga positibo, tulad ng inaasahan, halimbawa 4 ± 1 = {5|3}.