משתמש:N12345678/משחקים עם ידיעה שלמה

משחק עם ידיעה שלמה (Game With Perfect Information)

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

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

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

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

משפט פון ניומן (von Neumann):

בכל משחק שני שחקנים בעל ידיעה שלמה, שבו קבוצת התוצאות האפשריות היא÷ { תיקו, I מנצח, II מנצח } = O
מתקיימת אחת ורק אחת משלוש האפשרויות הבאות:

1. לשחקן I יש אסטרטגיה מנצחת.
2. לשחקן II יש אסטרטגיה מנצחת.
3. לכל אחד משני השחקנים יש אסטרטגיה המבטיחה לפחות תיקו.

• אסטרטגיה SI של שחקן I נקראת אסטרטגיה מנצחת אם: I מנצח = (u(SI,SII לכל SII.
• אסטרטגיה SI של שחקן I מבטיחה לפחות תיקו לשחקן I אם: {תיקו, I מנצח} u(SI,SII) E לכל SII.

משפט קיון (Kuhn):

בכל משחק סופי בעל ידיעה שלמה קיים לפחות שיווי משקל אחד.

ראו גם

• שיווי משקל
• מונחים בתורת המשחקים

לקריאה נוספת

• שמואל זמיר, מיכאל משלר ואילון סולן, תורת המשחקים, הוצאת מאגנס , 2008