Alchemize AI – איך בניתי שחקן מחשב עבור משחק לוח דיגיטלי

מאת: אורי ברוסילובסקי

באוגוסט 2018 סתיו גולדשטיין ויקיר בונקר השתתפו בג’אם האינטרנטי Ludum Dare, בנושא Running Out of Space, במהלכו הם בנו את המשחק Alchemize.
Alchemize הוא משחק לוח אסטרטגי לשני שחקנים, בסגנון משחקים כמו רברסי והקסגון. גם אני השתתפתי בג’אם באותה שנה, ויצא לי בשלב הדירוג לשחק ב-Alchemize. המשחק נראה מרשים וכיפי, וקיבלתי את הרושם שיש בו הרבה עומק, ובעיקר הופתעתי מהעובדה שמדובר במשחק עם חוקים חדשים לגמרי שהם פיתחו מאפס ב-72 השעות של הג’אם! אבל היתה רק בעיה אחת – זה היה משחק לשני שחקנים, ואני הייתי רק שחקן אחד.

באותו רגע חשבתי לעצמי “לשחק נגד מחשב יכול היה להיות נחמד” והמשכתי בחיי…

אבל כעבור שנה וחצי, אחרי ששוב השתתפנו בג’אם Ludum Dare (והפעם סתיו, יקיר ואני שיתפנו פעולה ובנינו משחק ביחד), שוב עלה הרעיון – מה עם Alchemize? לא חבל שרעיון כזה מגניב יהיה מוגבל רק לשני שחקנים על אותו המחשב?

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

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

חוקי המשחק

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

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

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

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

החוקים הבסיסיים האלה יצרו משחק מתוחכם ועמוק (ושאפו לסתיו ויקיר שהמציאו את המשחק הזה לגמרי מאפס בזמן הג’אם!). בכל תור, השחקן צריך לחשוב על השיקולים הבאים:

  • האם השיקוי שלי ייצור קריסטלים?
  • האם היריב יוכל לנצל את השיקוי שלי כדי ליצור קריסטלים בצבע שלו?
  • האם אני יכול להשמיד קריסטלים של היריב?
  • האם אני יכול לחסום את היריב מלהשמיד את הקריסטלים שלי?

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

כתיבת שחקן המחשב

מבוא לאינטלגנציה מלאכותית למשחקי לוח

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

עבור משחקים קצרים (כמו איקס עיגול), המחשב יכול לחשב את כל המהלכים האפשריים במשחק, וכך ליצור שחקן מושלם, שאמנם טוב במשחק אבל לא מאוד כיף לשחק נגדו. לעומת זאת, עבור משקים ארוכים יותר עם הרבה מהלכים אפשריים בכל תור, מספר החישובים הנדרשים גדל כל כך שזה כבר בלתי אפשרי. למשל בשח יש בממוצע 20 מהלכים כל תור. מה שאומר שכדי לחזות 2 מהלכים לעתיד צריך לחשב 400 מהלכים; כדי לחזות 5 מהלכים צריך יותר מ-3 מיליון מהלכים, וכדי לחזות 7 מהלכים צריך יותר ממיליארד!

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

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

אתאר את היוריסטיקה שבחרתי עבור אלכמייז.

היוריסטיקה

התחלתי עם היוריסטיקה הבאה:

[מספר הקריסטלים בצבע שלך] פחות [מספר הקריסטלים של היריב]

היוריסטיקה בפשטות מנסה להגיע למצב שיש לך כמה שיותר קריסטלים, וליריב כמה שפחות, על ידי מיקסום ההפרש. למשל, היא תעדיף לוח שבו לך יש 5 קריסטלים וליריב 2 (הערך הוא 3), לעומת לוח שבו לך יש 10 קריסטלים וליריב 9 (הערך הוא 1). וכמובן ששניהם עדיפים על לוח שבו ליריב יש יותר קריסטלים ממה שיש לך (ערך שלילי).

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

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

ניסיון 1 - יוריסטיקה פשוטה, עומק שונה

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

  1. קל – יוריסטיקה פשוטה, עומק 1
  2. בינוני – יוריסטיקה פשוטה, עומק 2
  3. קשה- יוריסטיקה פשוטה, עומק 3
  4. מטורף – יוריסטיקה פשוטה, עומק 4

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

 

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

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

היו רק שתי בעיות:

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

ניסיון 2 - יוריסטיקה מתקדמת - "קריסטלים חסומים"

המטרה ב-Alchemize היא ליצור כמה שיותר קריסטלים. אבל לא פחות חשוב, עליך להשמיד גם את הקריסטלים של היריב! מאוד נפוץ שבסוף משחק, נשארים מעט מאוד קריסטלים על הלוח. קחו למשל את הלוח האופייני הבאף שבו לכל שחקן יש רק 2 קריסטלים:

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

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

 

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

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

אז שיפרתי את היוריסטיקה:

100 כפול [ההפרש בין הקריסטלים החסומים שלך לאלה של היריב] + [ההפרש בין כל הקריסטלים שלך לאלה של היריב]

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

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

  1. קל – יוריסטיקה בסיסית, עומק 1
  2. בינוני – יוריסטיקה בסיסית, עומק 2
  3. קשה – יוריסטיקת קריסטלים חסומים, עומק 2
  4. מטורף – קריסטלים חסומים, עומק 3

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

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

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

וכך הוצאנו את המשחק – עם עדכון קטן:

ניסיון 3 - שחקן קל עם אקראיות

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

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

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

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

  1. קל – יוריסטיקה פשוטה עם אקראיות, עומק 1
  2. בינוני – יוריסטיקה פשוטה, עומק 2
  3. קשה – קריסטלים מאובטחים, עומק 2
  4. מטורף – קריסטלים מאובטחים, עומק

עוד אפשרויות שלא נכנסו למשחק

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

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

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

אשמח לשמוע מה חשבתם על הפוסט!

אורי ברוסילובסקי

Alchemize

עוד משחקים שלי.

הטוויטר שלי

כתיבת תגובה

האימייל לא יוצג באתר.