פריסל
מתוך ויקיפדיה, האנציקלופדיה החופשית
פריסל (FreeCell) הוא משחק קלפים לשחקן יחיד, בדומה לסוליטייר. המשחק מזכיר בעקרונותיו את המשחק קלונדייק (שנכלל במערכת ההפעלה חלונות תחת השם "סוליטייר") אך נבדל ממנו בכך שאין למזל השפעה על תוצאת המשחק מעבר לחלוקת הקלפים הראשונית. עם זאת, לא כל המשחקים פתירים, ורמת הקושי משתנה ממשחק למשחק. המשחק פופולרי מאוד בזכות הכללתו במערכת ההפעלה חלונות.
תוכן עניינים |
[עריכה] חוקים
- יש לערבב חבילה בת 52 קלפים (ללא ג'וקרים) ולחלק את הקלפים לשמונה עמודות כך שכל הקלפים גלויים, אך רק הקלף התחתון בכל עמודה חשוף לחלוטין (חופשי). ארבע מן העמודות יכילו 7 קלפים ואילו ארבע נוספות רק 6.
- פרט לשמונה העמודות ישנם ארבעה תאים ריקים וארבעה תאי יסוד שכל אחד מהם מתאים לאחד מארבע סדרות הקלפים. מטרת המשחק היא להעביר את כל הקלפים לתאי היסוד תוך שימוש בתאים הריקים.
- ניתן להניע רק קלפים חופשיים, על פי הכללים הבאים:
- אם קיים תא ריק, ניתן להעביר אליו קלף. הקלף ממלא את התא ונותר גלוי.
- ניתן להעביר קלף לתא היסוד המתאים לסדרת הקלף שלו אם הקלף הנוכחי בתא היסוד הוא התא הקודם אליו בחבילה. הקלף הנמוך ביותר בחבילה הוא האס, וניתן להעביר אותו לתא יסוד ריק.
- ניתן להעביר קלף לאחת מהעמודות אם הוא שונה בצבעו מצבע הקלף החופשי בעמודה זו, ובמספרו הוא הקלף הקודם לו. את הקלף מניחים על הקלף החופשי כך שהוא נותר גלוי, והקלף שהונח הופך להיות הקלף החופשי של אותה עמודה.
- אם אחת העמודות התרוקנה, ניתן להעביר אליה כל קלף חופשי.
- לא ניתן להוציא קלף מערימת היסוד אם כבר הונח בה.
- המשחק מסתיים בניצחון אם כל הקלפים הונחו על ערימת היסוד. קיימת האפשרות שהשחקן "ייתקע" במשחק ויגיע למצב שממנו אין סיכוי לנצח.
[עריכה] היסטוריה
מקורו של משחק הפריסל במשחק בשם Eight Off שבו ישנם שמונה תאים חופשיים שארבעה מהם מכילים קלפים בתחילת המשחק, והקלפים מסודרים בעמודות על פי סדרתם, ולא על פי צבעים מתחלפים, ועמודה ריקה ניתן למלא רק עם מלך. ביוני 1968 תיאר מרטין גרדנר בטורו בעיתון Scientific American וריאציה על Eight Off שבה היו רק ארבעה תאים פנויים, ארבעת הקלפים שב-Eight Off חולקו לתאים הושמו במקום זאת על העמודות, וניתן להעביר לעמודה ריקה כל קלף ולא רק מלך. הוריאציה, שהומצאה בידי C.L. Baker, נקראת כיום Baker's Game.
את המשחק בצורתו הנוכחית המציא פול אלפיל, אשר שינה את המשחק של בייקר על ידי כך שבחר כי בניית העמודות תהיה על פי צבע מתחלף, ולא על פי סדרת הקלף, מה שהפך את המשחק לקל יותר וניתן לפתרון לעתים קרובות יותר. אלפיל גם כתב את הגרסה הממוחשבת הראשונה של המשחק בשנת 1978 עבור מערכת PLATO.
לפופולריות של המשחק אחראי ג'ים הורן, שכתב את הגרסה של המשחק לחלונות. המשחק נכלל לראשונה ב־Win32s אך לאחר מכן הוכלל גם בחלונות 95, ומאז הוכלל בכל גרסה של חלונות.
המשחק זכה לפופולריות בייחוד בקרב פקידים, זאת בעיקר הודות לעובדה שבחברות רבות אי-אפשר להתקין משחקים נוספים פרט לאלה הבאים עם חבילת הבסיס של חלונות (ובארגונים מסוימים אף אין גישה לאינטרנט ולמשחקי רשת). בישראל המשחק פופולרי מאוד בקרב פקידי צה"ל, כפי שעלה מסקר שערך עיתון "במחנה".
[עריכה] גרסאות ופתרונות
ישנם 52 עצרת סידורים שונים של חבילת הקלפים ועל כן בתאוריה זהו גם מספר המשחקים השונים (מספר זה הוא בערך 
) אך חלק מהערבובים מביאים למשחקים הדומים מאוד זה לזה פרט לסדר העמודות. למרות זאת, מספר המשחקים האפשריים הוא עצום.
בגרסת המשחק הראשונה של מיקרוסופט נכללו 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 הוכח כי מנקודת מבטה של תורת החישוביות המשחק הוא בעיה NP-שלמה (כתלות במספר הקלפים).[1] על כן, אלגוריתם שפותר משחק פריסל שרירותי במהירות יהווה פריצת דרך בחקר מדעי המחשב.
[עריכה] פותרים אוטומטיים
אחד מהתחביבים של מספר חובבי פריסל הוא לבנות תוכניות מחשב שיכולות לפתור את פריסל אוטומטית. דון וודס כתב פותר לפריסל ומספר משחקים דומים עוד ב1997-. פותר זה יותר מאוחר שוכלל על ידי וילסון קלן ואדריאן אטלינגר ושולב בתוך התוכנה "Freecell Pro" שלהם.
פותר אוטומטי ידוע נוסף הוא Patsolve של תום הולרויד. Patsolve משתמש במהלכים אטומיים ומאז גרסה 3.0 שילב פונקציית שקילה המתבססת על התוצאות של אלגוריתם גנטי שגרמה לפותר להיות מהיר בהרבה.
שלומי פיש התחיל לפתח פותר משלו במרץ 2000. פותר זה כונה פשוט "Freecell Solver" ("פותר פריסל" באנגלית). פותר זה ייחודי בכך שהוא משתמש במטה-מהלכים - קבוצות של מהלכים שמטרתן להשיג מטרה מסוימת.
גארי קמפבל כתב פותר עבור פריסל ל-DOS באסמבלר של x86. גודלו של פותר זה הוא 12 קילובתים והוא די מהיר. הוא פועל רק על סידורי הלוח של Freecell Pro.
הרשימה הכי מקיפה של פותרים אוטומטיים הידועה מכילה קישורים לפותרים אחרים. פותרים חדשים נכתבים באופן מתמיד כחלק מעבודות או פרויקטים של אוניברסיטאות.
[עריכה] קישורים חיצוניים
- FreeCell FAQ תשובות לשאלות נפוצות הנוגעות למשחק
- סקר: הצבא מכור ל"פריסל" (מתוך אתר "וואלה")
[עריכה] מקורות
1. ^Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
