ארימא

ארימא (Arimaa) הוא משחק לוח המיועד לשני שחקנים. כללי המשחק פשוטים מספיק להבנה על ידי ילדים מחד, ומאידך הם גורמים לקושי רב לתכנות מחשב. המשחק תוכנן על ידי עומר סייד (Omar Syed), מהנדס מחשבים המתמחה בבינה מלאכותית, בהשפעת תבוסתו של גארי קספרוב על ידי מחשב השח "כחול עמוק" (Deep Blue). לבנו של סייד, אאמיר (Aamir), שהיה באותה תקופה בן ארבע, הייתה השפעה רבה על פיתוח המשחק. שם המשחק "ארימא" בא מהיפוך "אמיר" והוספת "א" לתחילת השם.

ב-2002 פרסם סייד את חוקי המשחק והכריז על פרס של 10,000 דולר, אותו ניתן לקבל עד שנת 2020, לתכנת המחשב הראשונה שתצליח להביס שחקן אנושי בעל דרגה גבוהה בארימא בקרב בן שישה משחקים או יותר. דויד פוטלנד, המפתח של תוכנת הגו, Many Faces of Go, יצר בתחילת 2004 את תוכנת ארימא החזקה ביותר עד אז, רק כדי לראותה מובסת לחלוטין על ידי סייד עצמו, עם שמונה ניצחונות, אפס הפסדים ואף תיקו. בשנת 2015 זכה דויד וו בפרס כאשר תוכנת 'שארפ' שלו ניצחה את השחקנים האנושיים.

לוח ארימא
בארימא משחקים על לוח שחמט שעליו סומנו ארבע משבצות הנקראות משבצות מלכודת (trap squares) במיקומים ג3, ו3, ג6 ו-ו6.

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

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

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

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

התור צריך להסתיים בשינוי ממשי של מצב הלוח.

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

פעולות מיוחדות ומצבי כלים
להלן, כאשר מדובר על כלים צמודים, הכוונה היא לכלים בשתי משבצות צמודות זו לזו (האלכסון לא נחשב).
 דחייה ומשיכה (push and pull) - כל כלי יכול להניע ממקומו כלי של היריב דרך "דחיית" הכלי אל מחוץ למשבצת בה הוא נמצא או דרך "משיכתו" לתוך המשבצת בה נמצא כלי השחקן. בדחייה מוזז כלי היריב לתוך משבצת פנויה סמוכה ולאחר מכן כלי השחקן נכנס למשבצת שפונתה. במשיכה כלי השחקן זז לתוך משבצת פנויה סמוכה ולאחר מכן מוזז כלי היריב למשבצת בה כלי השחקן היה. לפעולות אלו חמישה כללים:
הפעולות ניתנות לביצוע רק בין כלי חזק לכלי חלש יותר. לדוגמה, כלב לא יוכל לדחות כלב אחר, וגם לא סוס, גמל או פיל. תוצאה של כלל זה היא שאת הפיל לא ניתן להניע ממקומו.
עלות הפעולות שני צעדים - אחד להזזת כלי השחקן ואחד להזזת כלי היריב.
לא ניתן לבצע דחייה ומשיכה באותה התנועה.
הפעולה חייבת להסתיים בתור בו התחילה.
לא ניתן להניע כלים אחרים של אותו השחקן (לדוגמה לצורך משיכת ארנבים או דחייתם אחורה).
 מלכודת (trap) - כלים שהגיעו למשבצת מלכודת נלכדים ומוצאים מיידית מהמשחק, אלא אם כן יש כלי חברותי (כלי מאותו הצבע) הצמוד למשבצת זו. אם כל הכלים החברותיים הצמודים למלכודת יתרחקו ממנה, הכלי שיימצא בה ילכד. צריך לשים לב שמשיכה המובילה את הכלי המושך לתוך מלכודת תושלם אפילו אם הכלי נלכד בצעד הראשון.
 קפאון (freeze) - כלי הצמוד לכלי יריב יותר חזק קופא, אלא אם כן יש כלי ידידותי הצמוד לו. כלי קפוא לא יכול להזיז כלי קפוא, אבל יכול בלי קשר לקפאון להקפיא כלים יריבים יותר חלשים ממנו. כמו בכללי דחייה ומשיכה את הפיל לא ניתן להקפיא, אבל ניתן לחסום אותו על ידי כלים המוקפים בכלים אחרים, כך שהפיל לא יוכל לדחות את הכלים הצמודים אליו.

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

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

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

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

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

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

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

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

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

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

קישורים חיצוניים

 
תוכנת ארימא של דויד פוטלנד

משחקי לוח
משחקי חשיבה