Matematik Atölyesi – Oyun #9

Ne demek “beraber bitti”?!

Tarihin gelmiş geçmiş en basit ve güzel oyunu olarak gördüğüm futbolda sevmediğim tek şey bir maçın berabere bitmesidir. Her ne kadar kazanan olmayan durumlar yaşansa da sezon sonunda şampiyonluğu sadece bir takım alır. Yani nihai sonuçta beraberlik yoktur ki böyle olması çok doğal. Zaten beraberlik kavramı oyun oynamanın amacına ters değil mi? Yoksa bunu bir tek ben mi düşünüyorum?!

zidane-juve
Pek berabere kalmak istiyorlarmış gibi bir görüntü yok sanki.

Daha önce de bahsetmiştim: Ben bir oyun-severim. Fakat bir oyunun berabere bitmesini hiçbir zaman kabul edemedim. Bu yüzden örneğin küçükken x-o-x oyununu sonucunda beraberlik mümkün olduğu için hiç severek oynamazdım. Hatta öyle ki oyun berabere bitmesin diye bilerek yanlış hamleler yapardım.

Çözüm Hex

  • Dokuz tane düzgün altıgeni aşağıdaki gibi dizin:
    20190308_152834
  • Karşılıklı kenarlar aşağıdaki gibi kırmızı ve mavi olarak ayrılsın:
    rm
  • Oyunculardan biri kırmızı, diğeri mavi rengi seçsin.
  • Oyuna ilk başlayan yazı-tura ile belirlensin.
  • Oyuncular sırayla istediği boş kutuyu seçsin.

Amaç: Kırmızı kalemli oyuncu kırmızı, mavi kalemli oyuncu ise mavi kenarlar arasında bağlantı kurmaya çalışır. Bağlantıyı kuran oyunu kazanmış olur.

Hex’in x-o-x’den en önemli farkı şudur: Hex hiçbir zaman berabere bitmez.

Hex’de oyunculardan biri muhakkak oyunu kazanır.

Örnek: Kırmızı başlarken.

Hex’de beraberlik olması için çabalayalım. Bu; ne kırmızı ne de mavi kenarlar arasında bağlantı kurulmaması anlamına gelir.

Diyelim ki kırmızı ilk iki hamlesini aşağıdaki gibi yaptı:

20190308_152908.jpg

Mavi oyuncu bu durumda kırmızının bağlantıyı kurmaması için aşağıdaki tercihi yapmış olması gerekir:

20190308_152935.jpg

Kırmızı üçüncü tercihinde mavinin en altta kendine yol yapmasını engellemesi lazım. Fakat mavinin yolunu tamamlaması için iki tercihi vardır:

xx

Bu yüzden kırmızı hangi kutuyu seçerse seçsin mavinin diğer kutuyu seçmesiyle oyunu mavi kazanır:

İşin fenası kırmızı maviyi engellerse bu sefer kendi kırmızıdan kırmızıya bağlantı kurmuş oluyor. Bu da her ihtimalde oyunun berabere bitemeyeceğini gösteriyor.

20190308_153134

Rastgelelik

Hex oyunu kağıdımız aşağıdaki gibi numaralandırılmış olsun:

20190308_153150

5’er tane kırmızı ve mavi kağıdı karıştırıp sırayla çekelim. Denemem aşağıdaki gibi sonuçlandı:

20190308_153218

Bu rastgele Hex’de maviler kazanmıştır.

Oyundaki rastgelelik için numaraların farklı dizildiği bir oyun kağıdını kullanalım:

20190308_153240

Bu sefer sırayla çekilen kırmızı ve mavi kağıtlar aşağıdaki gibi dizilir:

20190308_153259

Bu rastgele Hex’i de kırmızılar kazanmıştır. Her halükarda oyunda bir kazanan vardır.

Biraz Tarih
Hex ilk olarak 1942’de Danimarkalı mimar Piet Hein tarafında bulunmuştu. 1948 civarında ünlü matematikçi John Nash’in de Hein’dan bağımsız olarak Hex’i bulduğu bilinir. Hex ismini ise oyunu piyasaya süren Parker Brothers vermişti.

Bi’ Göz Atmakta Fayda Var

Orijinal hex kağıdı 11’e 11 boyutlarındadır. Linkte bulunan kağıdın çıktısı üzerinde oyunu oynayabilirsiniz. Bunu yaparken kazanma stratejileri üzerine düşünmeye çalışın.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Sosyal Durumlar #3

Sevgililerin Savaşı

Bruce: Tüm sezon boyunca bu maçı bekledim. Ezeli rakibimizle evimizde oynayacağız. Bu zaten heyecanlı olmak için yeterli bir sebepken maçın sonucu şampiyonu belirleyecek: Biz ya da onlar.

Derby-Matches-Derby-Days

Kombine bilet almamın tek nedeni bu maça gidebilmekti. Zaten 2006’dan beri her derbi maçına gittim. Bu sene maçın sonunda şampiyonluk olması ise pastanın çileği olacak. Yenmeliyiz ve ben de buna tanık olmalıyım.

Jane: En sevdiğim müzik grubu son turnesini yapıyor ve turne içerisinde yaşadığım şehir de var. Onları ilk ve son defa canlı izleme şansını yakaladım.

635717049166625894-XXX-20150704-FOO-FIGHTERS-CONCERT-AN-32.JPG-USA-DC-

Grubu ilk kez 11 yaşındayken dinlemiştim. O gün dinlediğim albüm aynı zamanda kişisel favorim ve grubun en çok satan albümü. Veda turnesinde oldukları için en çok o albümden şarkı çalacaklarmış. Bu konseri kaçırmamam gerekiyor.

Bir süredir beraber olan Bruce ve Jane çifti önemli bir açmazda: İkisinin de uzun zamandır beklediği aktiviteler aynı güne, hatta aynı saate denk geldi.

İdeal Çift

Jane ile Bruce’un birbirlerine eşit (en azından denk) derecede aşık olduğunu varsayalım.

Çift için birlikte zaman geçirmek önemli. Bu 1 puan olsun.

Jane için konsere gitmek, Bruce içinse maça gitmek ekstra mutluluk verir. Bu da ekstra 1 puan olsun.

Eğer ikisi farklı aktivitelere giderse, ikisi de eşit derecede mutsuz. Yani farklı yerlerde olmak ikisine de 0 mutluluk getirsin.

O halde oyunun matrisi aşağıdaki gibi olur:

IMG_6574

Eğer Jane maça, Bruce konsere veya Jane konsere, Bruce maça giderse her ikisi de 0 mutluluk yaşar. Oyunda Jane için en iyi seçim konser, Bruce için en iyi seçim ise maçtır. Eğer konser-maç seçimi Nash dengesi ise, her halükarda ikilinin tercihleri değişmemelidir. Önce Bruce’un maça gittiğini varsayalım.

IMG_6574

Bunu bilen Jane konsere giderse 0, maça giderse 1 puan alacaktır. Jane maça gitmeyi seçer. Yani denge maç-maç olur. Nash dengesi için bir de Jane’in ilk seçeneği yaptığını varsayalım. Jane konsere giderse Bruce için aşağıdaki tercihler kalır:

IMG_6574-2.jpg

Bu durumda Bruce konsere giderse 1, maça giderse 0 puan alacağı için konsere gitmeyi tercih eder. Konser-konser tercihi Nash dengesidir.

Oyunda iki tane Nash dengesi vardır: Her ikisinin de maça veya konsere gitmesi. Bu da ancak çift birlikte karar verirse gerçekleşir.

Kişisel fikrim: İdeal çift de olsa böyle bir durumda Bruce maçın skorunu telefonundan takip eder.

Jane, Bruce’u Pek Sevmiyor

Bazı çiftler vardır ki yanlarında biraz zaman geçirseniz dahi ilişkilerinin pek uzun sürmeyeceğini anlarsınız. Bizim çiftimiz için de Jane’in Bruce’dan yavaş yavaş uzaklaştığını varsayalım. Yani Jane Bruce’u artık sevmiyor, fakat Bruce Jane’e hala aşık. Jane için sadece konserde olmak önemliyken, Bruce için Jane ile birlikte olmak ve maça gidebilmek önemli.

Problemimizi bu bilgiler üzerine kuracağız.

Her ikisi de konsere giderse: Jane Bruce ile beraber olmaktan 0, konserde olmaktan 2, toplamda 2 puan alır. Bruce ise sadece Jane ile beraber olduğu için 1 puan alır.

Her ikisi de maça giderse: Jane konserde olmadığı için -1, Bruce ile birlikte olduğu için 0, toplamda -1 mutluluk puanı alır. Bruce ise beraber oldukları için 1, maçta oldukları için ekstra  1, toplamda 2 puan alır.

Jane konsere, Bruce maça: Jane konserde olmaktan 2, Bruce ile olmamaktan 0, toplamda 2 puan alır. Bruce ise maça gitmekten 1, Jane ile olmamaktan 0, toplamda 1 puanda kalır.

Jane maça, Bruce konsere: Jane konserde olmadığı için -1, Bruce ile olmamaktan 0, toplamda -1 puan alır. Bruce ise konserden ve Jane ile olmamaktan 0’ar puan alır.

O halde matris aşağıdaki gibi olur:

IMG_6573

Jane için en iyi seçenek konsere gitmek iken, Bruce için en iyi seçenek maça gitmektir. Gelin konser-maç seçeneğinin Nash dengesi olup olmadığını test edelim.

IMG_6573

Eğer Jane Bruce’un maça gideceğini bilirse konseri seçmesi 2, maçı seçmesi -1 puan getirir. Bu yüzden Jane konsere gitmeyi seçer. Yani konser-maç seçeneği değişmemiş olur.

IMG_6573-3.jpg

Eğer Bruce Jane’in konsere gideceğini bilirse konser ve maç seçenekleri ona 1’er puan getirir. Yani Bruce için iki ihtimal de aynıdır.

Bu yüzdendir ki oyunda iki tane Nash dengesi vardır: Konser-konser ve konser-maç. Her iki seçenek de (2,1) sonucunu verir.

Bi’ Göz Atmakta Fayda Var

Bruce’un Jane’e artık aşık olmadığı durumda neler olabileceğini, matrisi ve Nash dengesini bulun.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Sosyal Durumlar #1

Haylaz Öğrenciler

Matematik sınavı ertesi gün yapılacak. En yakın arkadaşınızla berabersiniz ve önünüzde iki seçenek var: Ders çalışmak veya konsol oyunu oynamak. Kararı hızlı verip altı saat boyunca Fifa oynadınız. Verdiğiniz kararın sonucunda sınavdan neredeyse boş kağıt vererek çıktınız. Fakat sınavdan önce bir plan yapmıştınız: Soruları öğrenip aynı günün akşamına cevapları kağıda geçirmek ve sonraki gün içerisinde sınav kağıtlarını değiştirmek.

Sınavdan sonraki sabah öğretmenler odasının bulunduğu kattaki tuvalette saklanıp herkesin derse girmesini beklediniz. Ders zili çalıp tüm koridorlar boşaldıktan sonra sınav kağıtlarını değiştirmeyi başardınız fakat sevincinizi yaşarken okul müdürüne denk geldiniz.

Müdür, iki öğrencinin ders saatinde öğretmenler odasının bulunduğu katta ne aradığını düşünmüştü: “Bu çocuklar öğretmenler odasına girip orada bir iş karıştırmış olmalı.”

Müdürün elinde herhangi destekleyici bir kanıt yoktu. Fakat sizi ayrı odalara gönderip tek tek sorgulamayı akıl etmişti. Her halükarda ders kırdığınız için birer gün ceza yiyecektiniz. Ama sınav kağıdını değiştirmenin çok daha büyük cezası olduğunu biliyordunuz.

Tek başınıza oturmuş bunları düşünürken müdür bulunduğunuz odaya geldi. Arkadaşınızın her şeyi itiraf ettiğini ve sizin de yaptığınızı itiraf etmeniz gerektiğini, aksi takdirde daha büyük bir ceza alacağınızı söyledi.

Acaba müdür haklı mı? Arkadaşınız gerçekten sizi satmış olabilir mi?

Ne yapmanız gerekiyor? İtiraf mı edeceksiniz? Yoksa inkar mı?

Tutsak İkilemi

Bu hikaye aslında matematiğin önemli bir alt branşı olan oyun teorisini açıklayan tutsak ikilemi isimli oyunun bir parçasıdır. Tutsak ikilemi en basit haliyle şöyle özetlenebilir: Daha az ceza yemek için arkadaşını satıp sadece kendinizi mi düşünürsünüz? Yoksa hem kendiniz hem de arkadaşınız için en iyi seçimi mi yaparsınız?

Oyun teorisinde işbirlikçi oyunlarda önemli olan şudur: Herkesin kaderi ortak verilecek olan kararlara bağlıyken bencil olup sadece kendi iyiliğiniz yönünde mi yoksa herkesin iyiliği yönünde mi karar verirdiniz?

Ceza Matrisi

  • Tüm oyuncuları listeleyin.
  • Her oyuncu için alternatif seçimleri belirtin. Bu seçimlere strateji de denir.
  • Eğer iki oyuncu varsa birinci oyuncunun seçimleri matrisin satırlarına, ikinci oyuncunun seçimleriyle sütunlarına yazılır.
  • Matriste bulunan sayı ikilileri sırasıyla birinci ve ikinci oyuncunun o matris tercihinde alacağı sonucu gösterir.

Haylazlar için tüm matris aşağıdaki gibidir:

IMG_6314

İhtimaller

Eğer ilk oyuncu arkadaşını satmayı tercih ederse ya 10 gün ceza yer ya da serbest kalır.

IMG_6317

Bu durumda ikinci oyuncunun seçeneği satmak olursa oyuncular 10’ar gün ceza alacakken, sadık kalması durumunda birinci oyuncu ceza almaz. İkinci oyuncuysa 15 gün ceza alır.

Eğer ilk oyuncu arkadaşını satmamayı tercih ederse 15 ya da 1 gün uzaklaştırma alır.

IMG_6320

Bu durumda ikinci oyuncu arkadaşını satarsa serbest kalır, ilk oyuncu 15 gün uzaklaştırma alır. Eğer ikinci oyuncu da arkadaşına sadık kalırsa her iki oyuncu 1’er gün uzaklaştırma almış olur.

Bu noktada durun ve düşünün: Aynı durumda kalsaydınız neyi seçerdiniz?

Bencil

Oyuncular için en iyi senaryo ikisinin de birer gün ceza almasıdır. Bu da ancak her iki oyuncunun da birbirine sadık kalmasıyla gerçekleşir. Fakat burada dikkate alınması gereken bir şey daha var: En kötü senaryo.

Oyundaki en kötü senaryo oyunculardan birinin arkadaşına sadık olduğu, diğerininse olmadığı durumdur. Bu tercihler sonucunda arkadaşını satmayan oyuncu 15 gün ceza alır ki tüm oyundaki en ağır ceza budur. Arkadaşını satan ise ceza almadan kurtulur.

Eğer oyuncular bencilse, her ikisi de serbest kalacağı seçeneği tercih eder. Bu da arkadaşını satmak anlamına gelir. Fakat her iki oyuncu da birbirini satarsa 10’ar gün ceza alırlar.

Eğer oyuncular “birimiz hepimiz, hepimiz birimiz için” düşüncesine sahip olursa her ikisi için en ideal durumu tercih ederler. Böylece 1’er gün ceza ile kurtulurlar. Bunun için iki oyuncunun da arkadaşını satmaması gerekir.

indir (8)
John Nash

Nash Dengesi: Bir oyunda tüm oyuncuların hareketleri karşılaştırıldığında ortaya çıkan optimum sonuçtur. Nash dengesinde herkes kazanır çünkü herkes istediği sonucu almıştır. Bir oyunda Nash dengesinin olup olmadığını anlamak için her oyuncuya diğerlerinin hangi seçimi yaptığı açıklanır. Eğer buna rağmen yapılan oyuncuların seçimleri değişmiyorsa, burada Nash dengesi vardır.

Oyun teorisinin en önemli özelliklerinden biri olan Nash dengesi ismini ünlü matematikçi John Nash’den alır. (Akıl Oyunları filmini izlemiş olanlarınız bu isme aşinadır.) Nash’in düşüncesine göre tutsak ikileminde denge her iki oyuncunun da sadece kendini düşünüp diğerini satmasıdır.

Peki ama neden?

Sadakat

Öğrencilerin birbirine sadık olduğunu ve sonuçta 1’er gün ceza aldıklarını varsayalım. Eğer her öğrenciye diğerinin seçimini söylersek, ne yaparlardı?

İlk öğrenciye ikinci öğrencinin sadık olduğunu söyleseydik seçimini değiştirip arkadaşını satardı. Çünkü bu seçim sayesinde ceza almadan kurtulabilirdi.

IMG_6318
İkinci öğrenci sattıysa ilk öğrenci 0 ya da 1 gün cezadan birini seçebilir. Tabi ki 0’ı seçer.

İkinci öğrenci için de aynı şeyi yapardı!

O halde öğrenciler sadık olduklarını bildiklerinde seçimlerini değiştirir ve birbirini satardı. Sonuç: 10’ar gün ceza.

İhanet

Öğrencilerin birbirini sattığını ve sonuçta 10’ar gün ceza aldıklarını varsayalım. Eğer her öğrenciye diğerinin seçimini söylersek, ne yaparlardı?

İlk öğrenciye ikinci öğrencinin ihanet ettiğini söyleseydik, ilk öğrenci seçimini değiştirmezdi. Çünkü değiştirdiği takdirde 10 yerine 15 gün ceza alırdı.

IMG_6319
İkinci öğrenci arkadaşını satarsa, ilk öğrenci 10 ya da 15 gün cezadan birini seçer. Tabi ki ilk öğrenci 10 günü seçer.

İkinci öğrenci için de aynı şey geçerlidir!

O halde öğrenciler birbirlerine ihanet ettiklerini bildikleri durumda seçimlerini değiştirmezdi. Sonuç aynı kalırdı: 10’ar gün ceza.

Her iki durumda da sonuç birbirini satmak olduğuna göre, bu Nash dengesidir.

Bu çok ilginç bir sonuç. Çünkü oyuncular için en iyi ihtimal sadık kalıp sadece 1 gün ceza almak olmasına rağmen Nash dengesi her oyuncu için en doğru seçeneğin arkadaşını satmak olduğunu, yani 10 gün cezayı seçer. Bu durum oyunculardan birinin diğerinin neyi seçtiğini bilmediği her oyunda geçerlidir.

M. Serkan Kalaycıoğlu

Real Mathematics – Social Situations #1

Lazy Students

Mathematics test is the next day. You and your best friend have two options: Study for it or play video games. Your decision was made easily and you ended up playing Fifa for 6 hours. Obviously you choked during the exam and now you two are just waiting for an F to be announced. Although, you were prepared for such situation: Your plan was to memorize the questions, solve them at night and try to change your papers the next day.

Next day, early in the morning you went directly to the floor where teacher’s lounge is at. You hid inside the toilets and waited for first lessons to start. When you heard the bell, you let yourselves out of the toilet and managed to change your exam papers. You were cocky as you were walking down the corridors which caused principal to catch you.

Principal was wondering what these two were doing at this floor while they should have been in class. Principal was sure of one thing: They did something bad. He (let’s assume principal is a he) decided to separate students and interrogate them one by one.

As you were waiting in principal’s room alone, you were thinking that principal has no evidence whatsoever. You were aware that you will get suspended for 1 day as you were caught ditching class. Nevertheless if they understand that you changed your exam papers, punishment would be much harder.

Now principal is back. He claims that your friend betrayed you and told everything, and if you come clean you will be getting a minor penalty. In case you reject confessing you will get a much harder punishment.

Is he right? Did your friend really give you away?

What should you do? Confess or deny?

prisoner-dilemma

Prisoner’s Dilemma

This story is actually a different version of an example known as prisoner’s dilemma. Prisoner’s dilemma is the core example to explain an important branch of mathematics called game theory. To sum it up briefly prisoner’s dilemma examines whether you would sell your friend to avoid punishment or be loyal to him and make the best possible choice for both of you.

In game theory’s cooperative games this question is vital: When you are in a situation where everyone’s choices affects the result, would you be selfish and only consider your outcome or would you choose for the benefit of the group?

Punishment Matrix

  • List all the players.
  • Show alternative choices for each player. These choices are also called “strategies”.
  • If there are two players, choices for the first player would be represented in the rows. For the second player choices are represented in the columns.
  • Every entry inside matrices represents the utility or payoff to the first and second player respectively.

Then the punishment matrix for the lazy students become as follows:

IMG_6321

Possibilities

If first student decides to betray, he/she will get either 10 or 0 days of suspension.

IMG_6325

In this case, if second student betrays as well, both students will get 10 days of suspension each. If second student stays loyal and decides not to confess, he/she will get 15 days of suspension as the other gets 0.

If first student sticks loyal to his/her friend, then he/she will get either 15 or 1 day of suspension.

IMG_6324

In this case, if second student betrays, he/she will get no punishment. If second student also stays loyal, then they will get 1 day suspension each.

What would you choose if you were in this situation?

Selfish

Best scenario for both students is them to get 1 day suspension each. This could happen only if they both stay loyal to each other. But there is also another scenario to consider: Worst one.

The worst scenario in this game is to get 15 days of suspension which could only happen if one student stays loyal and the other betrays. In this case, the student who was loyal would get 15 days.

Hence there is the dilemma: Staying loyal gives the best possible outcome for both students. But individually it can cause the worst scenario too.

If students are selfish, they would consider the choice where they can get the minimum damage. For this game, it is getting 0 days of suspension. For both students this could only happen if they choose to betray. Here comes the second dilemma: If they both betray, they would get 10 days of suspension each.

If students are up for teamwork, they would consider the choice where there is least punishment in total for both of them. For this game it is getting 1 day of suspension each. This could only happen if they choose to stay loyal.

indir (8)
John Nash

Nash Equilibrium: Each player’s strategy is optimal when considering the decisions of other players. In Nash equilibrium every player wins because everyone gets the outcome they desire. To test if the Nash equilibrium exists in a game, reveal each player’s strategy to the other players. If no one changes his/her strategy, then there is a Nash equilibrium.

Nash equilibrium was discovered by famous mathematician John Nash whom you might have heard from the popular Hollywood movie called “A Beautiful Mind”.

What is so special about prisoner’s dilemma? And also what is the Nash equilibrium for our lazy students?

Prisoner’s dilemma is a very special example as it gives out an incredible result. In our lazy student game Nash equilibrium is when both students choose to betray. This is fascinating as the best possible outcome for the students to stay loyal and get 1 day of suspension each.

How?

Loyalty

Let’s assume that both students stay loyal and also assume that we told them what decisions they have made.

If first student knows that the second student stayed loyal, he/she would change his move and decide to betray so that he/she will get 0 days of punishment.

IMG_6323
If second student stays loyal, first would choose 0 over 1.

Same goes for the second student!

In the end both students would betray each other.

Betrayal

Now let’s assume that they both betrayed each other and we told them what decision they have made.

If first student knows that the second betrayed him/her, he/she wouldn’t change his/her first decision.

IMG_6322
If second student betrays, first student would choose 10 days over 15 days.

Same goes for the second student!

In the end both students wouldn’t change their decisions and betrays each other.

This is why betraying and getting 10 days of punishment instead of 1 day is the Nash equilibrium.

M. Serkan Kalaycıoğlu