Kombinatoryal oyun teorisi

CGT olarak da bilinen kombinatoryal oyun teorisi, kombinatoryal oyunları inceleyen uygulamalı matematik ve teorik bilgisayar biliminin bir dalıdır ve "geleneksel" veya "ekonomik" oyun teorisinden farklıdır. CGT, özellikle iki oyunculu Nim oyunu olmak üzere tarafsız oyunlar teorisi ile ilişkili olarak ortaya çıkmış ve belirli kombinatoryal oyun türlerinin "çözülmesine" vurgu yapmıştır.

Bir oyunun kombinatoryal bir oyun olması için birkaç koşulu karşılaması gerekir. Bunlar:

Oyunda en az iki oyuncu olmalıdır.
Oyun sıralı olmalıdır (yani oyuncular sırayla oynamalıdır).
Oyun mükemmel bilgiye sahip olmalıdır (yani Poker'de olduğu gibi hiçbir bilgi gizli değildir).
Oyun deterministik (yani şansa bağlı olmayan) olmalıdır. Şans oyunun bir parçası değildir.
Oyunda tanımlanmış miktarda olası hamle olmalıdır.
Oyun eninde sonunda bitmeli.
Bir oyuncu artık hareket edemediğinde oyun sona ermelidir.

Kombinatoryal Oyun Teorisi büyük ölçüde iki oyunculu, sonlu ve bir kazananı ve kaybedeni olan (yani berabere bitmeyen) kombinatoryal oyunların bir alt kümesinin incelenmesiyle sınırlıdır.

Bu kombinatoryal oyunlar, her bir tepe noktası, ağaçta hemen altındaki oyundan belirli bir hamle ile sonuçlanan oyun olan ağaçlarla temsil edilebilir. Bu oyunlara oyun değerleri atanabilir. Bu oyun değerlerini bulmak, oyun eklemenin teorik kavramı gibi CG teorisyenlerinin büyük ilgi alanıdır. İki oyunun toplamı, her oyuncunun sırası geldiğinde iki oyundan yalnızca birinde hamle yapması ve diğerini olduğu gibi bırakması gereken oyundur.

Elwyn Berlekamp, John Conway ve Richard Guy teorinin kurucularıdır. 1960'larda birlikte çalışmışlardır. Yayımlanan çalışmaları Matematiksel Oyunlarınız için Kazanma Yolları adını taşıyordu.

Tanımlar

Teoride sol ve sağ olarak adlandırılan iki oyuncu vardır. Oyun, sol ve sağın diğer oyunlara hamle yapmasını sağlayan bir şeydir. Örneğin, satranç oyununda olağan bir başlangıç düzeni vardır. Bununla birlikte, ilk hamleden sonraki bir satranç oyununu farklı bir kurguya sahip farklı bir oyun olarak da düşünebiliriz. Dolayısıyla her pozisyona bir oyun da denir.

Oyunlar {L|R} gösterimine sahiptir. L {\displaystyle L} $L$ sol oyuncunun hareket edebileceği oyunlardır. R {\displaystyle R} $R$ sağ oyuncunun hareket edebileceği oyunlardır. Eğer satranç notasyonunu biliyorsanız, olağan satranç düzeni şu oyundur

{ 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 \}$

"..." noktaları birçok hamle olduğu anlamına gelir, bu nedenle hepsi gösterilmemiştir.

Satranç çok karmaşıktır. Daha kolay oyunlar düşünmek daha iyidir. Örneğin Nim, düşünmesi çok daha basit bir oyundur. Nim şöyle oynanır:

Sıfır veya daha fazla sayaç yığını vardır.
Bir turda, bir oyuncu bir desteden istediği kadar sayaç alabilir.
Hamle yapamayan oyuncu kaybeder.

Nim'in en kolay oyunu hiç sayaç olmadan başlar! Böyle bir durumda iki oyuncu da hareket edemez. Bu {|} olarak gösterilir. Her iki taraf da boştur, çünkü iki oyuncu da hareket edemez. İlk giden oyuncu hareket edemez ve bu yüzden kaybeder. CGT'de insanlar genellikle {|} sembolünü 0 (sıfır) olarak yazarlar.

Bir sonraki en kolay oyunda sadece bir sayaç ile sadece bir yığın vardır. Eğer soldaki oyuncu ilk hamleyi yaparsa, o oyuncu sayacı almak zorundadır ve sağdaki oyuncunun hamlesi yoktur ({|} veya 0). Bunun yerine önce sağ hamle yaparsa, sol için daha fazla hamle olmayacaktır. Yani hem sol hem de sağ 0'a hamle yapabilir. Bu {{|}|{|}} ya da {0|0} şeklinde gösterilir. İlk hamleyi yapan oyuncu kazanacaktır. 0|0}'a eşit oyunlar çok önemlidir. Bunlar * (yıldız) sembolü ile yazılır.

Sorular ve Yanıtlar

S: Kombinatoryal Oyun Teorisi nedir?

C: Kombinatoryal Oyun Teorisi (CGT), kombinatoryal oyunları inceleyen uygulamalı matematik ve teorik bilgisayar biliminin bir dalıdır ve "geleneksel" veya "ekonomik" oyun teorisinden farklıdır.

S: Bir oyunun kombinatoryal bir oyun olarak kabul edilmesi için hangi koşulları karşılaması gerekir?

C: Bir oyunun kombinatoryal oyun olarak kabul edilebilmesi için en az iki oyuncuya sahip olması, sıralı olması (yani oyuncuların sırayla oynaması), mükemmel bilgiye sahip olması (yani hiçbir bilginin gizli olmaması), deterministik olması (yani şansa bağlı olmaması), şansın oyunun bir parçası olmaması, belirli miktarda olası hamle olması, oyunun eninde sonunda bitmesi ve bir oyuncu artık hamle yapamadığında oyunun sona ermesi gerekir.

S: Kombinatoryal Oyun Teorisi ne tür oyunlara odaklanır?

C: Kombinatoryal Oyun Teorisi büyük ölçüde kazananı ve kaybedeni olan (yani beraberlikle sonuçlanmayan) iki oyunculu sonlu oyunlara odaklanır.

S: Bu tür oyunlar nasıl temsil edilir?

C: Bu tür oyunlar ağaçlarla temsil edilebilir ve her bir tepe noktası, ağaçta hemen altındaki belirli bir hamleden elde edilen oyunu temsil eder.

S: CG teorisyenleri için bazı hedefler nelerdir?

C: CG teorisyenlerinin bazı hedefleri arasında bu tür oyunlar için değerler bulmak ve her oyuncunun iki farklı oyunda sadece bir hamle yaparak sırası geldiğinde diğerini değiştirmeden bırakmasını içeren "oyun ekleme" kavramını anlamak yer almaktadır.

S: CGT'yi kim kurdu?

C: Elwyn Berlekamp, John Conway ve Richard Guy 1960'larda yayınladıkları Winning Ways for Your Mathematical Plays adlı çalışmalarında CGT'yi kuran kişiler olarak anılmaktadır.