משפט צרמלו

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

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

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

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

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

הוכחה

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

עץ משחק

דוגמה לעץ משחק
ערך מורחב – עץ משחק

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

תוכן ההוכחה

המחשה להוכחה. במקרה זה השורש אפור, לכן כל שחקן יכול לכפות תיקו.

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

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

לפי הניתוח האחרון, ייתכנו שלוש אפשרויות התלויות בצבע של השורש של העץ:

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

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

דוגמאות על משחקים שונים

משחק הלוח רברסי

משפט צרמלו נשען על כמה תכונות מופשטות של המשחק:

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

להן דוגמאות אחדות למשחקים שעומדים בתנאי הסף של המשפט ועל כן הוא חל עליהם:

  • ארבע בשורה - האפשרות הראשונה נכונה - קיימת אסטרטגיה המבטיחה ניצחון לשחקן הראשון.
  • רברסי על לוח של 6x6 - האפשרות השנייה נכונה - קיימת אסטרטגיה המבטיחה ניצחון לשחקן השני.
  • איקס עיגול - האפשרות הנכונה עבורו היא השלישית - כל צד יכול לכפות תיקו.
  • דמקה אנגלית - האפשרות הנכונה עבורו היא השלישית - כל צד יכול לכפות תיקו.
  • שחמט[1] - לא ידוע - איננו משחק פתור, טרם נמצאה הוכחה איזו משלוש האפשרויות היא הנכונה.

להן דוגמאות אחדות למשחקים של שני שחקנים שאינם עומדים בתנאי הסף של המשפט ועל כן לא חל עליהם:

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

קישורים חיצוניים

הערות שוליים

  1. ^ בהנחה שפועל כלל המגביל את המשחק למספר מסעים סופי. לדוגמה, ניתן להחיל את חוק חמישים המסעים כך שיפעל באופן אוטומטי ולא רק לדרישת אחד השחקנים. במקרה זה, משחק השחמט מוגבל ל-5898 תורות לכל צד (ראו להרחבה כאן - https://www.youtube.com/watch?v=D5DXJxR3Uig) ובפרט הוא סופי.

Read other articles:

A gas processing complex in Hazira, India Hazira Gas Processing ComplexAerial view of Hazira Gas Processing Complex (2011)Location of Hazira Gas Processing ComplexCountryIndiaProvinceGujaratCityHazira, SuratCoordinates21°09′28″N 72°43′51″E / 21.157870°N 72.730929°E / 21.157870; 72.730929Refinery detailsOperatorOil and Natural Gas CorporationOwner(s)Ministry of Petroleum and Natural Gas Hazira Gas Processing Complex (also known as HGPC) is a natural gas proc...

 

17th Bombardment Wing redirects here. For the 17th Bombardment Wing of World War II, see 17th Air Division. Unit of the US Air Force assigned to the Air Education and Training Command This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: 17th Training Wing – news · newspapers · books · scholar · JSTOR (December 20...

 

Luvinate commune di Italia Tempat Negara berdaulatItaliaRegion di ItaliaLombardyProvinsi di ItaliaProvinsi Varese NegaraItalia Ibu kotaLuvinate PendudukTotal1.305  (2023 )GeografiLuas wilayah4,07 km² [convert: unit tak dikenal]Ketinggian425 m Berbatasan denganBarasso Varese Casciago Castello Cabiaglio SejarahSanto pelindungHippolitus dari Roma Informasi tambahanKode pos21020 Zona waktuUTC+1 UTC+2 Kode telepon0332 ID ISTAT012093 Kode kadaster ItaliaE769 Lain-lainSitus webLaman resmi...

Voce principale: Partito Comunista Italiano. La neutralità di questa voce o sezione sull'argomento storia è stata messa in dubbio. Motivo: Articolo fazioso, fonti di parte e utilizzate in maniera di parte. Leggendo la voce nella sua interezza si nota che essa consiste nel sostenere una precisa visione del fenomeno, parziale. In conclusione, la voce appare più come un articolo da sito web che alterna a fatti storici considerazioni chiaramente di parte. Vedere anche numerose critiche p...

 

Stasiun Magelang Kota Magelang Kota Bekas gudang Stasiun Magelang di Terminal KebonpoloLokasiJalan Jenderal Oerip SoemohardjoPotrobangsan, Magelang Utara, Magelang, Jawa TengahIndonesiaKoordinat7°27′53″S 110°13′21″E / 7.46472°S 110.22250°E / -7.46472; 110.22250Koordinat: 7°27′53″S 110°13′21″E / 7.46472°S 110.22250°E / -7.46472; 110.22250Operator Kereta Api IndonesiaDaerah Operasi VI Yogyakarta Letakkm 46+855 lintas Yogyak...

 

Questa voce o sezione sull'argomento calciatori è priva o carente di note e riferimenti bibliografici puntuali. Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento. Questa voce sull'argomento calciatori ...

Public university in Berkeley, California Not to be confused with Berkeley College (disambiguation). University of California, BerkeleyFormer namesUniversity of California (1868–1958)MottoFiat lux (Latin)Motto in EnglishLet there be lightTypePublic land-grant research universityEstablishedMarch 23, 1868; 156 years ago (1868-03-23)[1]Parent institutionUniversity of CaliforniaAccreditationWSCUCAcademic affiliationsAAUAPRUIARUURASpace-grantEndowment$6.9 billion (...

 

Pour les articles homonymes, voir Tanaka. Kōichi TanakaKōichi Tanaka en 2020.BiographieNaissance 3 août 1959 (64 ans)ToyamaNom dans la langue maternelle 田中耕一Nationalité japonaiseDomicile Préfecture de ToyamaFormation Université du Tōhoku (licence (en)) (1978-1983)École secondaire de Toyama Chūbu (d)Toyama City Shimazono Junior High School (d)Activités Chimiste, professeur d'université, ingénieurAutres informationsA travaillé pour Université de TokyoUniversité du T...

 

American interior design firm Mr. William H. Vanderbilt's Drawing-Room, (1882). The firm of Herter Brothers, (working 1864–1906), was founded by German immigrants Gustave (1830–1898) and Christian Herter (1839–1883) in New York City. It began as a furniture and upholstery shop/warehouse, but after the Civil War became one of the first American firms to provide complete interior decoration services. With their own design office and cabinet-making and upholstery workshops, Herter Brothers...

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Administrative divisions of Transnistria – news · newspapers · books · scholar · JSTOR (May 2019) (Learn how and when to remove this message) Administrative divisions of Transnistria. The Pridnestrovian Moldavian Republic (PMR, also known as Transnistria) is subdivided into five...

 

Northern Irish politician (born 1986) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (October 2020) (Learn how and when to remove this message) Gordon LyonsMLAMinister for CommunitiesIncumbentAssumed office 3 February 2024First MinisterMichelle O'NeillPreceded byDeirdre Hargey (2022)Minister for the EconomyIn office6 July 2021 – 27 October 2022...

 

هضبة الصمان في شمال شرق شبه الجزيرة العربية الصُّـمَّان هي هضبة مستطيلة تقع في شرق شبه الجزيرة العربية وتمتد الهضبة من الربع الخالي جنوباً حتى الحدود العراقية شمالاً وذلك بطول 1000 كيلو متر تقريباً ويتراوح عرضها بين 80 إلى 250 كيلو متر تقريباً، ويبلغ ارتفاع الهضبة ما بين 25 متر ...

Canadian provincial political party This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Progressive Conservative Party of New Brunswick – news · newspapers · books · scholar · JSTOR (October 2016) (Learn how and when to remove this message) Progressive Conservative Party of New BrunswickParti progressiste-conser...

 

「前田利広」とは別人です。 この存命人物の記事には検証可能な出典が不足しています。信頼できる情報源の提供に協力をお願いします。存命人物に関する出典の無い、もしくは不完全な情報に基づいた論争の材料、特に潜在的に中傷・誹謗・名誉毀損あるいは有害となるものはすぐに除去する必要があります。出典検索?: 前田俊博 – ニュース · 書籍&...

 

Multilingual book or manuscript For other uses, see polyglot (disambiguation). This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (July 2024) (Learn how and when to remove this message) Genoa psalter of 1516, edited by Agostino Giustiniani, Bishop of Nebbio A polyglot is a book that contains side-by-side versions of the same tex...

River in the United States of America Plotter Kill Nature ReserveTrail entrance signLength3 miles circular (4 miles total)LocationRotterdam (town), New York, USAUseRecreation and Natural HistoryDifficultyEasySeasonAll year roundSightsVariety of birds and other wildlifeHazardsHigh unstable cliff edges The Almy D. Coggleshall Plotter Kill Preserve is a 632-acre (256 ha) nature reserve and hiking area located on Route 159 in the town of Rotterdam, Schenectady County, New York State. Etymolo...

 

Neutron scattering technique Science with neutrons Foundations Neutron temperature Flux, Radiation, Transport Cross section, Absorption, Activation Neutron scattering Neutron diffraction Small-angle neutron scattering GISANS Reflectometry Inelastic neutron scattering Triple-axis spectrometer Time-of-flight spectrometer Backscattering spectrometer Spin-echo spectrometer Other applications Neutron tomography Activation analysis, Prompt gamma activation analysis Fundamental research with neutron...

 

Campionati italiani assoluti di atletica leggera 2022 Competizione Campionati italiani assoluti Sport Atletica leggera Edizione CXII Organizzatore FIDAL Lazio Date 24 - 26 giugno Luogo Rieti Discipline 42 + 2 Impianto/i Stadio Raul Guidobaldi Cronologia della competizione 2021 2023 Manuale I CXII campionati italiani assoluti di atletica leggera, si sono tenuti presso lo stadio Raul Guidobaldi di Rieti[1], dal 24 al 26 giugno 2022. I titoli di campioni italiani di marcia 35 km sono st...

Antonio II AcciaiuoliFonctionDucDuché d'Athènes1439-1441BiographieDécès 1441Activité Homme politiqueFamille Famille AcciaiuoliFratrie Nerio II AcciaiuoliEnfant Francesco II Acciaiuolimodifier - modifier le code - modifier Wikidata Antonio II Acciaiuoli (mort en 1441) est un duc d'Athènes de 1439 à 1441[1]. Antonio est le fils cadet de François Acciaiuoli (mort en 1420) et de Margareta Malpigli il grandit à Florence jusqu'à 1413, quand Antonio Ier, le cousin germain de...

 

American politician (1872–1937) This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (November 2021) (Learn how and when to remove this message) Joseph T. RobinsonSenate Majority LeaderIn officeMarch 4, 1933 – July 14, 1937DeputyJ. Hamilton LewisPreceded byJames Eli WatsonSucceeded...