הבלוג של גרי רשף

08/04/2010

איקס מיקס דריקס

Filed under: Uncategorized — תגיות: , — גרי רשף @ 20:59

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

נתחיל ביצירת טבלה T_Mazavim שתכלול את כל המצבים החוקיים האפשריים של הלוח:
1. בהנחה ש-X מתחיל, ההפרש בין מספר ה-X-ים וה-O-ים הוא לכל היותר 1.
2. כשמישהו מנצח או כשנוצר תיקו- עוצרים (לא יתכן ששני הצדדים מנצחים, למשל- שלושה X-ים בשורה העליונה ושלושה O-ים בשורה התחתונה).

With T1 As    --3 posible signs ("-" = empty)

(Select    '-' IMD

Union All

Select    'X' IMD

Union All

Select    'O' IMD),

T2 As

(Select    1 N,

        CAST(IMD As Varchar(9)) IMD,

        IMD IMD1,

        '-' IMD2,

        '-' IMD3,

        '-' IMD4,

        '-' IMD5,

        '-' IMD6,

        '-' IMD7,

        '-' IMD8,

        '-' IMD9,

        CAST(Null As SmallInt) As Tozaa

From    T1

Union All

Select    *,

        Case When 'XXX' In (IMD1+IMD2+IMD3,IMD4+IMD5+IMD6,IMD7+IMD8+IMD9,IMD1+IMD4+IMD7,IMD2+IMD5+IMD8,IMD3+IMD6+IMD9,IMD1+IMD5+IMD9,IMD3+IMD5+IMD7)

                Then Cast(1 As SmallInt) Else Cast(0 As SmallInt) End --X wins

        +Case When 'OOO' In (IMD1+IMD2+IMD3,IMD4+IMD5+IMD6,IMD7+IMD8+IMD9,IMD1+IMD4+IMD7,IMD2+IMD5+IMD8,IMD3+IMD6+IMD9,IMD1+IMD5+IMD9,IMD3+IMD5+IMD7)

                Then Cast(3 As SmallInt) Else Cast(0 As SmallInt) End --O wins

        +Case When IMD1+IMD2+IMD3 Like '%X%' And IMD4+IMD5+IMD6 Like '%X%' And IMD7+IMD8+IMD9 Like '%X%' And IMD1+IMD4+IMD7 Like '%X%' And IMD2+IMD5+IMD8 Like '%X%' And IMD3+IMD6+IMD9 Like '%X%' And IMD1+IMD5+IMD9 Like '%X%' And IMD3+IMD5+IMD7 Like '%X%'

                And IMD1+IMD2+IMD3 Like '%O%' And IMD4+IMD5+IMD6 Like '%O%' And IMD7+IMD8+IMD9 Like '%O%' And IMD1+IMD4+IMD7 Like '%O%' And IMD2+IMD5+IMD8 Like '%O%' And IMD3+IMD6+IMD9 Like '%O%' And IMD1+IMD5+IMD9 Like '%O%' And IMD3+IMD5+IMD7 Like '%O%'

                Then Cast(2 As SmallInt) Else Cast(0 As SmallInt) End --Equal

        Tozaa

From    (Select    T2.N+1 N,

                Cast(T2.IMD+T1.IMD As Varchar(9)) IMD,

                T2.IMD1,

                Case When N+1=2 Then T1.IMD When N+1>2 Then T2.IMD2 Else '-' End IMD2,

                Case When N+1=3 Then T1.IMD When N+1>3 Then T2.IMD3 Else '-' End IMD3,

                Case When N+1=4 Then T1.IMD When N+1>4 Then T2.IMD4 Else '-' End IMD4,

                Case When N+1=5 Then T1.IMD When N+1>5 Then T2.IMD5 Else '-' End IMD5,

                Case When N+1=6 Then T1.IMD When N+1>6 Then T2.IMD6 Else '-' End IMD6,

                Case When N+1=7 Then T1.IMD When N+1>7 Then T2.IMD7 Else '-' End IMD7,

                Case When N+1=8 Then T1.IMD When N+1>8 Then T2.IMD8 Else '-' End IMD8,

                Case When N+1=9 Then T1.IMD When N+1>9 Then T2.IMD9 Else '-' End IMD9

        From    T2,

                T1

        Where    N<9

                And Len(T2.IMD+T1.IMD)-Len(Replace(T2.IMD+T1.IMD,'X',''))<=5

                And Len(T2.IMD+T1.IMD)-Len(Replace(T2.IMD+T1.IMD,'O',''))<=4

                And IsNull(Tozaa,2) In (0,1,2,3)) T),

T3 As

(Select    *

From    T2

Where    IsNull(Tozaa,0) In (0,1,2,3)

        And Len(IMD)=9

        And (9-Len(Replace(IMD,'X','')))-(9-Len(Replace(IMD,'O',''))) In (0,1))

Select    *

Into    T_Mazavim

From    T3;

כעת ניצור את טבלת T_Ksharim שתכלול את הקשרים בין המצבים השונים, כלומר- בין מצב אפשרי של הלוח (IMD) למצבו הקודם (IMDp כאשר בדרך כלל יש לכל מצב כמה קודמים).

לכאורה הייתי יכול לעשות זאת במכה אחת ותוך כדי בניית המצבים הנ"ל לציין מה המצב הקודם, אולם זה גם יותר איטי וגם יוצר כפילויות רבות; ולכן במקום ליצור את המצבים בדרך של סימולציה של משחקים (X מתחיל ויש לו 9 אפשרויות, O ממשיך ויש לו 8 אפשרויות..) יצרתי צירופים חוקיים של (X O –) וכעת אנסה למצוא מי קשור למי:

Select    Mb.*,

        Ma.IMD IMDp

Into    T_Ksharim

From    T_Mazavim Ma

Inner Join T_Mazavim Mb

        On Case When Ma.IMD1=Mb.IMD1 Then 1 When Ma.IMD1='-' Then 0 Else 999 End

            +Case When Ma.IMD2=Mb.IMD2 Then 1 When Ma.IMD2='-' Then 0 Else 999 End

            +Case When Ma.IMD3=Mb.IMD3 Then 1 When Ma.IMD3='-' Then 0 Else 999 End

            +Case When Ma.IMD4=Mb.IMD4 Then 1 When Ma.IMD4='-' Then 0 Else 999 End

            +Case When Ma.IMD5=Mb.IMD5 Then 1 When Ma.IMD5='-' Then 0 Else 999 End

            +Case When Ma.IMD6=Mb.IMD6 Then 1 When Ma.IMD6='-' Then 0 Else 999 End

            +Case When Ma.IMD7=Mb.IMD7 Then 1 When Ma.IMD7='-' Then 0 Else 999 End

            +Case When Ma.IMD8=Mb.IMD8 Then 1 When Ma.IMD8='-' Then 0 Else 999 End

            +Case When Ma.IMD9=Mb.IMD9 Then 1 When Ma.IMD9='-' Then 0 Else 999 End=8

        And Ma.Tozaa=0;

כעת ליד כל מצב מופיעה אחת התוצאות הבאות:

0 – המשחק טרם הסתיים (התוצאה לא ידועה)

1- X ניצח

2- תיקו

3- O ניצח

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

לשם כך יש להיעזר בלולאה – שזו דרך מאוד לא אלגנטית בשעה שמדובר ב-SQL אך הכרח בל יגונה במקרה זה:

Declare    @RC Int;

Set        @RC=1;

While    @RC>0

        Begin

        Update T_Ksharim

        Set        Tozaa=Case When (9-LEN(Replace(IMD,'-',''))) In (1,3,5,7,9) Then Mn Else Mx End --MinMax algorithm

        From    T_Ksharim K

        Inner Join (Select    IMDp,

                            MIN(Tozaa) Mn,

                            MAX(Tozaa) Mx

                    From    T_Ksharim

                    Group By IMDp

                    Having    MIN(Tozaa)<>0) T

                On K.IMD=T.IMDp

        Where    K.Tozaa=0;

        Set        @RC=@@ROWCOUNT;

        End;

הלולאה מעדכנת בכל איטרציה את כל המצבים שאין להם תוצאה אך תוצאות מצבי ההמשך שלהם ידועות,

וחוזרת על כך עד שלא נותר מה לעדכן.

כעת ניגש למשחק, ובואו נניח שאנחנו מתחילים, ואנחנו שולפים מתוך טבלת הקשרים את כל המצבים שהמצבים הקודמים שלהם הם לוח ריק:

Select    *

From    T_Ksharim

Where    IMDp='---------'

כצפוי יש לנו 9 אפשרויות כיצד להתחיל וכולן מובילות לתיקו (תוצאה=2), ואנחנו נבחר ב-X בפינה השמאלית העליונה:

X

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

X
O

אנחנו שואלים בעצת המערכת:

Select    *

From    T_Ksharim

Where    IMDp='X--O-----'

מתברר שמבין 7 אפשרויות התגובה שלנו – 3 יובילו לנצחון (תוצאה = 1) ואנחנו בוחרים באחת מהן:

X
X O

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

X
X O
O

אבל אנחנו לא שומטים את הטרף מפינו:

Select    *

From    T_Ksharim

Where    IMDp='X--OX---O'

מתוך 5 האפשרויות הפתוחות בפנינו- 2 מובילות לנצחון ונבחר באחת מהן:

X X
X O
O

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

מובן שאם גם לו הייתה גישה לטבלה- הוא לא היה עושה את הטעות בתורו הראשון, והמשחק היה מסתיים בתיקו.

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: