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

http://www.chess.com/blog/zaifrun יש סדרות או מאמרים בנושא יצירת מנוע שחמט אם אתה רוצה לבחון לעומק יותר איך הם עובדים.

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

הערכה

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

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

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

אבל מה עם מהלכי מיקום עמוקים ועמוקים?

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

חיפוש

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

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

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

סיכום / שילוב הכל

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

אני מסכים עם התשובות.

אני זוכר ש- GM Roman Dzindzichashvili דיבר על זה, באחד מסרטוני ה מעבדות של רומן, אני לא זוכר איזה סרטון זה היה (אם מישהו מכיר את הפרטים אנא ערוך את תשובתי).

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

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

ערוך

ראה גם וויקי תכנות השחמט.

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

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

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

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

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

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

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

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

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