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

איך מממשות ארבע בשורה?

בגדול יש שני חלקים למימוש משחק ארבע בשורה: 

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

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

מה המכניקה של ארבע בשורה?

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

אלו האובייקטים של המשחק שנרצה לממש:

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

המכניקות שנרצה לממש:

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

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

הוספת דיסקית

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

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

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

• צבע של השחקן הנוכחי.
• אובייקט לוח, שבכל תא שלו אחד משלושה צבעים Red, Blue או Empty שיסמן תא ריק.
• מספר עמודה אליה נרצה להוסיף דסקית.

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

יאללה, אפשר לממש – 

def add_disc(current_color, board, column):
    row = 0
    success = False
    while row < 6 and not success:
        if board.get(row, column) is Color.EMPTY:
            board.set(row, column, current_color)
            success = True
        else:
            row += 1
    return success

האלגוריתם מאוד פשוט. 

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

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

זיהוי ניצחון

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

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

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

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

def four_sequence_exists(discs_vector):
    longest_seq = 1
    current_seq = 1
    for i in range(1, len(discs_vector)):
        if discs_vector[i] == discs_vector[i - 1] and not (discs_vector[i] is Color.EMPTY.value):
            current_seq += 1
        if current_seq > longest_seq:
            longest_seq = current_seq
        else:
            current_seq = 1
    return longest_seq == 4

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

1. ראשית, זה נראה קצת מוזר שאני לא בודקת רצף מצבע מסוים, לא? הרי אם השחקנית האחרונה ששיחקה שמה דיסקית כחולה, אני לא רוצה להחזיר ניצחון על רצף של דסקיות אדומות.
   הסיבה שאני יכולה להתעלם מהצבע הוא שאני מריצה את אלגוריתם הניצחון אחרי כל מהלך. כלומר, אם בוקטור הספציפי הזה קיימת רביעיה אדומה היא הייתה מתגלה בסיבוב שבו התווספה הדסקית שיצרה את הרצף.
   המחיר של זה הוא שאני נאלצת לבדוק שאני לא בטעות מוצאת רצף של תאים ריקים (בשורה 4). אז אפשר להגיד ששני המימושים די שקולים.
2. כדי לבדוק אם אני נמצאת ברצף אני רוצה תמיד לבדוק אם הדסקית הנוכחית תואמת בצבע לדסקית הקודמת. כדי שאני לא אצטרך להוסיף התייחסות מיוחדת לדסקית הראשונה, וכיוון שהצבע לא משנה לי (כפי שהסברתי בסעיף הקודם), אני פשוט מדלגת על הדיסקית הראשונה. אני מתייחסת אליה כרצף באורך 1.
3. אני תמיד מאתחלת את המשתנה current_seq שלי להיות באורך 1. זאת, למרות שאורך 0 נשמע אינטואיטיבית יותר הגיוני. הסיבה לכך היא שאני בודקת רצפים ״אחורה״. כלומר – בעבור כל דסקית אני בודקת אם היא מתחברת לרצף הקודם, אם כן, הוא מתארך, אם לא, היא מתחילה רצף חדש באורך 1.
   אם הייתי בודקת ״קדימה״ – רק דסקית עם צבע תואם הייתה מתחילה רצף חדש, ואז הייתי בוחרת לאתחל את current_seq להיות 0.

איסוף וקטורים

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

כזכור, לוח המשחק שלנו הוא מטריצה בגודל 6X9, אנחנו נרצה להתחשב בגבולות האלה כשאנחנו מחלצות וקטורים.
לדוגמא, אם דסקית הונחה בפינת המטריצה, במיקום (0,0) אני לא אוכל להחזיר וקטור באורך 7 שהיא נמצאת במרכזו. יהיו לי רק שלושה וקטורים באורך 4 שהיא נמצא בקצה אחד שלהם.

איך יודעות מהי נקודות ההתחלה של הוקטור? כדי למצוא את נקודת ההתחלה של הוקטור נחשב את המקסימום בין נקודת ההתחלה שאנחנו מחפשות – שלוש מקומות ״לפני״ המיקום הנוכחי – לבין נקודת ההתחלה האפשרית – שורה/עמודה 0.
אותו הדבר נכון גם לגבי נקודת הסיום של הוקטור – דמיינו שהדסקית הונחה במיקום (6,9), נקבל את אותה הבעיה רק הפוך. כדי לא לחרוג מגבולות הלוח נרצה שנקודת הסיום שלנו תהיה המינימום בין נקודת הסיום הרצויה – שלוש דסקיות ״אחרי״ המיקום הנוכחי – לבין נקודת הסיום האפשרית – שורה 6/ עמודה 9.

נתחיל מלכתוב אלגוריתם שמקבל מיקום של דסקית ולוח, ומחזיר את הוקטור של השורה –

    def get_row_vector(board, row, column):
        start = max(0, column - 3)
        end = min(8, column + 3)
        vector = []
        for c in range(start, end + 1):
            vector.append(board.get(row, c))
        return vector

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

    def get_column_vector(board, row, column):
        start = max(0, row - 3)
        end = min(5, row + 3)
        vector = []
        for r in range(start, end + 1):
            vector.append(board.get(r, column))
        return vector

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

    def get_diagonal_vector(board, row, column):
        start_row = max(0, row - 3)
        start_column = max(0, column - 3)

        end_row = min(5, row + 3)
        end_column = min(8, column + 3)
        vector = []

        r = start_row
        c = start_column
        while r <= end_row and c <= end_column:
            vector.append(board.get(r, c))
            r += 1
            c += 1
        return vector

בדיקת ניצחון

עכשיו, כל מה שצריך כדי לבדוק ניצחון זה –

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

def is_win(board, row, column):
	possible_vectors = [get_row_vector(board, row, column), get_column_vector(board, row, column), get_diagonal_vector(board, row, column)]
	for discs_vector in possible_vectors:
		if four_sequence_exists(discs_vector):
			return True
	return False

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

תזכורת לסיבה שתמיד חשוב לכתוב טסטים!

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

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

[[1,  2,  0,  0,  2],
[2,  1,  0,  2,  2],
[1,  2,  1,  1,  2],
[2,  2,  1,  1,  1]] 

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

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

    def get_negative_diagonal_vector(board, row, column):
        start_row = min(5, row + 3)
        start_column = max(0, column - 3)

        end_row = max(0, row - 3)
        end_column = min(8, column + 3)
        vector = []

        r = start_row
        c = start_column
        while r >= end_row and c <= end_column:
            vector.append(board.get(r, c))
            r -= 1
            c += 1
        return vector

אוקי, נראה לי שזה עובד. איזה מזל שכתבתי טסטים!

זה הכל לפוסט הנוכחי, בהמשך אני ארצה לכתוב משחק CLI פשוט שמאפשר לשתי שחקניות לשחק, ואולי בעתיד, מי יודע, אפילו GUI 🙂

היי לכולן!

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