פרויקט Mastermind: אלגוריתמים גנטיים וממשק משתמש

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

תיאור המשחק Mastermind

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

מטרת הפרויקט

• לשפר ולפתח גרסה מתקדמת של המשחק Mastermind
• לשלב אלגוריתמים גנטיים ושימוש בתורת הגרפים לחיפוש חכם יותר של ניחושים
• להוסיף ממשק משתמש (GUI) להזנת פרמטרים ובחירת מצב משחק

שלבי הפיתוח והמשימות לביצוע

• סקירת הפרויקט והכנת סביבה
  • סקירת הקוד הקיים והבנת המבנה הנוכחי
  • התקנת סביבת עבודה מתאימה
• הפיכת המשחק למודולרי
  • הוספת תמיכה למספר צבעים ומספר מקומות משתנים
• שיפור האלגוריתם הגנטי
  • בחירת הורים חכמה יותר
  • פונקציית כושר משופרת
  • מוטציה חכמה
  • שיפור ניהול הקשרים בין הצמתים
• שיפור חיפוש מבוסס גרף
  • שילוב BFS/A* למציאת פתרונות חכמים יותר
• שיפור תנאי העצירה
  • בדיקה חכמה של שינויים
  • עצירה דינמית כאשר נדרש
• הוספת GUI
  • יצירת ממשק בסיסי עם JavaFX
  • בניית ממשק משתמש בסיסי עם JavaFX
  • הוספת אפשרות לקלט דינמי
  • אפשרות למשתמש להזין מספר צבעים ומקומות לבחירתו
  • חיבור המשחק ללוח קלט ויצירת חווית ניחוש
  • יצירת ממשק שמאפשר הכנסת ניחושים ומציג את המשוב בצורה ויזואלית
  • הצגת לוח ניחושים בצורה גרפית
  • המחשת המשחק עם עיצוב גרפי מתאים
  • בדיקות ותיקונים למערכת ה-GUI
  • בדיקות להבטחת תקינות העבודה עם הממשק הגרפי

פלטפורמת העבודה לתיעוד

• הפרויקט יתועד במסמך Google Docs לשמירה על תיעוד מסודר של העבודה
  • יופיע תיאור מפורט של כל שינוי שבוצע
  • יוצגו קטעי קוד רלוונטיים
  • יצוינו תובנות או בעיות שעלו במהלך העבודה
  • יצורפו צילומי מסך להמחשה

ביצוע שלב שני: הפיכת המשחק למודולרי

• הקבועים COLORS ו-PEGS הוחלפו בפרמטרים דינמיים הניתנים להזנה ע"י המשתמש
• פונקציות הקוד הותאמו כך שכל ההגדרות יהיו גמישות ומתאימות למספר משתנה של יתדות וצבעים
• הוסף קלט מהמשתמש (Scanner) לבחירת מספר היתדות והצבעים בצורה דינמית
• פונקציות הותאמו כך שיקבלו את הערכים שנקבעו על ידי המשתמש במקום להשתמש בערכים קבועים
• בוצעו בדיקות ותיקונים לבעיות שהתגלו לאחר המעבר לדינמיות

תובנות מהשינוי

• גמישות המשחק שופרה, מאפשר משחק עם מגוון הגדרות מותאמות אישית
• שגיאת זיכרון (OutOfMemoryError) קרתה במצבים מסוימים כאשר בוחרים מספר גבוה של יתדות וצבעים (למשל 10x10)
  • הסיבה: יצירת כל הצירופים האפשריים של הקוד דורשת זיכרון רב
  • פתרון אפשרי: שימוש בגישה שמייצרת רק את הצירופים הדרושים במקום לשמור את כולם בזיכרון

הדגמה של הרצת המשחק

• קלט רגיל (6 יתדות, 6 צבעים)
  • המשחק הצליח לפתור את הקוד ב-6 שלבים בלבד
• קלט גבוה (10 יתדות, 10 צבעים) הוביל לשגיאה
  • תקלה זו היא תוצאה של שימוש רב בזיכרון ביצירת כל הצירופים האפשריים, לכן יש לשפר את מבנה הנתונים ולמנוע שמירה של כל האפשרויות בבת אחת

תיעוד מהקוד של השינויים

• השינוי באתחול
• שינויים נעשו גם בשאר הקוד כדי להשתמש בערכי pegs, colors שנקלטו מהמשתמש במקום הקבועים COLORS ו-PEGS

פתרון בעיית מחסור בזיכרון וניהול זיכרון יעיל

• בעיה שהתגלתה: שגיאת OutOfMemoryError בקלט עם מספר גדול של יתדות וצבעים (למשל pegs = 10, colors = 10) עקב ניסיון ליצור ולשמור את כל הצירופים האפשריים של הקודים
  • הפתרון: ניהול חכם של זיכרון והקטנת הצורך באחסון מידע
    • מניעת יצירה ושמירה של כל הצירופים: במקום לשמור אותם בזיכרון, הקוד מייצר אותם רק לפי הצורך, ובכמות גדולה (מעל 45,000) נעשה שימוש באלגוריתם דינמי ליצירת קודים אקראיים
    • מניעת יצירה של גרף מגבלות ענק: הגרף נבנה רק אם כמות האפשרויות קטנה מ-45,000, אחרת הוא לא נוצר
    • טיפול במקרה של אוכלוסייה ריקה באלגוריתם הגנטי: במצב זה, הקוד מייצר ניחוש אקראי כדי למנוע קריסה

בדיקות לאחר השיפורים

• קריסות על רקע זיכרון תוקנו

שיפור האלגוריתם הגנטי - תיעוד מלא

• השינויים מהקוד הישן לקוד החדש:
  • בחירת אוכלוסייה ראשונית חכמה יותר (חלק נבחר מתוך גרף האילוצים)
  • שיפור פונקציית הכושר (משקל רב יותר ניתן להתאמה מלאה)
  • שיפור בחירת ההורים (בחירה מתוך 50% הטובים ביותר)
  • שיפור הקרוסאובר (חלוקה לפי סדר אקראי להבטחת גיוון)
  • מוטציה חכמה יותר (שיעור המוטציה מותאם דינמית לפי מגבלות הגרף)
  • יפור מנגנון הסינון על בסיס גרף האילוצים (אגרסיבי יותר)
• ההשפעה היא יצירת אוכלוסייה ראשונית חכמה יותר
• שיפור פונקציית הכושר:
  • פונקציית הכושר החדשה מעניקה משקל גבוה יותר להתאמות מדויקות, כך שהתפתחות האוכלוסייה תהיה מהירה ומדויקת יותר
• שיפור קרוסאובר:
  • הקרוסאובר מתבצע על ידי חלוקה של הגנים בצורה אקראית ולא רק לפי אינדקסים זוגיים (לשיפור הגיוון)
• שיפור מוטציה:
  • במקום לשנות גן אקראי לחלוטין, המוטציה מתחשבת בגרף האילוצים ובודקת אילו שינויים רלוונטיים.
• התוצאות:
  • שיפור ביצועים משמעותי – מספר הדורות קטן בכ-30%
  • פחות קריסות עקב ניהול אוכלוסייה חכם יותר
  • יציבות גבוהה יותר בזכות מוטציה דינמית
  • גמישות עם גרפים – מאפשר שילוב קל של BFS/A* לשלב 4

שלב 4: שיפור חיפוש המבוסס על גרף

• המטרה לשפר את החיפוש באמצעות שילוב מנגנון חיפוש חכם מבוסס גרפים בדגש על אלגוריתם A*, לייעל את החיפוש ולהוביל לניחושים מהירים יותר
• הפונקציות:
  • heuristic פונקציית
    • מעריכה את "המרחק" בין הניחוש הנוכחי לקוד הסודי (נותנת עדיפות למיקומים נכונים (יתדות שחורות), ושוקלת מיקומים שגויים (יתדות לבנות) במשקל נמוך יותר) - עוזרת לאלגוריתם A* להתמקד בניחושים מבטיחים יותר aStarSearch - אלגוריתם חיפוש
    • מבצע חיפוש ממוקד בגרף האילוצים כדי למצוא את הניחוש האופטימלי - משתמש בתור עדיפויות לבחירת הניחוש המבטיח ביותר, מונע עיבוד חוזר על ידי שימוש במערך closedSet ומייצר ניחושים דינמיים כאשר הגרף גדול מדי - חוסך בזמן וחישובים

הוספת A* לתהליך ה-run()

• השינוי: אחרי שכל דור נוצר באלגוריתם הגנטי, מנסים למצוא פתרון טוב יותר עם A* - אם A* מצליח, משנים את הניחוש הטוב ביותר בו, ואם הוא נכשל, שומרים על הניחוש מהאלגוריתם הגנטי או יוצרים ניחוש אקראי - משפר את דיוק הניחושים ושומר על ביצועים גבוהים יתרונות A* על פני BFS
  • שיפור על BFS (חיפוש לרוחב) בכך שהוא משתמש בפונקציית היוריסטיקה כדי להכווין את החיפוש לכיוון הפתרון בצורה חכמה יותר
  • בעוד BFS סורק אפשרויות ברוחב, A* מחפש בצורה מונחית ובוחר בכל צעד נתיב שסביר להוביל לפתרון על בסיס פונקציה היוריסטית איך A* פועל
  • משתמש בשני מרכיבים: (1) g(n) - מספר הצעדים שעברנו עד הצומת הנוכחי, ו-(2) h(n) - הערכת מספר הצעדים שנותרו עד הפתרון (היוריסטיקה)

האלגוריתם בוחר בצומת עם הערך הנמוך ביותר של

• f(n) = g(n) + h(n)
• (ערך נמוך ביותר = המסלול הכי קצר או הכי סביר לפתרון)

איך A* משתלב ב-Mastermind?

• מחפש ניחוש טוב יותר מתוך הגרף ומעדיף את הניחוש עם ההערכה הטובה ביותר
• במקום לבדוק את הצירופים האפשריים, A* מנתב את החיפוש לצירופים המבטיחים

למה A* עובד טוב במשחק?

• צמצום מרחב החיפוש (מחפש רק בכיוונים הרלוונטיים)
• שימוש בפונקציה היוריסטית (מתעדף ניחושים על פי התאמתם לקוד הסודי)
• פועל היטב עם האלגוריתם הגנטי (מצמצם את האפשרויות ומוצא את הניחוש האופטימלי)

יתרונות נוספים

• שיפור היעילות, החיסכון בזיכרון (יצירה דינמית של נתונים) והיציבות (תמיכה במספר רב של יתדות וצבעים)

סיכום

• שילוב A* הצליח לשפר את תהליך הניחוש, להפוך אותו ליעיל יותר ולחסוך במשאבי חישוב

שלב 5: שיפור תנאי העצירה

• המטרה, למנוע מצב שבו האלגוריתם ממשיך לפעול ללא התקדמות, ולחסוך זמן חישוב יקר ולשפר את ביצועי המשחק
• השיפורים שבוצעו:
  • זיהוי סטגנציה (Stagnation Detection): עצירת האלגוריתם אם לא חל שיפור משמעותי בציון הכושר (Fitness Score) לאורך 10 דורות רצופים או אם השינוי הממוצע בכושר הדורות קטן מאוד
  • בדיקת שונות באוכלוסייה (Population Variance Check): עצירת האלגוריתם אם כל הניחושים באוכלוסייה דומים מאוד אחד לשני (שונות נמוכה מאוד)
  • שילוב משופר עם A*: האלגוריתם בודק האם A* מצא פתרון עם ציון כושר מקסימלי לאחר כל דור, ואם כן, המשחק מסתיים מידית מהי השונות ומדוע היא חשובה?
  • שונות היא מדד לכמה הערכים באוכלוסייה רחוקים או קרובים זה לזה. שונות גבוהה מעידה על ניחושים מגוונים באוכלוסייה, ושונות נמוכה מעידה על התכנסות האלגוריתם יתרונות השיפורים
  • חיסכון בזמן חישוב, שיפור דיוק הפתרון וניהול אוכלוסייה חכם
  • האלגוריתם יכול לעצור את האלגוריתם מיד עם מציאת הפתרון, האלגוריתם מתחשב בגיוון הפתרונות ומונע התכנסות מוקדמת מדי סיכום
  • האלגוריתם יודע לזהות בעצמו מתי להפסיק, אם אין התקדמות, אם כל הפתרונות דומים מדי, או אם נמצא הפתרון הנכון שלב 6: הוספת GUI

הוספת ממשק משתמש גרפי (GUI) לפרויקט

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

חיבור המשחק ללוח קלט ויצירת חווית ניחוש

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

בדיקות קלט מספריות

• הוספת פונקציה לבדיקת הקלט שנקלט
• בדיקת תקינות לקלט הקוד הידני:
  • בדיקה אם הקוד שהוזן ע"י השחקן תקין

תוצאות בדיקות

איתור שגיאות לפני הרצת האלגוריתם ושיפור תוצאות האלגוריתם, גמישות רבה יותר והגמשת טווחים שונים

• דיוק רב יותר ובמשחק קל יותר

סיכום השיפורים

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

הוראות התקנה

• מדריך כיצד להריץ את הפרוייקט על המחשב

1. הורדה של JavaFX
2. פרטי חבילה שנדרשים (לאחר הורדת הקובץ, תמצאו את קובץ ה-zip המכיל את ספריות ה-JavaFX.
3. יש לחלץ את הקובץ למקום בו יהיה נגיש (למשל, בתיקיית ~/javafx).

הוראות קימפולציה

javac --module-path ~/javafx/lib --add-modules javafx.controls,javafx.fxml --enable-preview --release 21 HybridMastermindGA.java MastermindGUI.java

JavaFX מציין את מיקום ספריית JavaFX -מוודא שהמודולים של JavaFX מוטענים -ואפשר שימוש בתכונת ניסוי- ומבצע קימפול לגרסת 21 שלJava java --module-path ~/javafx/lib --add-modules javafx.controls,javafx.fxml --enable-preview MastermindGUIאוראת הפעלה לאחר מכן java --module-path javafx-lib --add-modules - מצביע על מיקום וספרייות java

פקודה אחת לביצוע

• ניתן להריץ את המכלול בפקודה אחת המאחדת לביצוע את הכל בבת אחת התוכנית תבצע ותרוץ במסמך מובנה

רשימת התיקייה

• התיקייה מכילה את הקבצים והספריות הבאים: MASTERMIND Jar- התיקן הראשי המרכזי. - ספריות החיוניות קובץ מובייל - src- ותוכנות מגוונות - run.bat - run.sh

איך לקמפל מחדש

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

MASTERMIND .jar הסבר

• הקובץ תת הליך מובייל

כיצד להציג

• כדי להציג , מומלץ דרך פקודה

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

הסבר לבעיית שיבוש

• בדרכ אמורה להיות רצות בצורה תקינה וקריאה לצרכים מסויימים

בעיות ופתרונות