Prisoner's Dilemma : From Classroom to Hollywood

    เมื่อครั้งที่ Microsoft ประกาศตัว Web Service ใหม่ๆ นั้น ทาง DevX.com ก็ได้สร้างกิจกรรมทำ Online Programming Game โดยใช้ Technology ของ Web Service ซึ่งเกมส์นี้ก็คือ Prisoner's Dilemma นั่นเอง ผมเองก็เคยลงบทความเกี่ยวกับเรื่องนี้เหมือนกัน ลองย้อนไปอ่านดูได้ครับ วันนี้ผมขอเขียน Prisoner's Dilemma อีกมุมหนึ่งที่ไม่เกี่ยวกับ DevX.com

   

ที่มาของ Prisoner's Dilemma

    เกมส์นี้คิดค้นกันมากว่า 50 ปีแล้วครับ ดูเหมือนเกมส์ง่ายๆ ที่ไม่สามารถยึดหลักอะไรได้เลย คุณตอบได้เพียงว่าจะร่วมมือโดยการปฏิเสธทุกข้อกล่าวหา (Cooperate) หรือกล่าวหาเพื่อนของคุณเลยว่าเป็นคนผิด (Defect) แถมยังต้องเล่นพร้อมกัน การเลือกในอดีตไม่ส่งผลในตาปัจจุบัน กติกาดูน้อยเกินไปที่จะไปหาหลักการ แต่จริงๆ แล้วเรื่องนี้ซับซ้อนพอสมควรครับ

    เกมส์นี้ถ้าว่าไปแล้วเป็นเกมส์หนึ่งใน Game Theory ซึ่งเป็นศาสตร์หนึ่งในวิชาเศรษฐศาสตร์ เกมส์พวกหมากรุกหมากฮอตก็เข้าข่าย Game Theory เหมือนกัน เนื่องจาก Prisoner's Dilemma เป็นเกมส์ที่มีกติกาเรียบง่าย สามารถจำลองสถานการเล่นในห้องเรียนได้สะดวก ดังนั้นเกมส์นี้ถ้าเปรียบเทียบไป มันก็คือ Hello, World ของ Game Theory นั่นเอง

  

    คงต้องออกตัวหน่อยว่าผมไม่ได้เอกเศรษฐศาสตร์ เนื้อหามันอาจจะคลาดเคลื่อนได้ ถ้าใครเห็นว่าเพี้ยนตรงไหนบอกกันได้ครับ

 

เล่นแบบไม่เสี่ยง

   โจทย์ต้นฉบับนั้นเป็นเรื่องติดคุก ถ้าใครติดน้อยที่สุดก็ชนะ แต่ผมจะปรับตัวเลขให้เป็นบวก ใครใด้คะแนนสูงสุดคนนั้นชนะ จะทำให้เข้าใจได้ง่ายกว่า ผมลองเปลี่ยนตัวเลขเป็นดังนี้

    ผู้เล่นคนแรก Cooperate คนที่ 2 Cooperate แบบนี้ คนแรกได้ 3 คะแนน คนที่ 2 ก็ได้ 3 คะแนน
    ผู้เล่นคนแรก
Cooperate คนที่ 2 Defect แบบนี้ คนแรกได้ 0 คะแนน คนที่ 2 ได้ 5 คะแนน
    ผู้เล่นคนแรก
Defect คนที่ 2 Cooperate แบบนี้ คนแรกได้ 5 คะแนน คนที่ 2 ได้ 0 คะแนน
    ผู้เล่นคนแรก
Defect คนที่ 2 Defect แบบนี้ ได้ไปคนละ 1 คะแนน

    ถ้ากติกาเป็นแบบข้างบน คุณว่าเล่นแบบปลอดภัยคุณควรจะเลือก Cooperate หรือ Defect คำตอบก็ไม่ยากครับ จุดสมดุลอยู่ที่คนแรกควรเลือก Defect ส่วนคนที่ 2 เมื่อคนแรกเลือก Defect แล้ว ตัวเองต้องเลือก Cooperate เพื่อให้ตนเองได้ 1 ซึ่งดีกว่าไม่ได้เลย แต่เมื่อต้องเล่นพร้อมกัน ดังนั้นจึงควรเลือก Defect ครับ

    จุดสมดุลที่ผมกล่าวถึงนั้น เราเรียกว่า Nash Equilibrium (พหูพจน์คือ Nash Equilibria) ซึ่งคิดค้นโดย John Nash นักเศรษฐศาสตร์รางวัลโนเบิล หลักการหา ก็ใช้วิธีการสร้าง Game Tree จากนั้นก็ตัดทางที่ได้รับผลประโยชน์น้อยออก (Dominanted Strategy) ซึ่ง Game Tree ตัวนี้เองเป็นรากฐานของ MiniMax ซึ่งเป็น Algorithm ที่ใช้ในการเดินหมากกระดานต่างๆ

 

IPD : Iterative Prisoner's Dilemma

    เกมส์นี้ถ้าเล่นกันรอบเดียว แน่นอนครับ ผมคงเล่น Defect แต่ถ้าเล่นกันยาวๆ เป็นร้อยๆ รอบ เราจะใช้สูตรไหนดี ในปี 1981 มีการจัดแข่งขัน Algorithm สำหรับเล่นเกมส์นี้ มี Algorithm เป็นจำนวนมากที่เข้าแข่ง แต่ผลลัพธ์น่าสนใจ มี Algorithm ตัวหนึ่งที่ง่ายๆ แต่ได้คะแนนสูงสุด นั่นก็คือ Tit For Tat (ตาต่อตาฟันต่อฟัน) แต่ก่อนที่จะมาคุยกันเรื่อง Algorithm ตัวนี้ เรามาลองวิเคราะห์ความเป็นไปได้กันก่อนครับ

 

วิเคราะห์ Prisoner's Dilemma

    เกมส์นี้ดูเหมือนว่าเป็นเกมส์ที่แข่งขันกัน แต่ที่จริงแล้วเกมส์นี้ถ้ายิ่งแข่งก็ยิ่งทำให้บาดเจ็บครับ เหมือนสาดน้ำครับ ยิ่งสาดก็ยิ่งเปียก ทางที่ดีควรจะร่วมมือกัน เกมส์นี้ไม่ใช่เกมส์ที่ทำให้คู่แข่งขันบาดเจ็บมากที่สุด แต่หากเป็นเกมส์ที่ต้องหาวิธีที่ทำให้ตัวเองบาดเจ็บน้อยที่สุดครับ เรามามาวิเคราะห์กันเล่นๆ ดูครับ ค่าที่เป็นไปได้ทั้งหมดมี 4 ค่าเท่านั้นคือ

ผู้เล่นคนแรก Cooperate ผู้เล่นคนที่ 2 Cooperate แบบนี้ได้รางวัลครับฝรั่งเรียกว่า Reward
ผู้เล่นคนแรก
Cooperate ผู้เล่นคนที่ 2 Defect แบบนี้เสียรู้ ฝรั่งเรียกว่า Sucker's Payoff
ผู้เล่นคนแรก
Defect ผู้เล่นคนที่ 2 Cooperate แบบนี้โชคดี เรียกว่า Temptation
ผู้เล่นคนแรก
Defect ผู้เล่นคนที่ 2 Defect กัดกันตายทั้งคู่ ฝรั่งเรียกว่า  Punishment

หลักการแล้วผลตอบแทนที่ได้จากเกมส์จะเป็น

Temptation > Reward > Punishment > Sucker

ในที่นี้คือ

5 > 3 > 1 > 0

แต่ได้จาก Temptation ไม่ใช่เรื่องเกิดบ่อย เอาเป็นว่า Algorithm เป็นอะไรก็ตาม อย่าโดน Sucker เป็นดีที่สุดครับ

ยังมีกติกาที่สำคัญอีกข้อหนึ่งก็คือ    (Sucker + Tempation) / 2 < Reward      (5 + 0) / 2 <  3นั่นหมายความว่าเล่นแบบ Cooperate ดีกว่าเสี่ยงครับ

 

Algorithm - Tit for Tat

    หลักการของ TFT นั้น ซับซ้อนน้อยกว่าที่คิด เริ่มต้นโดยการเล่นแบบสุภาพในตาแรก โดยการ Cooperate ก่อน จากนั้นคู่ต่อสู้เล่นอะไรในตาที่แล้วก็จะเล่นตาม ซึ่งดูเผินๆ เหมือนการเลียนแบบ แต่มันปรัชญาอะไรลึกกว่านั้นครับ คือถ้าตาที่แล้วคู่ต่อสู้ Cooperate มา เมื่อดีมาก็ดีตอบ แต่ถ้าเล่น Defect มาก็จะเจอ Defect ตอบ ตาต่อตาฟันต่อฟันครับ แต่ถ้า Defect มาแล้วตาต่อมา Cooperate ก็พร้อมที่ให้อภัย ลองดู Code นี้ครับ                                                 

public class TitForTat : Player
{
	public override Action Play(Action @opponentLastTime)
	{
		if (@opponentLastTime== Action.None) {
			return Action.Coporate;
		} 
		return @opponentLastTime;
	}
}

    สังเกตดูนะครับ ข้างนอกจะส่งตัว @opponentLastTime คือการเลือกครั้งล่าสุดของคู่ต่อสู้มาให้เราพิจารณา ซึ่งถ้าพบกันเป็นครั้งแรก ตัวแปรนี้จะเก็บค่า Action.None ครับ  

Algorithm ทุกตัวที่ใช้ Inherit มาจาก Class Player ครับ ซึ่ง Class Player นี้ก็ไม่มีอะไรเลย

public abstract class Player
{
	public abstract Action Play(Action @opponentLastTime);
}

ที่ต้องให้ Inherit มานั้นเพื่อต้องการคุณสมบัติ Polymorphism จะได้เลือก Algorithm ได้ง่ายๆ ครับ

มีชนิดตัวแปรตัวหนึ่งที่ยังไม่ได้กล่าวถึง นั้นก็คือ Action เป็น enum ดังนี้ครับ

public enum Action
{
	Coporate,
	Defect,
	None
}

 

Algorithm - True Random

    ลองดู Algorithm อีกตัวหนึ่ง Random อย่างเดียว เชื่อว่าทุกคนคนเคยคิดถึง Algorithm ตัวนี้มาบ้าง ดัง Code นี้ครับ

public class TrueRandom : Player
{
	private static Random r = new Random();
	public override Action Play(Action @opponentLastTime)
	{
		if (r.Next(2) == 0) {
			return Action.Coporate;
		} else 	{
			return Action.Defect;
		}
	}
}

 

Algorithm - Defector

    แบบเกเรครับ Defect อย่างเดียวเลย ดูเหมือนว่าจะดีครับ

public class Defector : Player
{
	public override Action Play(Action @opponentLastTime)
	{
		return Action.Defect;
	}
}

 

Promoter

    โปรโมเตอร์เป็นผู้จับเอา Algorithm 2 ตัวมาแข่งขันกัน แล้วแสดงผลผู้ชนะ ในที่นี้ด้วยขนาดพื้นที่ที่จำกัด ผมเลยสร้างโปรโมเตอร์แบบง่ายๆ ซึ่งจับได้เพียง 2 ตัวมาแข่งกันเท่านั้น กติกาสากลของ IPD นั้นจะต้อง Register ผู้แข่งขันพร้อมกันหมด จากนั้นจะใช้วิธี Random เพื่อจับ 2 Algorithms ใดๆ มาเจอกัน จากนั้น Random ไปเรื่อยๆ ใครมีคะแนะสูงที่สุดก็ชนะไปครับ แต่ผมเอาง่ายๆ แบบนี้ก็แล้วกัน

class Promoter
{
	const int ROUND = 100;
	static void Main()
	{
		Player Player1 = new TrueRandom();
		Player Player2 = new TitForTat();
		Action action1, action2, oldAction1;		
		int score1 = 0;
		int score2 = 0;
		action1 = Action.None;
		action2 = Action.None;
		for (int i=1; i<ROUND; i++) {
			oldAction1 = action1;
			action1 = Player1.Play(action2);
			action2 = Player2.Play(oldAction1);		
			if (action1 == Action.Coporate) {
				if (action2 == Action.Coporate) {
					score1 += 3;
					score2 += 3;
				} else 	{
					score2 += 5;
				}
			} else 	{
				if (action2 == Action.Coporate) {
					score1 += 5;
				} else 	{
 					score1++;
					score2++;
				}
			}
		}
		Console.WriteLine("{0} years = {1}", Player1.GetType().ToString(), score1);
		Console.WriteLine("{0} years = {1}", Player2.GetType().ToString(), score2);
		Console.ReadLine();
	}
}

    ลองดูนะครับ ผมกำหนด Algorithm ทั้ง 2 ตัวเอาไว้ตอนแรก สามารถเปลี่ยนเป็น Algorithm อะไรก็ได้ โปรแกรมจะทำการแข่งขัน 100 ครั้งแล้วแสดงผลลัพธ์ ลองวิเคราะห์คะแนนดูนะครับ คะแนะต่ำสุดคือ 0 จะเกิดขึ้นเมื่อโดน Sucker's Payoff ทุกครั้ง ส่วนคะแนนสูงสุดคือได้ Temptation ทุกครั้งครับ แต่ที่จริงแล้ว ถ้าได้ 300 คือ Reward ทุกครั้งนี้ก็คือสุดยอดแล้วครับ ทุก Algorithm ต้องทำเพื่อให้ได้คะแนนสูงสุด

วิเคราะห์ Tit For Tat

    ถ้าลองเอาไปเล่นดู ก็ไม่ต้องแปลกใจนะครับ ว่าทำไม Tit For Tat ถึงแทบจะไม่เคยชนะใครเลย มันแพ้หมด แล้วมันชนะเลิศปี 1981 ได้อย่างไร มันแพ้ก็จริงครับ แต่ตัวเลขคะแนนขึ้นสูง ตัวเองก็รับเยอะ คู่ต่อสู้ก็รับเยอะกว่า แต่คุณต่อสู้พอไปเจอ Algorithm อื่นก็เสียคะแนะ ผิดกับ Tit For Tat ยังพยายามเชิดชูคู่ต่อสู้ พอคะแนนรวมเลยชนะครับ

 

Algorithm อื่นๆ

    Tit For Tat เป็น Algorithm เก่าแล้วครับ ปัจจุบันก็ไม่ใช่ Algorithm ที่เก่งกาจอีกต่อไป มีใหม่ๆ มาเยอะครับ เช่น  Pavlov, STFT, TF2T ยังมีอีกมากครับ เอาไว้ผมค่อยๆ Update web page นี้ก็แล้วกันครับ

 

ทิ้งท้าย

    ที่เลือกเขียนเรื่องนี้ ก็มีเหตุผลครับ เพราะมีคนเอาชีวประวัติของ John Nash ผู้เป็นปรมาจารย์เรื่อง Game Theory มาทำเป็นหนัง จะเข้าชิงปีนี้ด้วยครับ ตัวหนังผมยังไม่ได้ดู แต่เชื่อว่าน่าสนใจ เอาไว้ให้มันเข้า UBC แล้วค่อยดู ไปดูที่โรงมันเปลืองเงิน ผมเชียร์เรื่องนี้สุดตัวเลยครับ A Beautiful Mind