פריסל

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

חוקים

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

היסטוריה

מקורו של משחק הפריסל במשחק בשם Eight Off שבו ישנם שמונה תאים חופשיים שארבעה מהם מכילים קלפים בתחילת המשחק, והקלפים מסודרים בעמודות על פי סדרתם, ולא על פי צבעים מתחלפים, ועמודה ריקה ניתן למלא רק עם מלך. ביוני 1968 תיאר מרטין גרדנר בטורו בעיתון Scientific American וריאציה על Eight Off שבה היו רק ארבעה תאים פנויים, ארבעת הקלפים שב-Eight Off חולקו לתאים הושמו במקום זאת על העמודות, וניתן להעביר לעמודה ריקה כל קלף ולא רק מלך. הווריאציה, שהומצאה בידי C.L. Baker, נקראת כיום Baker's Game.

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

לפופולריות של המשחק אחראי ג'ים הורן, שכתב את הגרסה של המשחק לחלונות. המשחק נכלל לראשונה ב־Win32s אך לאחר מכן הוכלל גם בחלונות 95, ומאז הוכלל בכל גרסה של חלונות.

המשחק זכה לפופולריות בייחוד בקרב פקידים, זאת בעיקר הודות לעובדה שבחברות רבות אי-אפשר להתקין משחקים נוספים פרט לאלה הבאים עם חבילת הבסיס של חלונות (ובארגונים מסוימים אף אין גישה לאינטרנט ולמשחקי רשת). בישראל המשחק פופולרי מאוד בבסיסי צה"ל העורפיים, כפי שעלה מסקר שנעשה בפורטל חש"ל בקרב משתמשי הצה"ל-נט, ה"אינטרנט" הצה"לי, ובו פריסל זכה ל-29% מהקולות, והביס את קלונדייק ("סוליטר") שקיבל 25% מהקולות (בסקר 32% מהנשאלים טענו שאינם משחקים במחשב בצבא).^[1]

גרסאות ופתרונות

ישנם 52 עצרת סידורים שונים של חבילת הקלפים ועל כן בתאוריה זהו גם מספר המשחקים השונים (מספר זה הוא בערך $\ 8.06\cdot 10^{67}$ ) אך חלק מהערבובים מביאים למשחקים הדומים מאוד זה לזה פרט לסדר העמודות. למרות זאת, מספר המשחקים האפשריים הוא עצום.

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

אחת התכונות של פריסל שהופכות אותו לפופולרי היא שבניגוד למשחקים דומים לו, כמעט כל משחק ניתן לפתרון מוצלח. בגרסאות המשחק של מיקרוסופט נטען כי "השערה לא מוכחת היא שכל משחק ניתן לפתרון". השערה זו איננה נכונה, כפי שניתן היה לראות באותה גרסה עצמה: כאשר ניסה השחקן לשחק את משחק מספר מינוס 1 הוא היה מקבל משחק בלתי פתיר. עם זאת, עדיין התעוררה השאלה האם 32,000 המשחקים "החוקיים" (בעלי מספרים בין 1 ו-32,000) של מיקרוסופט פתירים. במסגרת הניסיון לענות על שאלה זו התארגן פרויקט אינטרנט רב משתתפים לפתרון כל המשחקים ה"חוקיים", אשר הסתיים בשנת 1995. המשחק היחיד אותו לא הצליח איש לפתור היה משחק מספר 11,982. במימוש המתקדם יותר של פריסל בחלונות ישנם 1,000,000 משחקים. מתוכם 8 התבררו כבלתי פתירים: 11,982; 146,692; 186,216; 455,889; 512,118; 517,776; 781,948.

בשנת 2000 הוכח כי מנקודת מבטה של תורת הסיבוכיות הגרסה המוכללת של המשחק (Generalised Freecell) היא בעיה NP-שלמה (כתלות במספר הקלפים).^[2] על כן, אלגוריתם שפותר משחק פריסל מגודל שרירותי ביעילות (כלומר בסיבוכיות זמן פולינומית) יהווה פריצת דרך בחקר מדעי המחשב.

פותרים אוטומטיים

אחד מהתחביבים של מספר חובבי פריסל הוא לבנות תוכניות מחשב שיכולות לפתור את פריסל אוטומטית. דון וודס כתב פותר לפריסל ומספר משחקים דומים עוד ב-1997. פותר זה יותר מאוחר שוכלל על ידי וילסון קלן ואדריאן אטלינגר ושולב בתוך התוכנה "Freecell Pro" שלהם.

פותר אוטומטי ידוע נוסף הוא Patsolve של תום הולרויד.^[3] ‏Patsolve משתמש במהלכים אטומיים, ומאז גרסה 3.0 שילב פונקציית שקילה המתבססת על התוצאות של אלגוריתם גנטי שגרמה לפותר להיות מהיר בהרבה.

שלומי פיש^[4] התחיל לפתח פותר משלו במרץ 2000. פותר זה כונה פשוט "Freecell Solver" ("פותר פריסל" באנגלית).^[5] פותר זה עושה שימוש במטה-מהלכים - קבוצות של מהלכים שמטרתן להשיג מטרה מסוימת.

גארי קמפבל^[6] כתב פותר עבור פריסל^[7] ל-DOS בשפת סף של x86. גודלו של פותר זה הוא 12 קילובתים והוא די מהיר. הוא פועל רק על סידורי הלוח של Freecell Pro.

חלק מהפותרים הללו ופותרים אחרים שולבו בתוך תוכנות פריסל וסוליטייר גדולות יותר. כך למשל, FreeCell Pro, מימוש הסוליטייר המשופר של אדריאן אטלינגר ווילסון קלן (בעבר תוכנה חינמית, ללא קוד המקור, אך מאוחר יותר הקוד נהיה זמין תחת הרישיון הציבורי הכללי של גנו (GPL) החופשי ופתוח הקוד) בהתחלה שילב את הפותר של דון וודס^[8] ומאוחר יותר שילב את הפותרים של פיש ושל הולרויד.^[9] PySolFC שילב את הפותר של פיש,^[10] עבור פריסל ומשחקים דומים אחרים שהפותר תומך בהם, בעוד ש-KPatience, גרסת משחקי הסוליטייר של KDE, שילבה בהתחלה את Freecell Solver אבל יותר מאוחר עברה לגרסה של Patsolve ששונתה באופן ניכר.^[11]

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

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

מדיה וקבצים בנושא פריסל בוויקישיתוף

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

הערות שוליים

^ אביעז רנד, במחנה, פריסל שולט בצה"ל, באתר nrg‏, 12 בספטמבר 2004
^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
^ http://members.tripod.com/professor_tom/
^ דף הבית של שלומי פיש
^ דף הבית של Freecell Solver
^ http://www.numin8r.us/gdc.htm
^ FFA: A World Class Freecell Player and Solver
^ Keller, Michael (1 בנובמבר 2010). "FreeCell -- Frequently Asked Questions (FAQ)". SolitaireLaboratory.com. {{cite web}}: (עזרה)
^ Adrian, Ettlinger (December 8, 2001). "FC-Pro policy". Freecell Solver Discussion. http://tech.groups.yahoo.com/group/fc-solve-discuss/message/198. Retrieved March 5, 2011.
^ Fish, Shlomi. "Programs that use Freecell Solver". Fc-solve.berlios.de. נבדק ב-5 במרץ 2011. {{cite web}}: (עזרה)
^ Kulow, Stephan (6 בנובמבר 2006). "Horrible News!!". Coolo's Blog via KdeDevelopers.org. אורכב מ-המקור ב-2011-03-23. נבדק ב-5 במרץ 2011. {{cite web}}: (עזרה)

[1] אביעז רנד, במחנה, פריסל שולט בצה"ל, באתר nrg‏, 12 בספטמבר 2004

[2] Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.

[3] ttp://members.tripod.com/professor_tom/

[4] דף הבית של שלומי פיש

[5] דף הבית של Freecell Solver

[6] ttp://www.numin8r.us/gdc.htm

[7] FFA: A World Class Freecell Player and Solver

[FCFAQ-8] Keller, Michael (1 בנובמבר 2010). "FreeCell -- Frequently Asked Questions (FAQ)". SolitaireLaboratory.com. {{cite web}}: (עזרה)

[9] Adrian, Ettlinger (December 8, 2001). "FC-Pro policy". Freecell Solver Discussion. http://tech.groups.yahoo.com/group/fc-solve-discuss/message/198. Retrieved March 5, 2011.

[10] Fish, Shlomi. "Programs that use Freecell Solver". Fc-solve.berlios.de. נבדק ב-5 במרץ 2011. {{cite web}}: (עזרה)

[11] Kulow, Stephan (6 בנובמבר 2006). "Horrible News!!". Coolo's Blog via KdeDevelopers.org. אורכב מ-המקור ב-2011-03-23. נבדק ב-5 במרץ 2011. {{cite web}}: (עזרה)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]