בשבוע האחרון של מאי 2006 התנהלה בטורינו (איטליה) אולימפיאדה שבה לא עלה שום זוכה על דוכן המנצחים, ושמעט מאוד אנשים ידעו עליה. זו היתה האולימפיאדה ה-11 למחשבים, שבה התחרו תוכנות מחשב בביליארד, שש-בש, גו, דמקה ומשחקים אחרים. באותו זמן ובאותו מקום התנהלה גם אליפות העולם ה-14 לתוכנות שחמט, וגם אולימפיאדת השחמט ה-37 לבני-אדם, שבה הגיעה הקבוצה הישראלית למקום הרביעי מבין 148 קבוצות. באליפות תוכנות השחמט החזירה לעצמה תוכנת ג'וניור, שפיתחו הישראלים שי בושינסקי (Bushinsky) ואמיר באן (Ban; ראו "לשחק כמו מכונה", "גליליאו" 74), את הכתר העולמי.
במשחקים רבים, ובהם משחק השחמט, אין שום מקום למקריות: תוצאת המשחק נובעת אך ורק מהחלטות שני השחקנים. אם יש מקום כלשהו לטענה של "מזל", יהיו טענות כאלה פנימיות לשחקן (מצב רוח, ריכוז, בריאות וכו').
במשחקים אחרים קיים אלמנט חיצוני של "מזל": הדבר ברור לגבי משחקי קובייה וקלפים, אך נכון במידה מסוימת גם לכל משחק שבו התוצאה תלויה בתהליך פיזיקלי כלשהו. לדוגמה, במשחק הביליארד, גם השחקן הטוב ביותר אינו יכול לדעת בביטחון היכן יהיה כל כדור לאחר שיכה בכדור הראשון, כדור זה יפגע בכדורים אחרים וכו'.
תנועת הכדורים מושפעת מגורמים כה רבים, הכוללים לא רק את עוצמת החבטה הראשונה וכיוונה אלא גם פרטים מיקרוסקופיים בשולחן ובכדורים, טמפרטורה, לחות וכו', עד שעלינו להתייחס לתוצאה הסופית כמצב הניתן לחיזוי מראש רק בחלקו, אך בחלקו נקבע בצורה אקראית. אפילו הבדלים קטנים עשויים להיות לפעמים חשובים מאוד: הם עשויים לקבוע, למשל, אם כדור יגיע אל אחד ה"כיסים" שבפינות השולחן ובדופנותיו.
גם השחקן הטוב ביותר אינו יודע בביטחון היכן יהיה כל כדור לאחר שיכה
אילוסטרציה: sxc.hu
ביליארד ממוחשב
קיימים רובוטים המשחקים ביליארד. שמו של אחד מהם, "ירוק עמוק" (קישור בסוף הכתבה), רומז לתוכנת השחמט המפורסמת "כחול עמוק", הנחשבת מיושנת כיום, אך זכתה לתהילת עולם כשניצחה ב-1997 את אלוף העולם גארי קספרוב. כאן הוחלף הצבע הכחול המסמל את IBM, מפתחת "כחול עמוק", בצבע הירוק של שולחן הביליארד. "ירוק עמוק" מצליח אפילו בביצוע חבטות קשות במיוחד, אך כמו רובוטי-ביליארד אחרים הוא אינו בנוי לתכנון אסטרטגי.
לעומת זאת, קיימות כמה תוכנות המשחקות ביליארד וירטואלי: משחק שכולו מתרחש בהדמיה ממוחשבת של שולחן המשחק והכדורים שעליו. תוכנות אלו מנסות לתכנן את מהלכיהן כך שייתנו לעצמן הזדמנות טובה להמשך, בעוד שאפשרויותיו של היריב יהיו מוגבלות ככל האפשר.
באולימפיאדת המחשבים בטורינו התחרו חמש תוכנות "ביליארד וירטואלי" כאלה. מתוך הסוגים הרבים של ביליארד, נבחר המשחק "eight-ball pool". הזוכה היתה תוכנת PickPocket ("כייס"), שיצרה אחת מקבוצות המחקר החזקות ביותר בתחום תוכנות המשחק: קבוצת הבינה המלאכותית למשחקים של אוניברסיטת אלברטה בקנדה (קישור בסוף הכתבה).
קבוצה זו פיתחה, בין השאר, את התוכנה שניצחה את אלוף העולם בדמקה ומתקרבת לפתרון מלא של משחק זה (מציאת המהלך הנכון בכל מצב אפשרי). זוהי השנה השנייה שבה "הכייס" מנצחת באולימפיאדת המחשבים.
מכיוון שהמשחק מתרחש בסביבה וירטואלית, יש צורך להחליט על רמת האקראיות: ללא אקראיות, יפעילו התוכנות מהלכים שאינם אפשריים כלל על שולחן אמיתי מכיוון שהם דורשים דיוק מוחלט של המכה עצמה, הכדורים, השולחן וכו' (למשל: כדור הפוגע בצד השולחן, ניתז ממנו ופוגע בכדור אחר, כך ששניהם ממשיכים לנוע ולהניע כדורים אחרים בסדרה ארוכה של התנגשויות, עד שהתנועה נעצרת במצב הנוח לשחקן המכה). ייתכן כי מהלכים "סופר-מדויקים" כאלה גם מאפשרים תמיד ניצחון לצד המתחיל, ללא העברת התור לשחקן האחר, ובכך מסלקים כל אלמנט של תחרותיות מהמשחק.
רמת האקראיות שנבחרה עבור האולימפיאדה גבוהה יחסית, ומייצגת את יכולת הדיוק של חובב מוכשר. ברמה זו, כמעט כל החבטות הפשוטות (הכדור הנחבט פוגע בכדור המטרה ומכניס אותו לכיס) והקצרות יצליחו, אך חלק מהחבטות הפשוטות הארוכות (הכדורים צריכים לעבור מרחק גדול, אף שהמסלול עצמו פשוט) ייכשלו, וקיים רק סיכוי נמוך להצלחה בחבטות מורכבות (הכדור הנחבט ו/או כדור המטרה פוגעים בכדורים אחרים ובדופנות השולחן כדי להגיע להכנסת כדור המטרה לכיס). מטרת בחירה זו היא להדגיש את האתגר של אסטרטגיה במצבי אי-ודאות.
אסטרטגיות ביליארד
אפשר לראות את משחק הביליארד כדומה למשחקים אחרים שבהם כל שחקן משחק בתורו (בניגוד לכדורגל, למשל, שבו היריבים פעילים בו-בזמן). בתורת המשחקים מקובל לנתח משחקים כאלה כ"עץ של מצבים": מהמצב הנתון, השחקן יכול לבחור בכמה אפשרויות. כל אפשרות כזו תביא למצב אחר של המשחק. בכל מצב כזה יש לבדוק את האפשרויות של השחקן שעכשיו הגיע תורו (בביליארד, חלק מהאפשרויות יביאו למצב שבו יוכל השחקן לשחק שוב, וחלק, שבהן לא הוכנס הכדור הנכון לכיס, יגרמו למעבר התור לשחקן היריב).
אם נראה את המצב הנוכחי כשורש של עץ, וכל אפשרות כענף ראשי של העץ, סופו של כל ענף כזה מייצג את מצב הלוח שאותה אפשרות תיצור בסוף תנועת הכדורים. מכל "סוף ענף" נוכל ליצור ענפים חדשים עבור האפשרויות השונות של המשך המשחק, וכן הלאה.
גישה זו מקובלת בשחמט, בדמקה וכו', אך נתקלת בשני סוגים של קשיים בביליארד: ראשית, בניגוד לשחמט, למשל, שבו יש לכל היותר כמה עשרות מסעים אפשריים בכל עמדה, בביליארד קיים מספר בלתי מוגבל של אפשרויות לבחירת מיקום המוט, כיוונו ומהירותו. שנית, יש להביא בחשבון את האקראיות, הגורמת לכך שגם לאחר שבחרנו בדיוק רב את כל המספרים המגדירים את החבטה, מצב הלוח בעקבות חבטה זו אינו ניתן לניבוי מדויק.
מייקל סמית (Smith), מאוניברסיטת אלברטה בקנדה, המפתח הראשי של PickPocket, מתאר את גישתו לבעיות אלה במאמר שהוצג בחודש יולי 2006 בכנס האיגוד האמריקני לבינה מלאכותית (AAAI). קודם כל, עליו להקטין את מספר האפשרויות שבוחנת התוכנה. ראשית, התוכנה מחפשת חבטות פשוטות (הכדור הנחבט פוגע בכדור המטרה ומכניס אותו לכיס) על-ידי חישוב גאומטרי-פיזיקלי. גם עבור חבטה כזו, חשוב לדעת היכן יהיה הכדור הנחבט בסיום התנועה, ואם יפגע בכדורים אחרים ויזיז אותם.
לכן, עבור כל חבטה כזו, התוכנה תציע כמה אפשרויות של מהירויות חבטה שונות וזוויות פגיעה שונות. אם לא נמצאה חבטה פשוטה, התוכנה תמשיך ותחפש סוגים אחרים. אחד מסוגים אלה הוא חבטה שאינה מצליחה להכניס כדור לכיס כנדרש בחוקי המשחק, ולכן מעבירה את התור לשחקן היריב, אך משאירה את הלוח במצב שבו קשה מאוד לשחקן היריב לבצע חבטה חוקית (חבטה שתשאיר בידיו את התור).
לצורך חיפוש חבטות כאלה, התוכנה מנסה צירופים שונים של כיוונים ומהירויות ובוחנת את מצב הלוח לאחר כל צירוף כזה, כשהיא מנסה למצוא מצב שבו חופש הפעולה של היריב הוא המוגבל ביותר. למעשה, כדי לקחת בחשבון את האקראיות, התוכנה מחשבת כמה פעמים את המצב שייווצר בעקבות החבטה, ובודקת את התפלגות התוצאות של החישוב (החישוב מביא בחשבון אקראיות ולכן מפיק תוצאות שונות בכל פעם, אף שהחבטה נשארת זהה).
הכותב עובד בחברת ClickSoftware בפיתוח שיטות אופטימיזציה מתקדמות.