מימוש משחק בול פגיעה חלק א׳ – לוגיקה

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

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

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

אז בואו נתחיל!

התוכנית

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

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

מהלך המשחק הוא כזה – 

1. שחקנית אחת בוחרת רצף של ארבעה צבעים.
2. בכל תור, השחקנית השנייה מנסה לנחש את הרצף הנבחר. השחקנית הראשונה ״מנקדת״ לה את הניחוש – אומרת לה כמה בולים ופגיעות היו לה. 
   בול – הצבע הנכון במקום הנכון.
   פגיעה – הצבע הנכון במקום הלא נכון.
3. המשחק נגמר כשהשחקנית השנייה מנחשת את הרצף המדויק, או אחרי שנגמרו לה הניסיונות.

פשוט? פשוט!

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

האלגוריתם

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

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

האלגוריתם הוא פשוט מאוד ונראה כך –

colors = ["red", "blue", "green", "purple", "pink", "yellow"]

def generate_code():
	code = []	
	for i in range(0,4):
		code.append(random.choice(colors))
	return code

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

1. האם הצבע קיים בקוד?
2. האם הצבע קיים בקוד, ונמצא בדיוק באותו מקום שבו הוא נמצא בניחוש?

לפני שאני ניגשת למימוש של האלגוריתם, התנאים הנ״ל גרמו לי לשקול מחדש את המימוש של הקוד שהמחשב בחר ברשימה. את סעיף 2 קל לבדוק על רשימה בסיבוכיות o(1)- ניגשים לאינדקס המתאים בקוד, ורואים האם הצבע נמצא שם. 
מה לגבי סעיף 1? אם בעבור כל צבע בניחוש אני אבדוק האם הרשימה שמייצגת את הקוד מכילה את הצבע, הסיבוכיות שלי תהיה o(n²) – לא כיף.

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

def check_guess(code, code_set, guess):
	bul = 0
	pgia = 0
	for i in range(0,len(guess)):
		color = guess[i]
		if color == code[i]:
			bul += 1
		elif color in code_set:
			pgia += 1
	return bul, pgia

*אגב, שמות המשתנים bul ו-pgia הם נוראיים, אני יודעת. הרגישו חופשיות להציע שמות טובים יותר.

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

כלומר, אם הקוד שהוגרל היה – 

["blue”, “purple”, “green”, “pink”]

אז הייצוג שלו בטבלה יהיה – 

{"blue”:0, “purple”: 1, “green”: 2, “pink”: 3}

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

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

def get_player_guess():		
	guess = input("Please enter your next guess\n").split(" ")
	# Validate guess
	return guess

def play():
	computer_code = generate_code()
	computer_code_set = set(computer_code)
	
	game_won = False
	rounds = 0
	while not game_won and rounds < 12:
		player_guess = get_player_guess()
		bul, pgia = check_guess(computer_code, computer_code_set, player_guess)
		if bul == 4:
			game_won = True
			break
		else:
			print("Bul: {}, Pgia: {}\n".format(bul, pgia))
			rounds += 1
	if game_won:
		print("You win!")
	else:
		print("You lose!")

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

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

מקווה שנהניתן ואולי קיבלתן השראה גם לשבת ולכתוב משחק היום!

פוסטים נוספים בסדרת בול-פגיעה