פתוח משחק שחמט
- פותח הנושא רפרנס
- פורסם בתאריך
נדמה לי שבשביל זה
צריך לעשות אלגוריתם כזה שבודק כל מהלך מה יהיו התוצאות האפשריות שלו ברקורסיה. כעיקרון התנאי יציאה אמור ליהיות כשלמלך של השחקן האנושי אין לאן ללכת כשהוא חייב ללכת (מצב של שח-מט). זה לא פשוט. הרקורסיה עצמה צריכה להתחשב בכל ההגבלות של משחק שחמט ובכל התנועות האפשריות של הכלים. אני מניח שזה גם יכול לגרום לעומס רב על המחשב ולכן חשוב לבדוק שהסיבוכיות לא תגרום לקריסה של התוכנית. אני מציע שתחפשי בגוגל דוגמאות קוד. אני בטוח שיש עשרות כאלה.
צריך לעשות אלגוריתם כזה שבודק כל מהלך מה יהיו התוצאות האפשריות שלו ברקורסיה. כעיקרון התנאי יציאה אמור ליהיות כשלמלך של השחקן האנושי אין לאן ללכת כשהוא חייב ללכת (מצב של שח-מט). זה לא פשוט. הרקורסיה עצמה צריכה להתחשב בכל ההגבלות של משחק שחמט ובכל התנועות האפשריות של הכלים. אני מניח שזה גם יכול לגרום לעומס רב על המחשב ולכן חשוב לבדוק שהסיבוכיות לא תגרום לקריסה של התוכנית. אני מציע שתחפשי בגוגל דוגמאות קוד. אני בטוח שיש עשרות כאלה.
זהרה מהר ירח
New member
מנסה
אני אתחיל בכך שהרעיון שלי הוא לא משהו שנוסה אי פעם בפועל, כי אין לי ניסיון בפיתוח משחקים שדורשים "בינה מלאכותי" (גם אם בינה מלאכותית פשוטה יחסית). בכל מקרה אני מציעה לך לעשות לולאות שבודקות בכל פעם כל מהלך. את יכולה לקחת מערך ולסרוק אותו כל פעם שוב ושוב ע" הלולאה, כך שהמחשב מקבל אינפורמציה איפה פנוי וניתן לשבץ את הכלי הנוכחי (לדוג' מלך, אבל זה יכול להיות כל כלי בעצם). כמובן שתתכנתי את הלולאה לעצור כאשר היא "נתקלת" במשהו, זה יכול להוריד מעט מהעומס על המחשב. את יכולה לעשות כמה רמות, כך שברמה הקלה המחשב ייקח באופן שרירותי את אחת האפשרויות מבלי לוודא עד כמה היא "כדאית" וברמה הקשה המחשב ייקח את האפשרות "הכי משתלמת" מבלי לעשות הנחות לשחקן. השאלה הגדולה היא, כמו שכתבו לפניי, האם זה לא יביא לקריסת התכנית משום שהמחשב לא יוכל להתמודד עם כ"כ הרבה לולאות שרצות בו זמנית. יש סיכוי שלא, כי מה שנראה לנו מסובך ודורש ים של פעולות ומיליון זמן, למחשב זה שום דבר שנעשה בכמה אלפיות שנייה, ויכול להיות גם אחרת. בכל מקרה אני אישית לא מכירה דרך יותר טובה, אבל נחכה למבינים ממני. בינתיים בהצלחה
אני אתחיל בכך שהרעיון שלי הוא לא משהו שנוסה אי פעם בפועל, כי אין לי ניסיון בפיתוח משחקים שדורשים "בינה מלאכותי" (גם אם בינה מלאכותית פשוטה יחסית). בכל מקרה אני מציעה לך לעשות לולאות שבודקות בכל פעם כל מהלך. את יכולה לקחת מערך ולסרוק אותו כל פעם שוב ושוב ע" הלולאה, כך שהמחשב מקבל אינפורמציה איפה פנוי וניתן לשבץ את הכלי הנוכחי (לדוג' מלך, אבל זה יכול להיות כל כלי בעצם). כמובן שתתכנתי את הלולאה לעצור כאשר היא "נתקלת" במשהו, זה יכול להוריד מעט מהעומס על המחשב. את יכולה לעשות כמה רמות, כך שברמה הקלה המחשב ייקח באופן שרירותי את אחת האפשרויות מבלי לוודא עד כמה היא "כדאית" וברמה הקשה המחשב ייקח את האפשרות "הכי משתלמת" מבלי לעשות הנחות לשחקן. השאלה הגדולה היא, כמו שכתבו לפניי, האם זה לא יביא לקריסת התכנית משום שהמחשב לא יוכל להתמודד עם כ"כ הרבה לולאות שרצות בו זמנית. יש סיכוי שלא, כי מה שנראה לנו מסובך ודורש ים של פעולות ומיליון זמן, למחשב זה שום דבר שנעשה בכמה אלפיות שנייה, ויכול להיות גם אחרת. בכל מקרה אני אישית לא מכירה דרך יותר טובה, אבל נחכה למבינים ממני. בינתיים בהצלחה
זה פתרון חלקי מדי
מכיוון שלפי התיאור שלך הוא ייתן לה את התוצאה הטובה ביותר למהלך הנוכחי בלבד. ככה השחקן האנושי יוכל בקלות לנצח כי המחשב יהיה פסיבי. הוא יגיב למצב הנוכחי של הכלים ולא יתכנן מהלכים עתידיים על סמך מהלכים אפשריים של השחקן. האלגוריתם לא חייב ליהיות בידיוק כמו שהצעתי, אבל הוא כן חייב לכלול איזה סוג של התחשבות גם במהלכים העתידיים של השחקן.
מכיוון שלפי התיאור שלך הוא ייתן לה את התוצאה הטובה ביותר למהלך הנוכחי בלבד. ככה השחקן האנושי יוכל בקלות לנצח כי המחשב יהיה פסיבי. הוא יגיב למצב הנוכחי של הכלים ולא יתכנן מהלכים עתידיים על סמך מהלכים אפשריים של השחקן. האלגוריתם לא חייב ליהיות בידיוק כמו שהצעתי, אבל הוא כן חייב לכלול איזה סוג של התחשבות גם במהלכים העתידיים של השחקן.
שחמט ממוחשב
התחום של בינה מלאכותית למשחקי לוח היה קפוא הרבה עשורים. השיפורים מדור לדור היו בעיקר הגדלת כוח החישוב של הפלטפורמות, ושיכלול השימוש בידע מומחה (ראי "פונקצית הערכה סטטית" בהמשך). כל האלגוריתמים התבססו (ועדיין מתבססים) על אותה השיטה, של קלוד שנון משנת 1950 [1]. בעשור האחרון לעומת זאת, רואים פריחה של שיטות ואלגוריתמים חדשניים. כנראה שהגיעו למסקנה שהוספת כח חישוב אולי טוב למשחקים כמו שחמט, אך למשחקים אחרים, אבסטרקטיים יותר זה לא מספיק. כעט אני אסביר אך האלגוריתם הקלאסי (זה של שנון) עובד. האלגוריתם הקלאסי הוא די פשוט ואף קל למימוש בגרסה הפשוטה שלו. בשביל יותר פרטים נסי לחפש Minimax באינטרנט. נתחיל מהגדרת הבעיה. נניח אנחנו משחקים בלבן. יש מולנו לוח עם עמדה מסוימת, והתור לשחק הוא שלנו [2]. אנחנו רוצים שמחשב יקבל את העמדה[3] הזאת ויחשב את המסע[4] הטוב ביותר שאנחנו יכולים לעשות במצב הנתון. בואו ניקח את הבעיה הזאת ונעבור לבעיה אחרת. במקום שהמחשב יחשב את המסע הטוב ביותר, כל מה שהוא יעשה זה להעריך למי יש יתרון במצב הנתון. צריך לחשב לא רק למי יש יתרון במצב נתון אלה גם לכמת את היתרון הזה, זאת אומרת שכל עמדה תקבל מספר (נניח בין 0 ל 100) שאומר כמה הלבן קרוב לנצחון. אם יש מט על הלוח ללבן (הלבן הפסיד) אז הערך יהיה 0, אם יש מט לשחור, אז הערך יהיה 100, בשאר המקרים הערך יהיה איפושהו בין 0 ל-100. המטרה שלנו היא לחשב את הפונקציה הזאת בצורה הכי מדויקת שאפשר. אני מקווה שכבר ברור שאם אנחנו יודעים לפתור את הבעיה השניה נוכל גם לפתור את הראשונה. נעשה זאת כך: מהעמדה הנתונה, המחשב יחשב את כל המסעים החוקיים. הוא יבצע כל מסע על הלוח נפרד ואז יחשב, בעזרת הבעיה הראשונה איזו מהעמדות שהתקבלו היא הכי טובה ללבן. זאת אומרת איזו עמדה היא בעלת הערך המקסימלי. המסע שהוביל לעמדה זו הוא המסע הכי טוב. ואיך פותרים את הבעיה השניה? נשתמש ברקורסיה! נניח שתורו של הלבן לשחק. המחשב יחשב את כל המסעים האפשריים של הלבן, ולכל עמדה שהתקבלה יחשב את ערכה (ברקורסיה). היות ותורו של הלבן, והלבן רוצה לנצח, הוא ישחק את המסע שמוביל לעמדה עם הערך המקסימאלי. כאשר בחישוב הרקורסיה מגיעים לעמדה שתורו של השחור לשחק, בוחרים את המסע שמוביל ללוח עם הערך המינימלי. בגלל זה קוראים לזה Minmax. התהליך דומה למה שמתרחב בראשו של שחקן אנושי, השחקן האנושי בודק אפשרויות: "אם אני אעשה כך, אז היריב יעשה כך ואז אני יעשה כך. אבל אם היריב ישחק כך אני אעשה כך" וכו... מהו תנאי העצירה של הרקורסיה? ניתן לטעון שתנאי העצירה הוא כאשר הגענו למצב בו יש מט לאחד הצדדים. האם זה פרקטי? בואו נבדוק. ניתן להסתכל על תהליך החישוב כעץ. המחשב צריך לעבור על כל העמדות שניתן ליצור מעמדה נתונה, ולכל אחת מהן לעבור על כל העמדות שהיא יוצרת וכו. ניתן לראות דוגמא של עץ חיפוש עבור איקס עיגול ב[קישור הבא]. נבדוק על כמה עמדות המחשב צריך לעבור. אם מעמדה נתונה ממוצעת יש 20 מסעים חוקיים, אז חישוב של מסע קדימה דורש מעבר על 20 לוחות. שני מסעים קדימה זה 20*20=400 שלושה מסעים קדימה זה 20*20*20 וכך הלאה. חישוב של 10 לוחות דורש מעבר על 1024 מיליארדי עמדות שעבור מחשב ביתי זה כבר מהווה בעיה. במשחק שחמט ממוצע של-120 מסעים לא ניתן לעבור על כל האפשרויות. במשחקים אחרים, ניתן לעבור על כל האפשרויות מהעמדה ההתחלתית, ולכן משחקים כאלו נחשבים ל"פתורים", זאת אומרת אם כל צד משחק הכי טוב שאפשר, ניתן לדעת עוד לפני שהתחיל המשחק מה תהיה התוצאה. ראינו שהרקורסיה לא יכולה להגיע עד לעלים של העץ ולכן היא צריכה לעצור לפני כן. בכל זאת צריך להעריך את הלוח בנקודה שהיא עצרה וכאן נכנסת לתמונה פונקצית הערכה סטטית. נשים לב שעד עכשו כלל לא השתמשנו בידע שלנו על שחמט. האלגוריתם יודע לשחק כל משחק, בתנאי שמסבירים לו את החוקים כמובן. בשביל הערכה סטטית של לוח נשתמש בידע של מומחים (אם אין אז שחקנים חובבים). למשל כל ילד שמתחיל לשחק שחמט יודע שהמלכה הי הכלי הכי חזק במשחק, ומי שאיבד את המלכה כנראה נמצא במצב יותר גרוע. שיטת הערכה קלאסית היא לתת ניקוד לכל כלי. עד כמה שאני זוכר חייל היה נקודה, פרש 3, רץ 3וחצי, צריך 5, ומלכה 7. כך ניתן למשל העביר למחשה את הידע שפרש שווה לשלושה חיילים. ישנם גם כללי אצבע שידועים לשחמטאים יותר מנוסים. למשל לקראת סוף המשחק עדיף להישאר עם רץ שרץ על משבות מהצבע ההפוך לצבע עלו עומדים החיילים שלך, או למשל שלהכפיל צריחים זה טוב. חוץ מי זה ישנה אפשרות לכוון את הפרמטרים של פונקצית ההערכה בעזרת מחשב. ידוע שלהכפיל צריחים זה טוב, אבל כמה זה באמת שווה במספרים? מומחה אנושי יתקשה להעריך. לכן נותנים למחשב לייצר הרבה פונקציות הערכה ואז עושים "תחרות" בין כולן (מריצים הרבה משחקים אחת נגד השניה) בשביל לבחור את הפונקציה הכי טובה. בשיטה הזאת למשל הגיעו למסקנה שהניקוד לכלים שהצגתי קודם לא טוב מספיק. [דרך אגב, אם השאלה המקורית התיחסה רק לנקודה הזאת, אני מוכן לחלוק כמה כללים כאלו שאני מכיר.] כל מה שהיה עד עכשו זה רק הרעיון. במימוש לא כדאי להשתמש ברקורסיה וצריך להפוך אותה לאיטרציות. לא מייצרים לוח חדש כל פעם שעושים מסע. ועוד כל מיני אופטימיזציות. יש הרבה שאלות שלא התיחסתי אליהן, למשל מהו יצוג טוב ללוח שחמט (רמז: לא מערך 8 על 8)? . כיצד מחשבים את המסעים החוקיים מעמדה נתונה? ועוד. יש גם מספר שיפורים שמשתמשים בהם: - גיזום עץ החיפוש (יש מקרים בהם אין צורך להמשיך לחפש בענף מסוים מפני שערכו לא ישפיע על ההערכה) - ספר פתיחות, המסעים הראשונים של המשחק שמורים מראש ולא צריך לחשב אותם מחדש. - ספר סיומים. היום, אם מגיעים למצב בו יש 5 או פחות כלים לכל צד, אפשר לדעת מי ניצח. - שמירת העמדות. לפעמים ניתן להגיע לאותה עמדה מכמה ענפים שונים, בשביל למנוע חישוב כפול שומרים את הערך שחושב בפעם הראשונה. - מיקבול וחומרה יעודית. ישנן "מפלצות" עם עשרות מעבדים [5]. כנראה לא רלוונטי בשבילך. - יש עוד, כדאי לחפש באינטרנט. ----------- [1] http://vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf [2] הכוונה שאנחנו והמחשב באותו צד. [3] עמדה, לוח, מצב [4] מהלך, או צעד [5] http://en.wikipedia.org/wiki/Hydra_(chess)
התחום של בינה מלאכותית למשחקי לוח היה קפוא הרבה עשורים. השיפורים מדור לדור היו בעיקר הגדלת כוח החישוב של הפלטפורמות, ושיכלול השימוש בידע מומחה (ראי "פונקצית הערכה סטטית" בהמשך). כל האלגוריתמים התבססו (ועדיין מתבססים) על אותה השיטה, של קלוד שנון משנת 1950 [1]. בעשור האחרון לעומת זאת, רואים פריחה של שיטות ואלגוריתמים חדשניים. כנראה שהגיעו למסקנה שהוספת כח חישוב אולי טוב למשחקים כמו שחמט, אך למשחקים אחרים, אבסטרקטיים יותר זה לא מספיק. כעט אני אסביר אך האלגוריתם הקלאסי (זה של שנון) עובד. האלגוריתם הקלאסי הוא די פשוט ואף קל למימוש בגרסה הפשוטה שלו. בשביל יותר פרטים נסי לחפש Minimax באינטרנט. נתחיל מהגדרת הבעיה. נניח אנחנו משחקים בלבן. יש מולנו לוח עם עמדה מסוימת, והתור לשחק הוא שלנו [2]. אנחנו רוצים שמחשב יקבל את העמדה[3] הזאת ויחשב את המסע[4] הטוב ביותר שאנחנו יכולים לעשות במצב הנתון. בואו ניקח את הבעיה הזאת ונעבור לבעיה אחרת. במקום שהמחשב יחשב את המסע הטוב ביותר, כל מה שהוא יעשה זה להעריך למי יש יתרון במצב הנתון. צריך לחשב לא רק למי יש יתרון במצב נתון אלה גם לכמת את היתרון הזה, זאת אומרת שכל עמדה תקבל מספר (נניח בין 0 ל 100) שאומר כמה הלבן קרוב לנצחון. אם יש מט על הלוח ללבן (הלבן הפסיד) אז הערך יהיה 0, אם יש מט לשחור, אז הערך יהיה 100, בשאר המקרים הערך יהיה איפושהו בין 0 ל-100. המטרה שלנו היא לחשב את הפונקציה הזאת בצורה הכי מדויקת שאפשר. אני מקווה שכבר ברור שאם אנחנו יודעים לפתור את הבעיה השניה נוכל גם לפתור את הראשונה. נעשה זאת כך: מהעמדה הנתונה, המחשב יחשב את כל המסעים החוקיים. הוא יבצע כל מסע על הלוח נפרד ואז יחשב, בעזרת הבעיה הראשונה איזו מהעמדות שהתקבלו היא הכי טובה ללבן. זאת אומרת איזו עמדה היא בעלת הערך המקסימלי. המסע שהוביל לעמדה זו הוא המסע הכי טוב. ואיך פותרים את הבעיה השניה? נשתמש ברקורסיה! נניח שתורו של הלבן לשחק. המחשב יחשב את כל המסעים האפשריים של הלבן, ולכל עמדה שהתקבלה יחשב את ערכה (ברקורסיה). היות ותורו של הלבן, והלבן רוצה לנצח, הוא ישחק את המסע שמוביל לעמדה עם הערך המקסימאלי. כאשר בחישוב הרקורסיה מגיעים לעמדה שתורו של השחור לשחק, בוחרים את המסע שמוביל ללוח עם הערך המינימלי. בגלל זה קוראים לזה Minmax. התהליך דומה למה שמתרחב בראשו של שחקן אנושי, השחקן האנושי בודק אפשרויות: "אם אני אעשה כך, אז היריב יעשה כך ואז אני יעשה כך. אבל אם היריב ישחק כך אני אעשה כך" וכו... מהו תנאי העצירה של הרקורסיה? ניתן לטעון שתנאי העצירה הוא כאשר הגענו למצב בו יש מט לאחד הצדדים. האם זה פרקטי? בואו נבדוק. ניתן להסתכל על תהליך החישוב כעץ. המחשב צריך לעבור על כל העמדות שניתן ליצור מעמדה נתונה, ולכל אחת מהן לעבור על כל העמדות שהיא יוצרת וכו. ניתן לראות דוגמא של עץ חיפוש עבור איקס עיגול ב[קישור הבא]. נבדוק על כמה עמדות המחשב צריך לעבור. אם מעמדה נתונה ממוצעת יש 20 מסעים חוקיים, אז חישוב של מסע קדימה דורש מעבר על 20 לוחות. שני מסעים קדימה זה 20*20=400 שלושה מסעים קדימה זה 20*20*20 וכך הלאה. חישוב של 10 לוחות דורש מעבר על 1024 מיליארדי עמדות שעבור מחשב ביתי זה כבר מהווה בעיה. במשחק שחמט ממוצע של-120 מסעים לא ניתן לעבור על כל האפשרויות. במשחקים אחרים, ניתן לעבור על כל האפשרויות מהעמדה ההתחלתית, ולכן משחקים כאלו נחשבים ל"פתורים", זאת אומרת אם כל צד משחק הכי טוב שאפשר, ניתן לדעת עוד לפני שהתחיל המשחק מה תהיה התוצאה. ראינו שהרקורסיה לא יכולה להגיע עד לעלים של העץ ולכן היא צריכה לעצור לפני כן. בכל זאת צריך להעריך את הלוח בנקודה שהיא עצרה וכאן נכנסת לתמונה פונקצית הערכה סטטית. נשים לב שעד עכשו כלל לא השתמשנו בידע שלנו על שחמט. האלגוריתם יודע לשחק כל משחק, בתנאי שמסבירים לו את החוקים כמובן. בשביל הערכה סטטית של לוח נשתמש בידע של מומחים (אם אין אז שחקנים חובבים). למשל כל ילד שמתחיל לשחק שחמט יודע שהמלכה הי הכלי הכי חזק במשחק, ומי שאיבד את המלכה כנראה נמצא במצב יותר גרוע. שיטת הערכה קלאסית היא לתת ניקוד לכל כלי. עד כמה שאני זוכר חייל היה נקודה, פרש 3, רץ 3וחצי, צריך 5, ומלכה 7. כך ניתן למשל העביר למחשה את הידע שפרש שווה לשלושה חיילים. ישנם גם כללי אצבע שידועים לשחמטאים יותר מנוסים. למשל לקראת סוף המשחק עדיף להישאר עם רץ שרץ על משבות מהצבע ההפוך לצבע עלו עומדים החיילים שלך, או למשל שלהכפיל צריחים זה טוב. חוץ מי זה ישנה אפשרות לכוון את הפרמטרים של פונקצית ההערכה בעזרת מחשב. ידוע שלהכפיל צריחים זה טוב, אבל כמה זה באמת שווה במספרים? מומחה אנושי יתקשה להעריך. לכן נותנים למחשב לייצר הרבה פונקציות הערכה ואז עושים "תחרות" בין כולן (מריצים הרבה משחקים אחת נגד השניה) בשביל לבחור את הפונקציה הכי טובה. בשיטה הזאת למשל הגיעו למסקנה שהניקוד לכלים שהצגתי קודם לא טוב מספיק. [דרך אגב, אם השאלה המקורית התיחסה רק לנקודה הזאת, אני מוכן לחלוק כמה כללים כאלו שאני מכיר.] כל מה שהיה עד עכשו זה רק הרעיון. במימוש לא כדאי להשתמש ברקורסיה וצריך להפוך אותה לאיטרציות. לא מייצרים לוח חדש כל פעם שעושים מסע. ועוד כל מיני אופטימיזציות. יש הרבה שאלות שלא התיחסתי אליהן, למשל מהו יצוג טוב ללוח שחמט (רמז: לא מערך 8 על 8)? . כיצד מחשבים את המסעים החוקיים מעמדה נתונה? ועוד. יש גם מספר שיפורים שמשתמשים בהם: - גיזום עץ החיפוש (יש מקרים בהם אין צורך להמשיך לחפש בענף מסוים מפני שערכו לא ישפיע על ההערכה) - ספר פתיחות, המסעים הראשונים של המשחק שמורים מראש ולא צריך לחשב אותם מחדש. - ספר סיומים. היום, אם מגיעים למצב בו יש 5 או פחות כלים לכל צד, אפשר לדעת מי ניצח. - שמירת העמדות. לפעמים ניתן להגיע לאותה עמדה מכמה ענפים שונים, בשביל למנוע חישוב כפול שומרים את הערך שחושב בפעם הראשונה. - מיקבול וחומרה יעודית. ישנן "מפלצות" עם עשרות מעבדים [5]. כנראה לא רלוונטי בשבילך. - יש עוד, כדאי לחפש באינטרנט. ----------- [1] http://vision.unipv.it/IA1/ProgrammingaComputerforPlayingChess.pdf [2] הכוונה שאנחנו והמחשב באותו צד. [3] עמדה, לוח, מצב [4] מהלך, או צעד [5] http://en.wikipedia.org/wiki/Hydra_(chess)
IdleThought
New member
ואו
אורן, הבחור נראה מועמד רציני להאדמה
אורן, הבחור נראה מועמד רציני להאדמה
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.