משחק האבנים – לראות את העתיד עם תכנות דינאמי

אתן יודעות מה עדיף בהרבה על קוד קצרצר ואלגנטי? קוד קצת פחות אלגנטי שאפשר לקרוא ולהבין מה הוא עושה. אין דבר יותר מחרפן מלקרוא קוד מלא ב-one liners ושמות משתנים בעלי שתי אותיות שעובד ואין לך מושג למה. 
חשבתי על זה כשראיתי את הפתרון הבא לשאלת התכנות הדינאמי המוכרת ״משחק האבנים״.

    def PredictTheWinner(self, A):
        memo = {}
        def maxscore(i,j):
            if (i,j) in memo:
                return memo[i,j]
            if i>j:
                return 0
            
            sA = A[i] + min( maxscore(i+1,j-1), maxscore(i+2,j  ) ) 
            sB = A[j] + min( maxscore(i  ,j-2), maxscore(i+1,j-1) )
            score = max(sA,sB)
            memo[i,j] = score
            return score

        p1 = maxscore(0,len(A)-1) # Score Player 1
        return p1>=(sum(A)-p1) # p1 >= p2

ספוילר – הפתרון הזה נכון, הוא עובד והוא יותר מהיר מהפתרון שלי. אבל מה שיותר חשוב (לדעתי) הוא שכשאני קוראת אותו, אין לי דרך להבין מה הוא עושה. כמו כן, ברור לי שאם אני אנסה לשנות משהו בקוד הזה יותר סביר שאני אקלקל אותו מאשר אם אני אשכתב אותו מחדש לגמרי. אז החלטתי להתחיל מההתחלה.

המשחק הולך כך – ישנה שורה של ערימות אבנים ושני שחקנים. כל שחקן בתורו בוחר ערימה מהצד הימני ביותר או השמאלי ביותר של השורה ולוקח אותה אליו. מי שמסיים את המשחק עם מספר האבנים הגדול ביותר מנצח.
והשאלה היא – בהינתן מערך A של מספרים שמייצג את מספר האבנים בכל ערימה, בדקו האם השחקן הראשון יכול לנצח.

השאלה הזו יכולה בקלות להישמע מפחידה. אין כאן שורה ברורה של צעדים ״נכונים״ שאפשר לעשות כדי להגיע לפתרון. השחקנים שלנו צריכים להיות חכמים. הם לא יכולים באופן ״טיפש״ לקחת תמיד מאותו צד או צד אקראי, הם אפילו לא יכולים לקחת תמיד את הערימה הגדולה מבין הימנית או השמאלית. השחקנים צריכים להסתכל לעתיד ולבחור בערימה שתיתן להם את הסיכוי הגדול ביותר לנצח בהנחה שהשחקן השני גם מנסה לנצח. סיוט.

אז איך אנחנו יכולות לראות את העתיד באלגוריתם שלנו?

הדרך היחידה לדעת מה המהלך האופטימאלי בכל שלב היא לחשב את כל התוצאות האפשריות ולבחור את הטובה מביניהן, וכך מצאנו את עצמנו בעולם התכנות הדינאמי. השאלה הזו דומה לשאלת תכנות דינאמי פשוטה יותר שפתרתי בעבר, אבל בהחלט מעלה את רמת הקושי.
נתחיל עם דוגמאות.

1. [1, 6, 4]
   שחקן א׳ יכול לבחור לקחת 1 או 4, אבל בכל מקרה שחקן ב׳ יקח לאחר מכן את 6 ושחקן א׳ את מה שנשאר. לכן, תוצאת המשחק תהיה א: 5, ב: 6.
2. [5, 40, 6, 4]
   במהלך הראשון שחקן א׳ יכול לבחור אם לקחת את 4 או את 5. שחקן ״טיפש״ יקח את 5, משום ש5>4. מהלך כזה מאפשר לשחקן ב׳ לקחת את 40 ולנצח את המשחק. לכן, שחקן חכם יבחר לקחת את 4. שחקן ב׳ יאלץ לקחת את 5 או 6, ושחקן א׳ יוכל לקחת את 40. תוצאת המשחק תהיה א: 44, ב: 11.

חשוב לי לציין שאני לא אכנס בפוסט הזה להסברים מלאים על איך תכנות דינאמי עובד. אם יהיה ביקוש אני אנסה לכתוב פוסט בעתיד, אבל בפוסט הזה אני רוצה להתרכז בפתרון הבעיה הספציפית הזו.אם אתן קוראות את הבעיה ולא מזהות למה מדובר בבעיית תכנות דינאמי, או מה קו המחשבה מאחורי הפתרון, אני ממליצה מאוד על הסרטון הזה.

אז קראתן את הבעיה וזיהיתן שמדובר בבעיית תכנות דינאמי קלאסי שתדרוש מכן לחשב את כל המהלכים האפשריים ולבחור את הטובים ביותר ביניהם. איך ניגשות לפתרון?

המבנה הכללי של בעיות תכנות דינאמי הוא מבנה של רקורסיה + ממואיזציה.

• הרקורסיה באה לענות על השאלה אם היה לי את הפתרון בעבור מערך באורך n-1, האם הייתי יכולה לפתור בעבור מערך באורך n?
• הממואיזציה באה לעזור להתמודד עם חוסר היעילות של בעיות רקורסיה.
  בהינתן מערך באורך n, כשבכל שלב יש לנו שני מהלכים פוטנציאליים – שחקן לוקח משמאל או שחקן לוקח מימין – למשחק יש 2ⁿ מסלולים אפשריים, שהרבה מהם יחזרו על עצמם. הממואיזציה תאפשר לנו לאחסן תוצאות ולחזור אליהן מאוחר יותר במקום לקרוא שוב ושוב לרקורסיה עם אותה תנאי התחלה.

הרקורסיה

בואו נראה מה יכול להיות הצעד הרקורסיבי שלנו.
כשניסיתי לפתור את השאלה הזו בפעם הראשונה התקשיתי למצוא את הצעד הרקורסיבי בגלל ניסוח השאלה שבלבל אותי. השאלה מנוסחת בצורה של תנאי בוליאני – ״בהינתן מערך A, בדקו האם השחקן הראשון יכול לנצח״. 

לפי כללי הרקורסיה הבסיסיים, אני צריכה לכתוב פונקציה שיודעת לחשב בעבור מערך באורך n-1 האם השחקן הראשון יכול לנצח, ורק להוסיף לכך את האיבר ה-n. 
הפונקציה הראשונה שניסיתי לכתוב נראתה כך – 

def canPlayer1Win(arr):
	takeLeft = canPlayer1Win(arr[1:])
	takeRight = canPlayer1Win(arr[0:-1])
	result = (takeLeft and condition(arr[0]) or (takeRight and condition(arr[n-1]))
	return result

מה ניסיתי לעשות פה?
התחלתי כרגיל מההנחה שיש לי פונקציה שיודעת לענות על השאלה בעבור מערך באורך n-1.
אז בהינתן מערך באורך n, השחקן יכול לקחת את הערימה מצד שמאל, או מצד ימין, ומה שנשאר לאחר מכן הוא מערך באורך n-1, ומכאן אני כבר יודעת לחשב.

הבעיה שנתקעתי בה היא השורה האחרונה, החלק שבו אני צריכה לחבר אני צריכה לחבר את התוצאה הרקורסיבית עם האיבר הנוסף. נסתכל על שתי דוגמאות שבהן המערך בגודל n-1 זהה, אבל המערך בגודל n הוא שונה, ונחשוב איך האיבר הנוסף משנה את התוצאה שלנו.

לדוגמא, נניח ויש לי את המערך [100, 1, 1] שבו שחקן א׳ בוודאות מנצח, ואני מוסיפה לו את האיבר [1] מצד ימין. במקרה כזה שחקן א׳ עדיין היה מנצח עם 101 נקודות למול 2. אבל אם במקום זאת הייתי לוקחת את  אותו המערך ומוסיפה לו את האיבר [100] מצד ימין עכשיו המשחק מסתיים בתיקו של 101 נקודות.

השאלה שאני צריכה לענות עליה היא – בהינתן פונקציה שיודעת להגיד לי ששחקן א׳ מנצח בעבור המערך [100, 1, 1], איזה תנאי אני יכולה להוסיף לאיבר האחרון כדי לדעת האם שחקן א׳ מנצח?
התשובה היא שאני לא יכולה. אין לי מספיק מידע. לא מספיק לנו לדעת האם בעבור מערך בגודל n-1 שחקן א׳ יכול לנצח, אנחנו צריכות לדעת מה סכום הנקודות ששחקן א׳ יכול לקבל בעבור מערך בגודל n-1, ואז נוכל לחשב האם האיבר החדש שהוספנו משנה את מאזן הכוחות.

פונקציה רקורסיבית מתאימה יותר תיראה כך – 

def maxScorePlayer1(arr):
	takeLeft = arr[0] + maxScorePlayer1(arr[1:])
	takeRight = arr[n-1] + maxScorePlayer1(arr[:-1])
	result = max(takeLeft, takeRight)
	return results

הפונקציה החדשה שלי מחזירה לי במקום ערך בוליאני את כמות הנקודות המקסימלי ששחקן יוכל לקבל בהינתן מערך באורך n-1. בעבור מערך באורך n היא מוסיפה את הערימה הימנית או הערימה השמאלית, ובוחרת בכמות הנקודות המקסימלי מביניהם.

אבל עוד לא סיימנו. בואו נחשוב איך הפונקציה יודעת כמה נקודות השחקן יקבל אם יבחר בערימה כלשהי? 
בדרך כלל כאן נכנס הקסם של רקורסיה ודברים פשוט עובדים מעצמם, אבל כאן המצב טיפה יותר מסובך כי יש לנו שני שחקנים. כלומר – אם שחקן א׳ משחק על לוח בגודל n, אז מי שעושה את הצעד הבא על לוח בגודל n-1 הוא כבר לא שחקן א׳, אלא שחקן ב׳. אם היינו משאירים את הפונקציה למעלה בדיוק כמו שהיא אז שחקן א׳ היה אוסף את כל הערימות וכל הנקודות בלי לתת לשחקן ב׳ הזדמנות לשחק. 

נסתכל שוב על הדוגמא ממקודם. בעבור המערך [100, 1, 1], הפונקציה תחזיר לי שהמקסימום שהשחקן הראשון יוכל לקבל (בהנחה שעכשיו שיחק במערך בגודל n, ועכשיו תור השחקן השני) הוא נקודה אחת.
עכשיו, בעבור המערך [1,1,100,100] המקסימום שהשחקן הראשון יקבל אם יבחר בערימה הימנית יהיה 100+1=101. המקסימום שהוא יוכל לקבל אם יבחר בערימה השמאלית יהיה זהה 1+100=101.
בעבור המערך [1,1,100,1] המקסימום שהשחקן הראשון יכול לקבל אם יבחר בערימה הימנית יהיה 1+1=2. המקסימום שהוא יוכל לקבל אם יבחר בערימה השמאלית יהיה 1+100=101. לכן, ברור שהשחקן יבחר בערימה השמאלית במצב כזה.

אז בואו נוסיף את שחקן ב׳ למשחק, ונגיד לפונקציה שלנו מי משחק ומקבל את הנקודות בכל קריאה.

def maxScorePlayer(arr, player):
	if player == ‘p1’:
		takeLeft = arr[0] + maxScorePlayer(arr[1:], ‘p2’)
		takeRight = arr[n-1] + maxScorePlayer(arr[:-1], ‘p2’)
		return max(takeLeft, takeRight)
	else:
		takeLeft = arr[0] + maxScorePlayer(arr[1:], ‘p1’)
		takeRight = arr[n-1] + maxScorePlayer(arr[:-1], ‘p1’)
		return max(takeLeft, takeRight)

בכל תור – בהתאם לשחקן שפועל בתור הנוכחי – אנחנו שולחות את השחקן המתאים לפונקציה בקריאה הבאה. השחקן ששיחק את התור מקבל את סכום הנקודות המקסימלי כמו מקודם ומחזיר אותו לפונקציה שקראה לו.

אבל רגע, עכשיו יצרנו סיטואציה לא הגיונית. כל קריאה אכן צריכה להפוך את התורות ולשלוח את השחקן הבא לשחק – אבל בפונקציה הנ״ל כל שחקן מרוויח את הנקודות של השחקן השני בטעות, נתקן זאת.

def maxScorePlayer(arr, player):
	sumTotal = sum(arr)
	if player == ‘p1’:
		p2TakeLeft = maxScorePlayer(arr[1:], ‘p2’)
		p2TakeRight = maxScorePlayer(arr[:-1], ‘p2’)
		return max(sumTotal - p2TakeLeft, sumTotal - p2TakeLeft)
	
	else:
		p1TakeLeft = maxScorePlayer1(arr[1:], ‘p1’)
		p1TakeRight = maxScorePlayer1(arr[:-1], ‘p1’)
		return max(sumTotal - p1TakeLeft, sumTotal - p1TakeLeft)

אוקי, עכשיו זה הרבה יותר הגיוני. בכל קריאה אנחנו מחשבות את מקסימום הנקודות שהשחקן הבא יקבל בצעד שלו, והנקודות שישארו אחרי הצעד שלו יהיו מקסימום הנקודות שהשחקן הנוכחי יוכל לקבל.

לדוגמא, אם זה המערך שלנו – [2, 5, 3, 2]
אם בתור שלנו ניקח את הערימה השמאלית, השחקן הבא יקבל את הלוח – [2, 5, 3].  בלוח כזה המקסימום שהשחקן הבא יוכל לקבל עד סוף המשחק הן 5 נקודות. המקסימום שאנחנו נוכל לקבל הן – 2+3+5+2-5=7

אם בתור שלנו ניקח את הערימה הימנית השחקן הבא יקבל את הלוח [5, 3, 2]. בלוח כזה המקסימום שהשחקן יוכל לקבל עד סוף המשחק הן 7 נקודות. המקסימום נקודות שאנחנו נוכל לקבל הן – 2+3+5+2-7 = 5

לבסוף, נשאר השלב הקריטי ביותר שאף רקורסיה לא שלמה בלעדיו – תנאי העצירה.
באיזשהו שלב נרצה להגיע למקרה הבסיס שלנו שמחזיר תוצאה בלי לקרוא לקריאה רקורסיבית נוספת. מקרה הבסיס שלנו הפעם הוא כמובן מערך ריק – במקרה כזה שחקן תמיד יקבל 0 נקודות.

נוסיף את מקרה הבסיס לפונצקיה שלנו ונבדוק – 

def maxScorePlayer(arr, player):
	if len(arr) == 0:
		return 0
	sumTotal = sum(arr)
	if player == ‘p1’:
		p2TakeLeft = maxScorePlayer(arr[1:], ‘p2’)
		p2TakeRight = maxScorePlayer(arr[:-1], ‘p2’)
		return max(sumTotal - p2TakeLeft, sumTotal - p2TakeRight)
	
else:
	p1TakeLeft = maxScorePlayer1(arr[1:], ‘p1’)
	p1TakeRight = maxScorePlayer1(arr[:-1], ‘p1’)
	return max(sumTotal - p1TakeLeft, sumTotal - p1TakeRight)

להלן טבלת המהלכים – 

אכן קיבלנו את התוצאה הנכונה!

עצירה מתודית קטנה להודעה חשובה!
אתן יודעות שבמשך כל השנים שכתבתי את הבלוג תמיד תמיד הייתי כותבת לבד את ההרצות? זה לקח נצח ודרש כל כך הרבה עבודה.
היום, כיוון שהטכנולוגיה קיימת, השתמשתי ב-chat gpt בשביל לג׳נרט את הטבלה להלן. בהרצה הראשונה הוא הריץ את הפונקציה לא נכון, שזו תזכורת טובה לכך שתמיד צריך לבדוק את התוצאות שלו ולא פשוט לסמוך עליהן. אבל בהרצה השנייה קיבלתי טבלה נוחה לבלוג בלחיצת כפתור. איזה כיף ושימושי.

הזיכרון

אוקי, מעולה, עכשיו יש לנו פונקציה עובדת, אבל מאוד כבדה ולא יעילה. פה נכנס השלב השני – ממואיזציה. בבעיות של תכנות דינאמי אנחנו נעבוד בצורה של הרצת כל (או רוב) האפשרויות ולאחריה תעדוף האפשרויות הטובות ביותר. בשרשרת האפשרויות האלו תמיד יהיו לנו מצבים שחוזרים על עצמם.

למשל, בעבור המערך – [2, 5, 3, 2], המצב [3,5] יכול לחזור כמה פעמיים – אם השחקן הראשון לוקח את הערימה השמאלית והשני את הימנית ולהיפך. ככל שהקלט שלנו גדול יותר יהיו יותר מצבים כאלה שחוזרים על עצמם. מכיוון שכל חישוב כזה דורש הרצה רקורסיבית של כל תת האפשרויות, נחסוך המון ריצות אם נאחסן את כל התשובות בזיכרון מקומי.
בואו נוסיף זיכרון לפונקציה שלנו.

שימו לב שכדי להימנע מאחסון המערך כולו בזיכרון עברתי להשתמש באינדקסים start, end לציון החלק במערך שאני עובדת עליו, אבל שאר הלוגיקה לא השתנתה.
עוד ייעול פשוט שהוספתי הוא חישוב הסכום פעם אחת והעברתו מקריאה לקריאה, במקום חישוב בכל קריאה בעלות o(n).

Class StonesGame:
	self.scoresMemo = {}

	def maxScorePlayer(arr, start, end, player):
		if start>end:
			return 0
		if (start, end, player) in scoresMemo:
			return scoresMemo[(start, end, player)]

		if player == ‘p1’:
			p2TakeLeft = maxScorePlayer(arr, start+1, end, ‘p2’, sumTotal-arr[start])
			p2TakeRight = maxScorePlayer(arr, start, end-1, ‘p2’, sumTotal-arr[end])
			scoresMemo[(start, end, player)] = max(sumTotal - p2TakeLeft, sumTotal - p2TakeRight)
	
		else:
			p1TakeLeft = maxScorePlayer1(arr, start+1, end, ‘p1’, sumTotal-arr[start])
			p1TakeRight = maxScorePlayer1(arr, start, end-1, ‘p1’, sumTotal-arr[end])
			scoresMemo[(start, end, player)] = max(sumTotal - p1TakeLeft, sumTotal - p1TakeRight)

		return scoresMemo[(start, end, player)]

def playGame(arr):
		sumTotal = sum(arr)
	return maxScorePlayer(arr, 0, len(arr)-1, ‘p1’, sumTotal)

עכשיו התוצאות שלנו תמיד תהיינה מאוחסנות בזיכרון ולא נצטרך לחזור על חישובים בצורה לא יעילה. כל פעם שנגיע לחלק במערך שכבר חישבנו בעבורו את התוצאה הרקורסיבית נוכל לשלוף את התוצאה מהזכרון.

עד לפה השאלה הזו, מקווה שהצלחתי לגרום לנושא המפחיד של תכנות דינאמי להיראות יותר פשוט עם פונקציה קצת יותר קריאה.