לא מצליח ליצור עץ משחק מספיק עמוק

[Blade2]

לא מצליח ליצור עץ משחק מספיק עמוק

ניסיתי לתכנת משחק איקס עיגול (דו מימדי, עד 5 בשורה, לוח אינסופי), ולממש שם מינמקס, הבעיה היא שזה לא מייצר לי עץ משחק בעומק גדול מ3 בזמן סביר. האם מישהו מוכן להתסכל בקוד שכתבתי ולומר לי מה לא בסדר? מה לא יעיל מספיק? כמה הערות הדרושות להבנת התכנית: אני מייצג רק את ה"אבנים" (איקסים ועיגולים) במערך ושומר עבור כל אחת את ה x ו y שלה, אני לא שומר ייצוג של כל הלוח. כמו כן, אני לא משחק במשבצות שרחוקות עד רווח של משבצת אחת מ"אבן" כלשהי, (מפני שהלוח אינסופי אני צריך להגביל את המחשב איכשהו ביצירת המהלכים שלו)

 

[Blade2]

קובץ ה cpp

(נא לשנות את הסיומת)

 

[Blade2]

קובץ h

(נא לשנות את הסיומת)

 

[ליאור ב]

נסה שני דברים.

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

 

[Blade2]

תודה, אבל..

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

 

[אלדד28]

חסרים לי כל מיני דברים

ב - GENERATEMOVES, מה זה MINY ו - MAXY (וכל החבר'ה שלהם?) כלומר, מה הערכים שלהם? חסר לי tictactoe.h כדי שאוכל לקמפל את כל העסק. תעלה גם אותו (ואם יש עוד קבצים אז גם אותם) ואסתכל שוב. אתה יכול להעלות את כולם ב-ZIP אחד שהסיומת שלו היא TXT.

 

[Blade2]

MINX, MAXY וחברים....

הם מחזיקים את הx והy הקיצוניים ביותר שבהם יש כלים, וכך זה תוחם את כל הכלים במלבן - הם מתעדכנים בכל פעם שמניחים כלי על הלוח, אני משתמש בזה כדי לדעת איפה לייצר את המהלכים הבאים (הרי אין הגיון לשחק במרחק 1000 משבצות משם) עשיתי כדבריך ולהודעה זו מצורף zip שמכיל את קובץ ה cpp ואת קובץ ה h.

 

[Blade2]

ושכחתי להודות לך על הנכונות לעזור

 

[Blade2]

עוד כמה הערות

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

 

[אלדד28]

יש לי מחשב חזק ../images/Emo8.gif

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

 

[Blade2]

10 -15 שניות - עץ בעומק 4?!

אני עובד עם פנטיום 4 - 1500, 256 rdram וזה כמעט הרג אותו... אנסה להריץ אותו ב release באמת ושוב, תודה!

 

[אלדד28]

אכן

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

 

[אלדד28]

הבעיה היא

שהאלגוריתם שבו אתה משתמש הוא אקספוננציאלי, כלומר, הוא בסדר גודל של 2 בחזקת גודל הקלט. במקרה שלך זה יותר מ - 2, וגם יש מכפיל נוסף. בעומק של 1, העץ מונה 24 עלים. בעומק של 2, העץ מונה 816 עלים. בעומק של 3, העץ מונה 34960 עלים. בעומק של 4, העץ מונה 1,785,152 עלים. עומק של 5 לא ניסיתי. זה היה משבית לי את המחשב לשעה בערך. פלא שלוקח לו הרבה זמן? הבעיה עם עצי משחק היא בדיוק הבעיה הזו. מהר מאוד אתה מגיע למצב שבו אתה לא יכול לחשב את העסק. מה עושים? מוצאים פתרון אחר, משופר. קח למשל שחמט. בשחמט, מספר הקומבינציות ל - 5 המהלכים הראשונים בלבד הוא מיליונים רבים של קומבינציות. ולמרות זאת, אנשים יכולים לתכנן מספר יותר גדול של מהלכים קדימה, וגם מחשבים יכולים לתכנן מספר גדול יותר של מהלכים קדימה. איך? פה יש כל מיני שיטות, וצריך לנסות כמה מהן לפני שמחליטים מה יותר טוב ומה פחות טוב. השיטה הבסיסית היא לחתוך ענפים מהעץ. נניח שיש לך ברמה הראשונה 15 ענפים, וברמה השניה 14 ענפים לכל ענף ראשון. זה יוצא 210 עלים, שזה הרבה. אבל למעשה, ברור שיש כל מיני צעדים שהם יותר טובים מהאחרים. למשל, יש צעדים שאתה חייב לעשות - אם למשל היריב שם (בלוח 4x4) שלושה עיגולים באותה שורה, הרי ברור שבצעד הבא אתה חייב לשים X באותה שורה, אחרת הוא ינצח. העניין הוא שאם זה המצב, אתה פתאום לא צריך לבדוק את כל האפשרויות האחרות - אתה *חייב* לשים שם חתיכה. עכשיו, הנקודה היפה היא שאם בכל "מצב לוח" תבדוק האם מישהו ניצח, ובהתאם תימנע מלחשב את כל המצבים שאחריו - תחסוך הרבה מאוד בדיקות למעשה. בנוסף, יש צעדים שהם אסטרטגיים יותר או פחות. אם תיתן ניקוד לכל מצב לוח, ואז נניח תזרוק 75% מהענפים ותתמקד ב - 25% מהשאר, תחסוך הרבה מאוד זמן. זה רק קצה המזלג. נתקלת בבעיה אולי הגדולה ביותר של עולם הבינה המלאכותית - בהצלחה

 

[Blade2]

תודה ושתי שאלות אם אתה כבר כאן

חפפתי את האופרטור = עבור הclass Position בפונקציה generate moves כאשר עשיתי

NewPos=*this*;​

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

 

[Blade2]

הכוכבית לא בצד הנכון

*NewPos=*this;​

 

[ליאור ב]

לא ליצור אובייקטים בזמן ריצה.

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

 

[Blade2]

כל רמה זה לא אובייקט אחד.

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

 

[ליאור ב]

יש אמנם עץ גדול אבל...

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

 

[ליאור ב]

אני ממש מצטער על חוסר ההתחשבות.

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

 

[Blade2]

תודה רבה! אבל,

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