פורסם ב זה רק קוד, מתכוננות לראיונות

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

קוד: main.py
זמן קריאה: 7 דקות

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

Not today!

אוקי, אז חשבתי לעצמי שיהיה מגניב לתכנת איזשהו משחק קטן ופשוט ולכתוב לו 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(n2) – לא כיף.

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

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}

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

choose-between-options
למה לבחור בנורה כבויה כשאפשר לבחור בנורה דולקת?

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

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 בעתיד.

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

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

6 תגובות בנושא “מימוש משחק בול פגיעה חלק א׳ – לוגיקה

  1. גם אני הייתי משחק את המשחק הזה כשהייתי קטן. לגבי הקוד שלך, לדעתי אפשר לצמצם אותו משמעותית בלי לפגוע בפונקציונליות
    https://colab.research.google.com/drive/1Ub2bH4oNNwJqvksNmBHrc0IBGgXS_ut8?usp=sharing
    לגבי האופטימיזציות, חז"ל אמרו:
    premature optimization is the root of all evil
    לא בטוח שהגישה שלך חוסכת זמן ריצה, לא בטוח שזה צוואר הבקבוק, ובכל מקרה צריך לעבוד עם פרופיילר כדי לבדוק שינויים בביצועים
    אני השתמשתי בbullseye ו-hits במקום בbul pgia

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

  2. כתיבה מצויינת ומעניינת (כרגיל).
    אני לא שיחקתי בול-פגיעה בילדותי, אבל כן שיחקתי סנייק (למשל בפלאפונים הישנים של נוקיה).
    כבר הרבה שנים שכל פעם שאני לומד שפת תכנות חדשה, אני מאתגר את עצמי לתכנת סנייק בשפה הזאת (כתבתי סנייק אפילו במאטלאב ובג'אווהסקריפט עם CSS).
    אני חושב שהמטרה בלתכנת סנייק שונה מהמטרה בלתכנת בול פגיעה, בעיקר כי סנייק כן דורש GUI מסויים, וגם המשחק ימשיך לרוץ גם אם אין אינפוט של השחקנית. לכן זה יכול להיות מאתגר יותר (וגם כי לכל שפה יש לוגיקה אחרת שיעילה יותר למימוש). אבל, התוצאה יותר מהנה (לדעתי לפחות).
    בכל מקרה, גם תכנתתי סנייק בפייתון וכשחיפשתי ספריית GUI נוחה, מצאתי את pygame שמבוססת על SDL של C. יכול להיות שיהיה לך יותר נוח להשתמש בספרייה הזאת מאשר ב-tkinter, אבל אני לא בטוח אם זה ישרת את מטרת הפוסט.

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

  3. משהו מוזר לי בלוגיקה של ״פגיעה״. אם הניחוש הוא אדום-אדום-אדום-ירוק, ויש אדום אחד בתשובה האמיתית, אז את מחשבת אותו כ־3 פגיעות?

השאר תגובה