Page 113 - sce smart
P. 113
חוברת תקצירים הנדסת תוכנה | מסיימי תשפ״ג
הטיית גביע העולם בכדורגל
מס' פרויקט SWE018
בהנחיית: ד״ר ליאור ארונשטם
המכללה האקדמית להנדסה SCE אשדוד , המחלקה להנדסת תוכנה, קמפוס אשדוד
omeralali@gmail.com
מאת: עומר אללי;
113
Tournament fixing problem היא בעיה פתוחה במדעי המחשב הנחקרת שנים רבות ועוסקת
באפשרות של הטיית טורניר גביע ע״י מארגן הטורניר כדי לנסות להבטיח ששחקן ספציפי ינצח.
את הבעיה ניתן להגדיר פורמלית כך: מקבלים קבוצה של שחקנים V, מידע עבור כל זוג שחקנים ( ,u
w) האם u או w ינצחו במשחק ראש בראש, ושחקן שאנחנו מעוניינים בו v; והשאלה היא האם קיים
סידור התחלתי לטורניר גביע שבו v מנצח?
במסגרת הפרויקט בחרנו לחקור את אפשרות הטיית משחק גביע העולם בכדורגל (מונדיאל), אשר בו
קיים שלב נוסף, שלב בתים הקודם לשלב טורניר הגביע, בעזרת אלגוריתם גנטי.
לצורך המחקר ביצענו סקירת ספרות מקיפה על הגישות הקיימות השונות של האלגוריתמים הגנטיים
שעל בסיסה פיתחנו אלגוריתם גנטי ייעודי לבחינת הבעיה. את המודל בחנו בתחילה על מידע סינטטי
שהוגרל בצורה אקראית ע"פ מודל מוכר של הגרלת טורנירים אקראיים ובהמשך על מידע הסתברותי
אמיתי של משחקי גביע העולם בכדורגל.
תוצאות המחקר הראו כי המודל מצליח למצוא סידור התחלתי מנצח לשחקן רצוי v, גם לשחקנים
חלשים ובעלי הסתברות נמוכה (0.05) לנצח. בחינת פרמטרים שונים הביאה לשיפור משמעותי
בהצלחת המודל (שיפור של 400%-1000%).
את המודל פיתחנו בשפת פייתון עם שימוש בספריית numpy .
