בתשובה לאביב י., 26/04/08 23:20
אפרופו 476744
אני מסתייג מטענתך ש minimax הוא אלגוריתם לא ממש טריויאלי.
לדעתי אם תמצא ילד בן שבע שמשחק שח באופן סביר, ותשאל אותו איך הוא עושה את זה, ותבקש ממנו לפרט (תשאל "מה זאת אומרת חושב קדימה?") אז הוא יתאר בפניך את האלגוריתם. אז אולי הוא לא יכתוב לך אותו בשפת תכנות אבל הוא מבין אותו באופן אינטואיטיבי.

לגבי alpha-beta, חפש מישהו שמשחק שח די טוב, אבל מבלי שלמד בחוג שח (או מספר) על פתיחות, סיום, עקרונות, טריקים, וכו', וסביר שאם תגרום לו לתאר לך את תהליך המחשבה שלו תגלה שהוא אפילו משתמש ב alpha-beta, גם אם הוא לא יודע מה זה והוא לא חושב שהוא אי פעם ממש חשב על זה.
בנוסף, לפי הויקיפדיה ( http://en.wikipedia.org/wiki/Alpha-beta_pruning ) נראה ש alpha-beta הומצא פעמים רבות באופן בלתי תלוי.
ובנוסף, ציטוט מפי ג'ון מקרתי, חתן פרס טורינג ( http://www-formal.stanford.edu/jmc/slides/wrong/wron... ):
alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers .... We humans are not very good at identifying the heuristics we ourselves use.
אפרופו 476766
אני לא מסכים.

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

"גם אם הוא לא יודע מה זה והוא לא חושב שהוא אי פעם ממש חשב על זה"

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

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

אל תבין אותי לא נכון: אני לא אומר משהו נגד הילד בן ה-‏15 שפתח ספר וקרא ולמד משהו על אלגוריתמים בבינה מלאכותית (בדיוק להיפך). אין ספק שזה ילד חכם ומוצלח. אבל ילדים שלומדים משהו מספרים זה סיפור עם קצת פחות זוהר מהמיתוס הנ"ל (משום מה). אני גם לא טוען שאין ילדים נדירים ומוכשרים במיוחד שהצליחו להגיע אל אלגוריתמים קלאסיים לגמרי בכוחות עצמם.
אפרופו 476822
ככל שאני מצליח להבין, אנחנו בדו-קרב של אינטואיציות; האינטואיציה שלי היא כמו של יאיר (בנוגע למינימקס; גיזום אלפא-ביתא הוא סיפור אחר). נדמה לי שאתה אולי מדמיין לא נכון את התהליך: הילד לא חושב על האלגוריתם באופן אבסטרקטי, אלא משפר את התוכנה שלו באופן איטרטיבי. הוא יתחיל אולי באמת מכתיבה של תוכנית שבוחרת אקראית של המהלך, אבל באופן מיידי ממש, בלי צורך בשום גאונות, יגיע לרעיון של העדפה, במהלך הקרוב, למהלכים של הכאת כלי יריב, ואז להעדפת הכאה של כלים "שווים". כשהוא יחשוב איך אפשר לשפר הלאה, *כמעט לא תהיה לו ברירה* אלא לחשב את המהלך הכי טוב של היריב בסיבוב הבא; וגו'. בכל שלב כזה כבר יש לו ביד תוכנית שרצה ועושה את השלב הקודם, ושהוא מכיר באופן אינטימי, וזה בהחלט עוזר להתמקד. במילים אחרות: לא מדובר בתרגום מהבנה אינטואיטיבית להבנה מכניסטית, וממנה לשפת תכנות, אלא בתרגום מהבנה אינטואיטיבית ישירות לשפת תכנות, ואז הכללה להבנה מכניסטית מופשטת. השלב השני הוא אופציונלי, ואןלי שמור באמת לגאונים שבחבורה.

(וידוי: לכל צורך ועניין לא התנסיתי בתכנות, ובקושי בשימוש במחשבים בכלל, לפני הצבא. עכשיו הייתי צריך לשאול את הדוד מה זה הדמוסצנה הזאת שלך.)
אפרופו 476833
עם מינימקס נטו אני עוד עלול להשתכנע, אבל עם גיזום אלפא-ביתא נראה לי שכבר צריך להיות אחרי השלב השני, לדמיין בראש את העץ ולהגיע לתובנה שאפשר לגזום ענפים מיותרים.
ארקפה‏1 476838
זה המקום להכניס קצת אמפריציזם‏2 לויכוח. מישהו שמע על נער שכתב תוכנית שח סבירה? תוכנית שח בכלל? דמקה? שש בש?

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

מלבד הידע הנחוץ, תכנות הוא עיסוק שדורש דחיית סיפוקים והתמודדות עם תסכולים, שני מאפיינים שהופכים אותו לבלתי אטרקטיבי בעליל עבור נערים ונערות.
____________
1- די עם הפרסומת הסמויה, כאן זה לא "השרדות".
21- לא, זה המקום להכניס קצת מלים לועזיות לויכוח.
ארקפה‏1 476842
נערים שכותבים תוכנית שח סבירה זה בגדר האפשר (גם אם לא נפוץ במיוחד). נערים שעושים זאת מבלי להשתמש ברעיונות קיימים עליהם הם קראו באינטרנט, בספרים או באמצעות ידע מפה לאוזן, זה כבר סיפור אחר.

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

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

alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers .... We humans are not very good at identifying the heuristics we ourselves use.

חזרה לעמוד הראשי המאמר המלא

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