>> [השמעת מוסיקה]
>> דובר: ברוכים שבים, כולם.
זה CS50.
והיום, יש לנו הרבה דברים מעניינים לדבר עליו.
ראשית, אם כי, אני צריך להזכיר ל לך על כמה דברים מנהליים.
שבוע זה הוא חידון אחד, יום רביעי או לסעיף ייל
בימי שלישי וחמישי, ביום חמישי.
יש ביקורות חידון ערב באוניברסיטת ייל, 5:30-07:00.
בהרווארד, הם רשמו אתמול אחד.
וכל אחד יכול לצפות באינטרנט ש.
>> כמו כן, שבוע או בתחילת השבוע הבאה, יש לנו הרצאת CS50 האחרונה שלנו.
[גניחות] אני יודע.
זה הגיע כל כך מהר.
הסטודנטים באוניברסיטת ייל יהיו חי להרצות כאן בבית הספר למשפטים
אולם ביום שישי.
יהיה עוגה.
הסטודנטים באוניברסיטת הרווארד יהיו לי ההרצאה האחרונה בסנדרס ביום שני.
תהיה גם עוגה.
>> כמו כן, השבוע ביום שישי, למי מכם שמגיעים לניו הייבן,
יש לנו אקספו CS50.
יש לנו יותר מ -30 קבוצות שונות רשומות
כדי להראות לך כל מה ש ממפרשיות אוטונומיות,
למערכות שמזהים דיוקנאות דיגיטליים, למחשב
מוסיקה ומוסיקה בייצור מחשב.
אז אנא הצטרף אלינו.
אני חושב שזה הולך להיות זמן נהדר.
>> היום, אם כי, אנו מקבלים ל תמשיך לדבר על AI,
על בינה מלאכותית.
ואחד הדברים ש אנחנו הולכים לקבל היום ל
הוא את הרעיון של איך להשתמש AI כדי לפתור את הבעיות.
עכשיו, כמו תמיד, בואו נתחיל עם משהו פשוט.
ואנחנו הולכים להתחיל עם רעיון פשוט.
וזה באמצעות חיפוש.
>> אז דמיינו לרגע שאני יש משימה שאני צריך לבצע.
ואני רוצה שאהיה לי משימה ש אוטומטי על ידי כמה סוכן תוכנה.
תארו לעצמכם שאני מנסה להזמין סט טיסות מ, נניח, בוסטון
לסן פרנסיסקו.
אני יכול לעבור ואני יכול להשתמש אחד החיפוש המקוון הנפלא
כלים, שהוא הולך לעשות בעצם אותו דבר התהליך שאנחנו
הולך לעבור היום.
אבל אם אתה לא צריך ש כלי, מה היית עושה?
>> ובכן, אתה יכול להסתכל ו לראות ואומרים, אני בבוסטון.
מה טיסות זמינות לי?
עכשיו, אולי יש לי שלוש טיסות מבוסטון אפשריות
שיתאים את הזמן כאשר אני צריך לעזוב.
אני יכול לטוס לשיקגו.
או שאני יכול לטוס למיאמי.
או שאני יכול לטוס לניו יורק.
אז אני יכול להסתכל מ אחת ערי יעד אלה
ולחשוב על מקומות מה אולי אני יכול להגיע
מכל אחת מהערים בודדות אלה.
>> אז אולי משיקגו, אני יכול לקבל טיסה ישירה לסן פרנסיסקו.
זה מצוין.
או שאני יכול להשיג טיסה לדנבר.
עכשיו, אולי כי טיסה לסן פרנסיסקו הוא הפתרון המושלם עבורי,
אבל אולי לא.
אולי אני מחפש משהו זה קצת זול יותר
או קצת יותר טוב ללוח הזמנים שלי.
וכדי שאוכל לחפש מה אחר אפשרויות עשויות להיות שם בחוץ.
אז אני יכול להסתכל על דנבר.
ומדנוור, טוב, אולי אני יכול להשיג טיסה לאוסטין.
ומאוסטין, אולי אני יכול לקבל טיסה לפניקס, ומפניקס
לסן פרנסיסקו.
עכשיו, אני לא עשיתי עדיין.
כי אולי יש טיסה ישירה מניו יורק
לסן פרנסיסקו זה מושלם בשבילי.
או אולי יש טיסה ממיאמי דרך דנבר זה הרבה יותר זול.
אז אני עדיין צריך ללכת.
ואני עדיין צריך להסתכל על כל אלה ערים שלא נחקרו עדיין.
אני צריך לבדוק ביסודיות את כל האפשרויות שאולי יש לי.
>> אז מניו יורק, אולי אני יכול לקבל טיסה לנאשוויל, ומנשוויל
לאוסטין.
ואז אני יודע איפה אני.
ואז אני יודע מאוסטין, שאני יכול לטוס לפניקס, ומפניקס
לסן פרנסיסקו.
אם אני טס ראשון למיאמי, אם כי, אולי אני יכול להשיג טיסה ממיאמי
לנשוויל, או ממיאמי לאוסטין.
>> ועכשיו אני כבר ניסיתי את כל של האפשרויות.
אני כבר בניתי את הגרף הזה ש מראה לי את כל המסלולים האפשריים
כי יכול להיות שאני מסוגל לקחת.
כאשר אנו מייצגים אלה מיני בעיות,
אנחנו לא מתכוונים לייצג שלהם במפורש כגרף הזה,
כי הגרף שאינו מייצג ההיסטוריה שלנו שבו עברו.
בידיעה שטסתי מ פניקס לסן פרנסיסקו
לא אומר לי אם אני בא דרך נאשוויל, או באמצעות דנבר, או באמצעות מיאמי.
>> אז מה אני אעשה במקומו אני אקח את אותה בעיה זו,
ואני מייצג אותו כעץ.
ובשורש של העץ, ב עליון, אני אשים את המקום שהתחלתי,
בוסטון.
ומבוסטון, אני אסתכל על כל המיקומים האפשריים
שאני יכול לנסוע ל.
ובכן, במקרה זה, היה לי שלושה, שיקגו, ניו יורק, ובמיאמי.
ואז אני לחקור כל אחד מ ילדים אלה בעץ.
>> משיקגו, שראיתי כי היה לי שתי טיסות.
אני יכול לטוס ישירות ל סן פרנסיסקו או לדנבר.
עכשיו סן פרנסיסקו, שהמטרה שלי.
זה היעד שלי.
זה הולך להיות עלה של העץ הזה.
כלומר, אני לא מתכוון ללכת איפשהו אחרי סן פרנסיסקו.
מדנבר, אם כי, אני יכול לעוף מדנבר
לאוסטין, מאוסטין לפניקס, ומפיניקס לסן פרנסיסקו.
ועכשיו שוב, אני כבר הגעתי לעלה.
>> אז אני יכול לחזור לבא עיר שלא חקרתי באופן מלא.
זה יהיה ניו יורק, ללכת בחזרה לראש העץ שלי,
לרדת לניו יורק.
מניו יורק, אני יכול לטוס ל נאשוויל, מנשוויל לאוסטין,
מאוסטין לפניקס, ו מהפניקס לסן פרנסיסקו.
ולבסוף, אני עיר אחת לא הסתכל על עדיין, מיאמי.
>> ובכן, ממיאמי אמרתי לי שני אפשרויות, נאשוויל או אוסטין.
אם אני טס לנשוויל, גם אז אני טס מנשוויל, לאוסטין, לפניקס,
לסן פרנסיסקו.
אם אני טס לאוסטין, אני טס אוסטין, לפניקס, לסן פרנסיסקו.
ועכשיו יש לי עץ.
זה עץ מלא.
זה כל האפשרויות ו כל הנתיבים שאני יכול לקחת.
כלומר, אם אני מתחיל ב שורש של העץ בראש
ואני יורד לאחד מ עוזב, זה אומר לי לא רק
לאן אני הולך ל בסופו של, סן פרנסיסקו,
אבל זה אומר לי את המסלול ש אני צריך לקחת כדי להגיע לשם.
>> עכשיו, שאחד מהם הוא הטוב ביותר?
ובכן, שום דבר על זה בעיה עדיין אומרת לי
אשר מהם הוא הפתרון הטוב ביותר.
אולי אכפת לי הכי הרבה על כמה זמן אני באוויר,
או המרחק שאני טס.
במקרה זה, שיקגו סאן פרנסיסקו עשויה להיות המספר הקצר ביותר
קילומטרים באוויר.
>> אולי אכפת לי עלות.
וכולנו יודעים טיסות ישירות הם בדרך כלל יקר יותר.
אז אולי אם אני אקח את זה סוג של מסלול אחורה
דרך מיאמי, נאשוויל, אוסטין, פניקס, אולי אז
אני מקבל מחיר נמוך יותר.
אבל אני יכול לייעל בכל קריטריונים שאכפת לי.
למי יש הכי טוב ב טיסת Wi-Fi, או ש
יש שדות תעופה את האוכל הטוב ביותר זמינה.
וכל אחד מאלה עשויים תן לי פתרון אחר
שאני רואה כטוב ביותר.
>> אלו סוגים של בעיות, לאן אנחנו הולכים
לבנות את העץ הזה של אפשרויות, ולאחר מכן
מסתכל על כל אחד מאלה נתיבים בודדים, ולבחון
אשר ממלא של אלה קריטריונים לנו,
אנחנו הולכים לקרוא בעיות חיפוש.
ויש לנו המון אלגוריתמים, שחלקם
ראינו כבר, ללכת ולחקור עצים אלה.
אנחנו יכולים לעשות את זה בדרך שאני רק עשה, אלגוריתם חיפוש לעומק,
יורד ככל שאנחנו יכולים עד ש פגע עלה, ולאחר מכן חוזר למעלה,
והולך ימינה בחזרה למטה.
או שאנחנו יכולים לעשות את מה ש נקרא חיפוש רוחב-ראשון.
אנו יכולים להרחיב את הכל בחלק העליון, ולאחר מכן
קו אחד הכל מתחת ש, ולאחר מכן
הכל שורה אחת מתחת ש.
אלה עצי החיפוש הם יסוד לAI.
אבל הם לא ממש מקבלים זה נכון בכל הזמן.
למעשה, בהרבה מהמקרים שבאמת אכפת,
אנחנו רוצים לבנות עץ, אבל אנחנו לא ממש
תקבל להפוך את כל ההחלטות.
>> אלה הם מצבים שנקראו חיפוש יריב, הידוע גם
כאיך לכתוב נגינת משחק מערכות ולקבל תשלום עבור זה.
אבל אלה הם הסוגים מערכות שבו אני
אולי יכול לבחור כשאני הולך מ בוסטון, שעיר שאני הולך לצד.
אבל אחרי ש, מישהו אחר עלול לקבל כדי לקבל את ההחלטה על איפה אני טס.
אז לבנות אלה מבני סוגים, אנחנו
תצטרך לקחת מעט גישה שונה לזה.
אנחנו לא הולכים להיות מסוגלים רק לחפש דרך העץ
יותר, כי אנחנו לא אחד שהוא בשליטה
של כל אחד מנקודות אלה החלטה.
>> אז בואו נדמיין פשוט משחק כמו איקס-מיקס-דריקס.
אני יכול להתחיל עם לוח ריק לחלוטין.
ובאיקס עיגול, X מקבל לשחק ראשון.
וכדי שאוכל לחשוב על כל מהלכים אפשריים שX יכול לעשות.
ואם אני משחק אחד X, זה נהדר.
יש לי תשע אפשריים נע שאני יכול לעשות.
אני יכול לשים X בכל אחד של תשע עמדות אלה.
>> ואז מכל אחד מאלה, אני יכל לדמיין מה יקרה עכשיו.
ובכן, במקרה זה, אחר שחקן יקבל לקחת תור.
O יקבל לקחת תור.
ומכל אחד מאלה, יש יהיו שמונה מקומות שונים
O שיכול למקם את הסמן שלהם.
>> נניח שהחלטתי שאני היה הולך לשים X במרכז.
שתמיד נראה כמו מהלך פתיחה טוב.
אני יכול להסתכל על מתחת כי, שמונה מהלכים אפשריים שO עושה.
עכשיו, אם אני משחק X, זה נפלא.
אני יכול לבחור לי שאחד ללכת, אחד באמצע.
אבל עכשיו O מקבל לבחור.
ואין לי שליטה על החלטה זו.
>> אבל מכל אחד מאלה עמדות לוח אפשריות,
יש אז עוד סט של אפשרויות.
כשזה מגיע ללהיות שלי לפנות שוב, הייתי עושה
מקבל לבחור ואומרים, טוב, אם O עובר ל, גם,
נקודת אמצע בצד השמאל, ולאחר מכן יש לי קבוצה של אפשרויות
איפה אני יכול לקחת את הצעד הבא שלי.
מאלו, אני יכול לשקול את כל האפשרויות מתחתיהם.
ולאחר מכן יקבל O לבחור בין אלה.
>> ואני יכול לשמור על בנייה זו עץ החוצה עד שהגעתי לנקודה
שבו או שמישהו זוכה game-- זה
יש להיחשב עלה node-- או הלוח מלא לחלוטין
ואף אחד לא זכה.
וזה גם הולך להיות צומת עלה.
זה הולך להיות עניבה.
>> אבל הדבר מסובך עם זה אם זה היה רק ​​חיפוש רגיל
בעיה, אני רוצה להיות מסוגל למשל, גם, X צריך ללכת כאן.
וO צריך ללכת בדרך לשם.
ואז X צריך ללכת לכאן.
ואז O צריך ללכת בדרך לשם.
ואז X יכול לקבל שלוש בשורה, ואני מנצח.
והמשחק יהיה מעל בחמישה מהלכים, שלוש בשבילי,
שני ליריב שלי.
אבל אני לא תמיד יכול לבחור ש.
>> אז במקום, מה שאנחנו אצטרך לעשות
הוא שאנחנו הולכים יש לי יש אסטרטגיה חדשה.
והאסטרטגיה ש אלגוריתמים לנצחון במשחק לעתים קרובות להשתמש ב
הוא מה שנקרא minimax.
הרעיון של המרכז minimax הוא שאנחנו
הולך להרים את המהלך שנותן היריב שלנו הסט הגרוע ביותר
מהלכים שהם יכולים לעשות.
זה לא עושה לי טוב כל לבחור מהלך שבו
יכול להיות שאני מסוגל לנצח אחרי כי, משום שהיריב שלי הוא לא
הולך לתת לי הזדמנות ש.
הם הולכים לבחור כמה תוצאה נוראה בשבילי.
אז אני הולך לעשות להעביר שמאלץ את היריב שלי
לעשות משהו טוב יותר עבורי.
בסדר.
בואו לראות איך שמשחק.
אז הנה האלגוריתם שלנו בפסאודו קוד.
אנחנו הולכים ליצור עץ המשחק כולו.
אנחנו הולכים לבנות המבנה כולו.
ואז נלך דרך.
ובתחתית מאוד בכל אחד מ בלוטות מסוף, בכל אחד מהעלים,
אנו להעריך כיצד יקר הוא לי את זה?
ואנחנו הולכים לדברים ערך ש טובים בשבילי כמו להיות חיובי.
דברים שהם לא טובים בשבילי יהיה פחות חיובי, או אפס,
או אפילו שלילי.
>> אז באיקס עיגול, אולי נצחון בשבילי הוא טוב.
זה אחד.
ועניבה היא אפס.
ומשהו שהפסד ל שלי, אולי זה אחד שלילי.
כל מה שמשנה הוא שיותר טוב זה בשבילי, גבוה יותר הציון
הוא מקבל.
מאלו אפשרויות ב תחתון, אז לסנן כלפי מעלה.
וכאשר זה הסיכוי שלי לבחור בין סט של חלופות,
אני אבחר אחד זה קיבלתי את הציון הגבוה ביותר.
>> ובכל פעם שזה שלי מתנגדים לפנות ללבחור,
אני מניח שהם הולכים לבחור אחד עם הציון הנמוך ביותר.
ואם אני עושה את זה כל הדרך עד לחלק העליון של העץ,
אני בחרתי בדרך שנותנת לי שלי את התוצאה הטובה ביותר שאני יכול לקבל,
בהנחת שהיריב שלי עושה את כל המהלכים הנכונים.
>> בסדר, אז בואו לראות בפעולה זו ראשונה.
ואז אנחנו בעצם מסתכל על הקוד לזה.
אז דמיין שיש לי העץ הגדול הזה.
ועכשיו אני לא משחק איקס עיגול.
אני רוצה לתת לך משהו קצת יותר עשיר.
אז יש לי כמה משחק שבו יש עשרות רבים ושונים
שיש לי יכולים בסופו של הדבר.
וכך אני בונה עץ מלא זה.
ואני מקבל להעביר ראשון.
אני בשורש של העץ.
>> ואני יכול לבחור לראות-- כך אני מקבל על מנת למקסם את רוחב שהצומת הראשונה.
ואז היריב שלי מקבל ללכת.
ואז אני מקבל ללכת שוב.
אז למטה בתחתית, יש לי קבוצה של אפשרויות שאני יכול לבחור,
מדינות מסוף שונות של המשחק.
אם אני למטה שב כה פינה שמאלית,
ואני רואה שיש לי בחירה בין שמונה, שבע, ושתי,
טוב, אני אחד שמקבל לבחור.
אז אני הולך לבחור אחד הטוב ביותר של אלה.
אני הולך לבחור שמונה.
>> אז אני יודע שאם אני אי פעם לרדת לנקודה ש,
אני אהיה מסוגל לקבל את זה שמונה נקודות.
אם אני בסופו של בנקודה הבאה מעל, את הצומת הסמוכה,
תשע, אחד, או שש, טוב, אני הולך לבחור את הטוב ביותר של אלה.
אני אבחר תשע.
אם יש לי בחירה בין שני, וארבעה, ואחד,
אני אבחר ארבעה, הגבוה ביותר.
>> עכשיו, אם אני מסתכל על הרמה מעל זה, היריב שלי
הוא אחד מקבל לעשות את הבחירה ש.
אז היריב שלי מקבל ל לבחור, אני רוצה לתת לו
הדבר שקורה כדי להשיג אותו שמונה נקודות,
או שאני נותן לו את הדבר זה הולך לתת לו תשע נקודות,
או הדבר שקורה לתת לו ארבע נקודות?
והיריב שלי, להיות רציונלים, הוא הולך
לבחור את המינימום של אלה, הולך לבחור את ארבעה.
>> ואני יכול לעשות את זה דרך כל העץ.
אני יכול לרדת של סט אמצע שלוש.
ואני יכול לבחור בין אחד, שלוש, חמש ו.
ואני יכול לבחור.
אז אני בוחר חמש.
אני יכול לבחור שלוש, תשעה, או שתיים.
אני יכול לבחור, אז אני בוחר את תשע.
שש, חמש, או שתיים, אני בוחר.
אני יכול לבחור את שש.
רמה מעל זה, שמקבל לבחור?
מי מקבל לבחור?
הבחור השני, היריב שלי.
אז הם בוחרים חמש, תשע, או שש, איזה מהם?
>> קהל: חמש.
>> דובר: הם בוחרים את חמש.
הם יכולים לבחור את המינימום.
ולאחר מכן עבר אחד, לבחור אחד, שתיים, או שלושה.
אני יכול לבחור, אז אני בוחר שלוש.
תשע, שבע, או שניים, אני בוחר תשע.
ו -11, שש, או ארבעה, אני בוחר 11.
היריב שלי ולאחר מכן בוחר שלושה, תשע, או 11, בוחר את המינימום.
הוא נותן לי שלוש.
ולבסוף בחלק העליון של העץ, אני יכול לבחור שוב.
ואני יכול לבחור בין ארבעה, חמש, או שלוש.
אז אני לוקח את חמש.
>> אם יש לי לשלוט בכל דבר, לא הייתי לי לקחת את הנתיב שהוביל ל11.
אבל אני לא מקבל לעשות את הבחירה ש.
אם אני הולך במורד השביל ש.
היריב שלי יכריח אותי ל הבחירה שמובילה לשלושה.
אז הוא הטוב ביותר שאני יכול לעשות לקחת את זה סניף אמצע,
לעשות את הבחירה זה סופו של דבר הולך להוביל אותי לחמש נקודות.
זה מה שעושה minimax.
>> בסדר.
בואו נסתכל על זה.
אז הנה בCS50 IDE הוא תכנית ש
מיישם minimax לשחק איקס עיגול.
אנחנו הולכים לבנות עד ייצוג.
אנחנו הולכים לשתי opponent-- או שני שחקנים, המחשב שלנו
שחקן ושחקן אנושי.
מספר שחקן אחד יהיה משחק O. זה יהיה שחקן המכונה.
הם מקבלים לנוע שני.
והשחקן האחר, שחקן אנושי, יהיה X.
>> וכדי לעשות את החיים שלי פשוט קצת, אני הולך
תווית ששחקן אחד שלילי.
אז אני יכול רק להכפיל על ידי שלילי אחד כדי להחליף
בין שחקן אחד ואחר.
בסדר, אז בואו נסתכל מה אנחנו בעצם הולכים לעשות.
אנחנו הולכים להגדיר הלוח שלנו.
זה הולך להיות, ובכן, אנחנו הולכים כדי לאפשר לו להיות שלוש על ידי שלוש,
או שאנחנו יכולים אפילו לשחק חמישה על ידי חמש או שבע
על ידי שבעה-מיקס-דריקס טיק אם היית כמו, המבוסס על כמה ממד ד
>> ויהיה לנו זוג פונקציות עוזר
שיעשה דברים כמו לאתחל את screen-- או מצטער,
לאתחל משתנינו, לנקות את מסך, לצייר הלוח על המסך,
אחד שבודק לוח לראות או לא
יש זוכה, אחד ש מנתח דרך שורת הפקודה,
רק כדי לעזור, אחד שקורא ב קלט, ותפקיד אחד בשם minimax.
וזה אחד אנחנו אכפת ביותר על.
אבל בואו נסתכל ראשון בעיקרי.
>> מה אנחנו עושים?
ובכן, אנחנו הולכים לנתח את שורת הפקודה שלנו,
פשוט לקרוא ולראות מה ממד לוח שהיינו רוצה להיות.
אנחנו לאתחל הלוח שלנו.
ואז נכנסים אחד לולאה פראית גדולה, שוב ושוב
קיבל מהלכים עד המשחק הוא זכה, או שאין מהלכי שמאל.
בכל פעם שאנו עוברים ש לולאה, אנחנו לנקות את המסך.
אנחנו לצייר את הלוח על המסך.
ואנחנו בכוונה סוג של הפשטה אלה משם כמו שגרות,
כך שאנחנו לא צריכים לדאוג יותר מדי על הפרטים של איך שהם קורים.
>> יהיה לך את הקוד מאוחר יותר היום.
ואם אתה רוצה להסתכל דרך ולברר, אתה יכול לראות את כולם.
אבל אנחנו לצייר לוח על המסך.
ולאחר מכן נבדוק ו רואה, יש לנו מנצח?
האם מישהו ניצח את המשחק הזה?
אם יש להם, אנו נדפיס את הודעת נצחון.
ואנחנו בסופו של המשחק.
>> אנחנו גם נבדוק ו לראות אם יש עניבה.
זה יהיה קל לראות אם יש עניבה.
זה אומר שכל החללים מלאים, אבל יש לא היה זוכה עדיין.
אנחנו יכולים להכריז על עניבה ולעשות.
אז meat-- האמיתי אם זה שחקן מכונה,
אנו נאפשר ש שחקן מכונה כדי לחפש
באמצעות שימוש באלגוריתם minimax זה, כדי למצוא את המהלך הטוב ביותר שהוא יכול.
ואז לשים את זה צעד למעלה.
>> אחרת, אם זה שחקן אנושי, אנחנו קראנו כמה קלט מהאדם.
ואז אם זה האדם שחקן או שחקן המכונה,
אנחנו נעשה את זוג קטן ביטים של בדיקת שגיאות,
לוודא שזה יישאר בתוך הגבולות של הממדים האמיתיים של הלוח
שיש לנו, לוודא שהמרחב שהוא ריק,
שהמכר של אף אחד חתיכה שם כבר.
ואז אנחנו פשוט לשים חתיכה, על הלוח
לשנות את השחקן לשכבה הבאה, ו להגדיל כמה מהלכים שקרו.
>> זה הלולאה העיקרית ל משחק איקס העיגול שלנו.
Minimax, אם כן, הוא בדיוק האלגוריתם שלפני.
ההתאמה היחידה ש שעשינו כדי ש
יכול לשחק גבוה יותר לוחות ממדיים הוא שיש לנו
המשיך פרמטר הנוסף הזה שנקרא עומק.
ועומק רק אומר, אם אני חיפוש כלפי מטה דרך העץ ש
ואני מקבל כל כך רחוק למטה מעבר לכמה עומק רמה
כי אני פשוט לא רוצה ללכת יותר,
אני הולך להפסיק ופשוט להעריך את הלוח בשלב זה.
אני אבדוק ותראה אם ​​יש זוכה.
אם יש מנצח, אני להחזיר אותם.
אחרת, אני אלך דרך לולאה.
ואני אומר, לכל מיקומים האפשריים
כי מה שיכולתי לקחת כמהלך שלי, אני
לבנות לוח היפותטי ש כולל מהלך שלי על לוח ש,
ולאחר מכן באופן רקורסיבי קורא minimax.
>> אם זה המהלך שלי, אני מקבל כדי למצוא את אחד שיש לי הציון הגדול ביותר.
אם זה המהלך של היריב שלי, אנו מוצאים אחד שיש לי ציון המינימום.
וכל דבר אחר שמירה רק שיא.
בסדר, אז בואו לראות טווח זה.
בעצם, אולי אנחנו יכולים לקבל כמה מתנדבים
לבוא ולשחק איקס עיגול.
[לא ברור] אחד, ואחד יותר, שתי, ממש שם.
בואו למעלה.
>> אז בואו נלך קדימה ו הפעל מחדש לחלוטין זה.
אז, היי.
>> קהל: היי.
>> דובר: מה שמך?
>> קהל: Gorav.
דובר: Gorav.
>> קהל: אני לילה.
>> דובר: ולילה, ולילה, מצטער.
בואו למעלה.
Gorav, אנחנו הולכים יש לך ללכת ראשון.
ואני הולך לשאול אותך להיות לא שחקן איקס עיגול טוב מאוד.
אוקיי, אז כל הלחץ הוא אותך.
תן לי נראה, שהמכונה שלנו שחקן באמת יכול לעשות משהו חכם.
אז קדימה.
אתה הולך להקליד בי לתאם אתה רוצה לשים X שלך ב.
A0, אישור, והמכונה עברה מייד והטביע את חותמו בA1.
>> שים O על הלוח.
בסדר, עכשיו קדימה.
לאן תרצה ללכת?
C2.
שחקן המכונה שלנו לקח כיכר האמצע, חסמה אותך.
אז זה היה טוב, דבר חכם לזה לעשות.
שחסמת אותו.
זה מצוין.
זה לוקח הפינה שם.
>> וזה הולך להכריח אותך לקחת את החלל האחרון, B0.
והמשחק מסתיים בתיקו.
אבל זה שיחק סביר משחק נגדך, נכון?
בסדר, תודה רבה, Gorav.
>> [תְשׁוּאוֹת]
>> בסדר, הלילה, אנחנו הולכים את המשחק עליך כאן.
>> קהל: הו, נהדר.
>> דובר: אנחנו הולכים לתת לי אתה ארבעה על ארבעה-מיקס-דריקס טיק.
עכשיו, בארבעה על ארבעה, אתה צריך לנצח עם ארבע בשורה, לא שלוש ברציפות.
וזה כולו שלך.
אז לקח את הלילה D1.
עכשיו אנחנו הולכים למעקב שחקן המחשב שלנו כאן.
שלושה על ידי שלושה-מיקס-דריקס טיק הוא הסוג של דבר כי הוא קל לכולנו.
אבל זה עדיין נחמד לראות שחקן מחשב לבצע מהלכים חכמים.
ארבעה על ארבעה מקבלים ל להיות קצת יותר מסובך.
>> נעשה באופן יפה.
בסדר, אז הלילה של סיימו.
אה, והיינו צריכים הסתיימו שם.
אבל בואו נעשה עוד אחד עד כאן.
אז הלילה, תודה.
נעשה באופן יפה.
>> [תְשׁוּאוֹת]
>> אז שחקן איקס העיגול שלנו הולך דרך ומקומות מוצא,
פותר אותם באמצעות minimax זה.
והיה לי הגדרת עומק שבכך שהוא
לא לרוץ מהר מדי, וזו כנראה הסיבה
הלילה היה מסוגל ללכת יפה קדימה כפי שהיא עשתה, ועשתה טובה מאוד.
אבל מערכות שרק אלה לעבור וכוח הזרוע
ללכת עמוק יותר, ועמוק יותר, ועמוק יותר, ולשמור על מציאת הפתרון
שהם צריכים, אלו סוגים של מערכות הם מוצלחים למדי באלה, טובים,
משחקי לוח סטנדרטיים.
>> ולמעשה, אם אנחנו מסתכלים על שלוש על ידי שלושה משחק איקס עיגול,
זה בעצם בעיה נפתרה.
וזה תרשים נפלא מרנדל מונרו בXKCD,
מראה שאתה צריך לעבור לקחת, נתן המהלכים של היריב שלך.
זה משהו שאנחנו יכולים בקלות לציין מראש.
אבל מה קורה כפי שאנו מקבלים יותר משחקים מורכבים, משחקים מורכבים יותר,
שבו יש לוחות גדולים יותר, יותר אפשרויות, אסטרטגיה עמוקה יותר?
>> מתברר שזה בכוח הזרוע חיפוש עדיין
עושה טוב באופן סביר, למעט כאשר אתה מגיע לנקודה
שבו העץ שהוא כל כך גדול כי אתה לא יכול לייצג את כל זה.
כאשר אתה לא יכול לחשב את כל העץ, כאשר אתה לא יכול ללכת קדימה ודחיפה
את עצמך לנקודה שבה יש לך קיבל את כל העץ בזיכרון,
או אם אתה יכול לקבל את זה בזיכרון וזה פשוט
אקח לך דרך ארוכה מדי כדי לחפש דרך זה, אתה צריך לעשות משהו חכמה יותר.
>> כדי לעשות את זה, אתה צריך לעשות שני דברים.
ראשית, אתה צריך למצוא כמה דרך של הגבלת העומק שלך.
ובכן, זה בסדר.
אנו יכולים למצוא כמה מינימום נחמד, חשוף ואומרים, אתה יכול רק ללכת כל כך עמוק.
אבל כאשר אתה עושה את זה, זה אומר שאתה יש לוחות שלמים באופן חלקי אלה.
ואתה צריך לבחור, אני אוהב לעשות לוח שלם באופן חלקי זה,
או לוח שלם באופן חלקי זה?
>> ועלינו ארבעה על ידי ארבעה משחק איקס עיגול,
שחקן המחשב שלנו ירד לתחתית וזה אמר,
יש לי שני לוחות שונים.
אף אחד הוא נצחון.
אף אחד הוא הפסד.
אף אחד היא עניבה.
איך בוחר ביניהם?
וזה לא שיש לי דרך חכמה לעשות את זה.
>> אנו רואים מסוג זה הערכה קורה כל הזמן
כפי שאנו מקבלים למשחקים מורכבים יותר.
שחמט הוא דוגמא מצוינת.
בשחמט, יש לנו, ראשון מכל, לוח גדול יותר.
יש לנו הרבה יותר חתיכות.
והמיצוב של יצירות אלה ואופן שבו חתיכות אלה לעבור
הוא חשוב ביותר.
אז אם אני רוצה להשתמש בminimax, אני צריך להיות מסוגל להגדיר
ואומר, לוח, שבו זה אף אחד לא ניצח או הפסיד עדיין,
הוא איכשהו יותר טוב מזה אחר לוח, שבו אף אחד לא ניצח או הפסיד.
>> כדי לעשות זאת, אני יכול לעשות דברים כמו אני יכול רק
לספור כמה חתיכות עושות לי וכמה חתיכות יש לך?
או שאני יכול לתת לי שונה נקודות שונות חתיכות.
המלכה שלי היא שווה 20 נקודות.
החייל שלך הוא שווה נקודה אחת.
למי יש יותר נקודות כוללת?
או שאני יכול לשקול דברים כמו, למי יש את עמדת הלוח טובה יותר?
תור של מי הוא אותו ליד, כל דבר שאני יכול
אין להעריך בצורה מדויקת יותר שאפשרויות אלה
עדיף ללא ממצה שוקל
כל מהלך שיכול לבוא אחרי ש.
>> עכשיו לעשות את העבודה, אחד הדברים זה
הולך להיות ממש חשוב לנו הוא לא רק נע ישר
עד לעומק מסוים גבול, אבל להיות מסוגל לומר,
אחד מהרעיונות האלה שאני יש כל כך רע שזה
לא שווה לשקול כל הדרכים אפשריות
שדברים יכולים ללכת מדחי אל הדחי.
כדי לעשות זאת, נוסיף לminimax עיקרון נקרא אלף-ביתא.
ואלפא-ביתא אומר, אם יש לך רעיון רע,
אל תבזבזו את הזמן שלך מנסה לברר בדיוק כמה רע זה.
>> אז הנה מה שאנחנו הולכים לעשות.
אנחנו הולכים לקחת אותו עקרונות שהיו לנו לפני,
אותו סוג minimax של חיפוש, רק אנחנו
הולך לעקוב אחר, לא רק של ערכים בפועל שיש לנו, אבל אנחנו
לעקוב אחר הטוב ביותר ערך שאני יכול לקבל,
והגרוע ביותר תוצאה הייתי יכול.
וכל זמן הגרוע ביותר האפשרי דבר מחפש סביר,
אני לנטוש חלק זה של העץ.
ואני אפילו לא טורח מסתכל על זה יותר.
>> בסדר, אז לדמיין שאנחנו מתחילים עם אותו עץ המשחק הזה בדיוק.
ועכשיו אנחנו הולכים שוב, כל הדרך למטה
שלפינה השמאלית תחתונה.
ובתחתית שפינה שמאלית, ש נראה ואנו מעריכים לוח זה.
אולי זה ארבעה על ארבעה-מיקס-דריקס טיק לוח, או אולי זה לוח שחמט.
אבל אנחנו מסתכלים על זה, ואנו מעריכים זה, ואנחנו מקבלים ערך של שמונה.
>> בשלב זה, אנחנו יודעים ש אנחנו הולכים לקבל לפחות
שמונה נקודות מהחלטה תחתונה זה.
זה לא משנה מה אחר שתיים, ששבעה ושני ש.
הם יכולים להיות כל ערכים הם רוצים להיות.
אנחנו הולכים לקבל ב לפחות שמונה נקודות.
בסדר, אבל אנחנו יכולים קדימה ולבדוק.
אולי אחד מהם הוא טוב יותר משמונה.
>> אנחנו מסתכל על שבע.
האם זה טוב יותר משמונה?
לא, זה לא משנה חוות דעתנו בכל.
אנחנו מסתכל על שני.
האם זה טוב יותר משמונה?
לא, זה לא משנה חוות דעתנו בכל.
אז עכשיו אנחנו יודעים שאנחנו מותשים כל האפשרויות שיש.
אנחנו לא הולכים לקבל שום דבר טוב יותר משמונה.
אנחנו הולכים לקבל בדיוק שמונה.
>> וכך אנו לשנות צומת וש למשל, שהוא כעת ודאות.
אנחנו עולים ברמה אחת מעל זה.
ועכשיו אנחנו יודעים משהו על שרמת המזעור.
אנחנו יודעים שאנחנו לא הולכים לקבל יותר משמונה נקודות אם אנחנו יורדים
כיוון ש.
כי גם אם אלה שני סניפים אחרים להתברר
להיות פנטסטי ושווה אלפי נקודות כל אחד,
היריב שלנו ייתן לנו את מינימום, ולתת לנו את שמונה.
בסדר, טוב, בואו נראה.
אנחנו נמשיך במורד שביל ש.
אנחנו יורדים לאמצע שעל השמאל.
אנחנו מסתכלים למטה ואנחנו רואים שיש תשע.
אנחנו יודעים שאנחנו הולכים לקבל לפחות תשע נקודות על ידי יורד
שדרך אמצע.
ובשלב זה, אנחנו יכולים רק להשהות.
ואנחנו יכולים לומר, נראה, אני יודע ברמה מעל,
אני הולך לקבל לא יותר משמונה מצביע על הליכה בכיוון זה.
אבל אם הלכתי באמצע נתיב במקום הנתיב השמאלי,
הייתי מקבל לפחות תשע נקודות.
>> היריב שלי הוא אף פעם לא הולך ל תן לי לרדת כי דרך אמצע.
הם יכולים לבחור.
והם הולכים לבחור נתיב אל שמאלה לכיוון שמונה,
ולא באמצע לכיוון מה לפחות תשע נקודות.
אז בשלב זה, אני אפסיק.
ואני אומר, אתה יודע מה?
אני לא צריך להסתכל כל יותר למטה בכיוון זה.
כי אני אף פעם לא הולך להגיע לשם.
>> אני יכול לדלג על זה אחד, ואני יכול לדלג על שש ש,
בגלל שאף פעם לא הולכים לקרות.
אז אני אלך למטה ואני יהיה לשקול את האפשרות הבאה.
אני יורד לשם ואני אומר, אני רואה שתי.
אני יודע שאם אני מגיע לכאן, אני הולך לקבל לפחות שני.
אוקיי.
אני ממשיך הלאה.
אני רואה ארבעה.
אני יודע שאני הולך לקבל לפחות ארבעה.
יש עדיין הרבה בין ארבעה ושמונה, אם כי.
אז אני ממשיך ללכת.
אני מסתכל למטה ואני רואה שיש אחד.
בסדר, אני יודע שאם אני הולך בדרך הזאת,
אני הולך להיות מסוגל לבחור את ארבעה.
מה היריב שלי הולך לעשות?
בין משהו שנותן לי שמונה, משהו שנותן לי ארבעה,
ומשהו ש נותן לי לפחות תשע,
גם, שהוא הולך לתת לי ארבעה.
ואני יודע שעכשיו ב מאוד עליון, אני הולך
כדי להיות מסוגל לקבל לפחות ארבע נקודות מתוך המשחק הזה.
>> כל הרעיון של אלפא-ביתא הוא לחתוך את חלקי העץ כך
שאני לא מסתכל עליהם יותר.
אבל זה עדיין נראה כמו שהייתי מסתכל על הרבה עץ.
בואו נמשיך במורד.
הנרד הבא עכשיו.
למטה בתחתית, אני מוצא אחד.
אני יודע שאני הולך לקבל לפחות אחד.
אני ממשיך לחפש.
>> אני מוצא את שלוש.
אני יודע שאני הולך לקבל לפחות שלוש.
אני ממשיך הלאה.
אני מוצא חמש.
אני יודע שאני הולך לקבל חמש אם אני יורד בדרך זו.
ואני גם יודע אז שהיריב שלי, אם אני
לבחור אמצע שלוש אפשרויות גדולות,
הוא הולך לתת לי משהו שחמישה או פחות.
>> אוקיי.
אני יכול להמשיך שם.
אני יכול להסתכל למטה ואני ניתן לומר, מה אני הולך
כדי לקבל אם אני הולך במורד השביל באמצע?
אני הולך לקבל, גם, שלוש שם.
אני הולך לקבל משהו זה לפחות שלוש.
יש עדיין דברים בין שלוש וחמש, אז אני אמשיך לחפש.
אה, תשע, אני בהחלט לקחת את זה על שלוש.
אני הולך לקבל לפחות תשע אם אני יורד שביל באמצע.
>> עכשיו היריב שלי עוצר ואומר, תראה, אין טעם יותר.
אני יודע ששלי יריב מזעור, הוא
הולך לתת לי דבר זה פחות או שווה לחמש,
ולא הדבר זה גדול או שווה לתשע.
אני עוצר.
אני לא מסתכל יותר שב.
אני ממשיך הלאה.
>> אני מסתכל על זה.
עד לתחתית, אני מוצא את שש.
אני יודע שאני הולך לקבל לפחות שש.
ומה אני יכול לעשות?
אני יכול להפסיק.
כי יש בחירה בין משהו שלפחות שישה
ומשהו ש פחות מחמישה, הוא
הולך לתת לי הדבר זה פחות מחמישה.
ועכשיו אני יודע שאני הולך כדי לקבל בדיוק בחירה ש.
אני הולך לקבל את זה בחירה חמש.
>> אני חוזר לראש.
שאני הולך ל לבחור בין משהו
זה גדול או שווה לארבעה, או משהו שהוא שווה לחמש?
אני הולך לקחת משהו זה לפחות חמש.
אני הולך במורד השביל שעבר, כל הדרך עד לתחתית.
יש אחד.
אישור, לפחות אני הולך לקבל נקודה אחת.
אני ממשיך הלאה.
שני, הו, זה טוב יותר מאשר אחד.
אני הולך לקבל לפחות שני.
אני מוצא את שלוש.
אני יודע שאני הולך לקבל שלוש.
>> והנקודה מעל ש, היריב שלי הולך
לתת לי משהו ש פחות או שווה לשלוש.
ועכשיו אני יכול להפסיק.
כי בבחירה ביני להיות תוכל לקבל חמש ויריב שלי
נותן לי משהו פחות משלושה, אני תמיד הולך לקחת חמש ש.
אז אני לא להעריך ש חלק תחתון של העץ בכלל.
>> עכשיו, זה אולי נראה קל.
אבל כאשר פיסות קטנות של חשבון, גדול יותר ומפחות מ,
יכול לחתוך חלקים שלמים של עץ גדל באופן אקספוננציאלי זה,
שמוביל לענק סכום חיסכון, חיסכון
כי הם גדולים מספיק לי ש יכול להתחיל לשחק תחרותי
במשחקים נוספים מורכבים.
>> בסדר, אם אנחנו מסתכל על הגודל ומורכבות של משחקים שונים,
איקס העיגול היה הדוגמא קלה שלנו.
יש לנו לוח קטן, שלושה על ידי שלוש.
אנחנו מקבלים, לכל היותר, בממוצע כארבע אפשרויות שונות
כפי שאנו עוברים את המשחק.
יש לנו בערך 10 ל עלים שונים אפשריים חמישי.
ובניית איקס עיגול שחקן, טוב, אנחנו פשוט עשינו את זה.
זה קל.
>> אם אנחנו הולכים למשהו יותר מורכב, כמו חבר ארבעה.
האם אתה זוכר את המשחק שבו זה אתה טיפה אסימונים הקטנים ב?
זה שישה שבע לוח, לא כל כך הרבה יותר גדול, עדיין
יש בערך באותו ההסתעפות גורם באיקס עיגול.
יש לי בערך ארבעה אפשרויות איפה אני יכול לשים את הדברים ב.
אבל עכשיו, יש לי הרבה יותר מוביל, 10 לשלטון -21.
זה משהו שהוא קל מספיק שאנחנו פותרים אותה מייד.
>> דמקה, יותר complex-- יש שמונה על ידי שמונה לוח.
אתה רק במחצית שלהם בכל עת, אם כי.
יש לך הסתעפות גורם זה על 2.8.
ובכן, יש לנו כמה עובר לך יכול לקחת.
יש לך כ -10 עד 31 העלים, רווחים גדולים יותר, וגדולים יותר, וגדולים יותר.
כפי שאני צריך לחפש דרך אלה חללים גדולים יותר ויותר,
זה כאשר דברים כמו אלפא-ביתא ו להיות מסוגל לחתוך כל סניפים
הופך להיות חיוני.
>> עכשיו, הדמקה הייתה די קלה בשנת 1992.
תכנית מחשב הנקראת Chinook לנצח את הדמקה העולם
אלוף, מריון טינסלי.
ומאז, לא יש שחקן ראשי אנושי
הצליח לנצח את הטוב ביותר מערכות ממוחשבות.
אם אנחנו מסתכלים על משהו כמו שחמט, עכשיו שוב, יש לנו שמונה על ידי שמונה לוח.
אבל יש לנו הרבה יותר מורכב חתיכות, הרבה תנועות מורכבות יותר.
יש לנו גורם הסתעפות של כ 35, 35 מהלכים אפשריים בממוצע
שאני יכול לקחת, ומדינה חלל, מספר העלים
שגדל ל -10 לכח 123, מספרים עצומים של אפשרויות.
>> אפילו עדיין, מעבדים מודרניים הם מסוגלים לעשות את זה בהצלחה.
בשנת 1995 ולאחר מכן בשינה 1997, מחשב תכנית בשם הכחול עמוק שנבנתה על ידי יבמ
שרץ על מחשב-ענק לנצח את אלוף העולם הנוכחי,
גארי קספרוב.
זו הייתה נקודת מפנה.
היום, אם כי, באותו עיבוד כוח יושב על ה- MacBook שלי.
>> מהירות עיבוד שומרת מקבל יותר ויותר מהר.
אנחנו יכולים להעריך יותר ויותר לוחות מהירים יותר ומהיר יותר.
אבל יותר חשוב, יש לנו יותר טוב פונקציות הערכה וגיזום טוב יותר
שיטות.
אז אנחנו יכולים לחפש שטח מורכב יותר.
הגדול ביותר של הלוח משחקים שאנחנו יכולים לחשוב על,
משהו כמו Go זה קיבלתי 19 על ידי 19 לוח,
עכשיו פתאום, אנחנו מעבר לנקודה שבו מערכות חישובית יכולות לנצח.
אין חישובית מערכת בחוץ
שיכול לנצח את שחקן עבור מקצועי.
הדרגה הכי טובה היום על המערכות הסוג של רמת חובב טובה.
אז יש עדיין לא מעט החוצה יש שאתה לא יכול להגיע לעוד.
>> בסדר, אלה משחקי לוח מסורתיים,
סוגים של מערכות אלו בנו לבנות minimax זה, אם זה יש לי
אלפא-בטא או לא, אלגוריתמים אלה לעבוד כי יש אילוצים מסוימים.
יש לנו מידע מושלם על העולם.
אנחנו יודעים איפה כל החלקים נמצאים.
העולם הוא סטטי.
אף אחד לא מקבל לנוע חתיכות סביב בזמן שאני
יושב שם וחושב, לוקח התור שלי.
יש מרחב פעולה זה דיסקרטי.
אני יכול לשים את החייל שלי כאן, או שאני יכול לשים את החייל שלי כאן.
אסור לי לשים את החייל שלי ב הקו בין שני הריבועים.
>> ולבסוף, הפעולות הם דטרמיניסטיים.
אני יודע שאם אני אומר, צריח לאביר שלושה,
הצריח שלי הולך בסופו של אביר ב שלוש, כל עוד זה מהלך חוקי.
אין ודאות לגבי זה.
עכשיו, כמו שאני הולך ליותר סוגים שונים של משחקים,
אנחנו צריכים לשבור הנחות אלה.
>> מה אם אני הולך למשהו כמו משחקי וידאו קלאסיים?
הנה מבחר של וידאו משחקים מהאטארי 2600.
מה יש לי עד לשם?
יש לי Frogger, חלל פולשים, מלכודת, ופק-מן.
אילו סוגים של סביבות יש לי כאן עכשיו?
איזו מהנחות אלה יש לי לשבור?
>> ובכן, זה תלוי במשחק.
אני יכול לשחק שחמט על 2600, ו זה יהיה בדיוק כמו שהיה לפני.
עבור רוב המערכות אלה, יש להשלים ידע על העולם.
יש לגמרי פעולות דטרמיניסטיות.
אבל בדרך כלל, העולם של כבר לא סטטי.
כלומר, בזמן שאני יושב שם מחכה, משהו זז.
הרוחות באים לקחת אותי.
העקרב הוא בעקבותיי מתחת.
הפולשים החלל הולך ומתקרב.
כמה טוב שאנחנו יכולים לעשות נגד אלה?
>> לפני כמה שנים, גוגל היה פרויקט שנקרא
DeepMind, שבו הם הוכשרו מחשב תכנית לשחק אטארי 2600 משחקים.
ואם אתה חושב שזה לא רציני עסק, תוצאות המחקר שלהם
פורסם בטבע, ולכן רק על כטוב פרסום
ככל שאתה יכול לקבל.
והנה כמה טוב הם ביצעו.
>> יש להם אלגוריתם שישב וצפה רק תשומות המסך.
זה לא קיבל הוראות כלשהן על כללי המשחק.
וזה היה אמור להבין, הציון שלה מבוסס, כמה טוב זה עושה.
זה היה מערכת שמשמשת משהו נקרא למידת חיזוק.
כלומר, זה הסתכל בציונו.
ואם זה קיבל ציון טוב, זה אמר, אני צריך לזכור את הדברים האלה.
ואני צריך לעשות אותם שוב.
ואם זה קיבל ציון רע, הוא אמר, אני לא צריך לעשות את הדברים האלה שוב.
>> זה הביצועים מערכות אלה מאומנים
מותר לשחק כמה שעות בכל משחק,
לעומת נגד גיימרים מקצועיים.
אז לכל המשחקים ש לצד השמאלי של קו זה,
תכנית מחשב-מאומן עצמית ביצועים טובים יותר גיימרים המקצועיים.
ועל הכל ל נכון, גיימרים המקצועיים
היו עדיין הטוב ביותר.
למשהו שידע דבר על הכללים, ש
לא ידע דבר על המבנה משחקים, זה הוא ביצועים מרשימים.
וזה מה שאנחנו יכולים לעשות היום.
>> בסדר, אתה אומר, אבל אם אנחנו חושב על AI במשחקים,
בדרך כלל אנחנו חושבים על דברים שבעצם אנחנו יכולים
לשבת ולשחק נגד.
אם אני יושב ואני משחק סטארקראפט, או שאני משחק מסננת חינם,
יריב המחשב אדם השולט Zerg,
או שליטה הציביליזציה אחרת.
איך השחקנים האלה למעשה למצוא המהלכים שלהם?
>> ובכן, המשחקים האלה בנויים הרבה באותו אופן כמו משחקי הלוח שלנו,
משחקים שנוסיף לאלה באופן קולקטיבי קוראים ארבעה משחקי X,
לחקור, expand-- לשכוח את אלה.
מה הם?
לחקור, להתרחב, ולכבות, אני חושב שזה אחרון.
אבל הם בעצם משחקי חיפושים וכיבוש.
בדרך כלל, יריב המחשב שם יש מידע מוגבל.
הם לא יודעים בדיוק מה קורה מאחורי ערפל של מלחמה.
הם לא זוכים לראות את מה ש יש לך במלאי שלך.
>> יש סביבה שהיא דינמי.
הכל משתנה כל הזמן.
אתה לא מקבל לשבת ו לחכות לקחת את הצעד שלך.
אבל רוב הדברים עדיין בדידים.
אני צריך לשים את העיר שלי כאן.
או שאני צריך לשים את העיר שלי כאן.
וכל מה שהוא דטרמיניסטי.
כשאני אומר, להעביר היחידה שלי כאן, היחידה שלי נע כאן, אלא אם כן מכשול פתאום
נכנס לשחק.
עכשיו, זה לא כל המחשב משחקים כי הם שם היום.
>> אם אני הולך ואני משחק סוג האדם ראשון משחק, משהו כמו גנב או Fallout
או Skyrim, או Halo, עכשיו יש לי יריבי מחשב
כי הם שם כי יש לי מצב שונה מאוד.
יש להם, שוב, מידע מוגבל.
הם יכולים לראות רק שדה מסוים של נוף.
הסביבה היא עדיין דינמית.
דברים משתנים כל הזמן.
>> אבל עכשיו יש לי הרבה יותר מרחב פעולה רציף.
אני יכול להיות רק מציץ קצת מחוץ לדלת.
וכמה משחקים, שלי פעולות הן סטוכסטיים.
אני מקבל לנסות לקפוץ מעל הקיר ש, אבל יש לי סיכוי של כישלון.
סוגים אלה של משחקים מתקרבים וקרוב יותר לסוגים השונים של הבקרים
שאנו בונים ברובוטיקה.
>> ברובוטיקה, אנחנו צריכים להניח שיש לנו מידע מוגבל.
יש לנו חיישנים ש ספר לנו על העולם.
יש לנו תמיד משתנים, סביבה דינמית.
יש לנו עולם שבו השטח הוא רציף, ולא בדיד.
והפעולות שלנו, כאשר אנו מנסים , יש להם סיכוי של כישלון.
ולמעשה משחק, מודרני בקרים ליריב את ההילה שלך,
או למי NPCs בSkyrim, בעצם לרוץ ארכיטקטורות רובוטיקה קטנות.
>> הם חשים העולם.
הם בונים מודל של העולם.
הם לחשב מבוססים על סט של מטרות שהם רוצים להשיג.
הם מתכננים פעולות מבוססות על מה שהם יודעים.
ואלה הם בדיוק אותו הסוג מערכות שאנו בונים ברובוטיקה.
אז ארכיטקטורות אלה, ל להחזיר את זה ביחד,
לעתים קרובות בדיוק אותו הדבר.
>> אז בואו לראות אם אנחנו יכולים לראות את זה.
בואו נחזור לנו איקס עיגול דוגמא.
ואני הולך לשאול כמה פוסט המסמכים לבוא ולעזור לי.
אז חן מינג, ואלסנדרו, ו אוליבייה, אם אתם היו לבוא.
ואני הולך צריך כמה מתנדבים
>> אישור, ראיתי יד ימין למעלה שם באמצע.
תן לי לקחת עוד אחד, מישהו נוסף בחלק האחורי אולי.
בסדר, שם.
בואו למעלה.
בסדר.
אז בואו ניקח את הכיסוי שלמטה.
ואם אתם יבואו תקין בחזרה כאן בשבילי, פנטסטי.
>> אז זה רובוט בשם בקסטר.
ובקסטר הוא רובוט זה פלטפורמה מסחרית, שנועדה
על ידי חברה בשם לחשוב מחדש.
ורובוט זה נועד לייצור בקנה מידה קטנה.
אבל היום אנחנו הולכים ל להשתמש בו כדי לשחק איקס עיגול.
עכשיו, הרובוט הזה הוא גם משהו זה יחסית ייחודי.
כי אם אני היה עומד בכל מקום קרוב לאוטומציה במפעל סטנדרטית
מערכת, שהייתי בקבר מאוד סכנה שנפגעו.
>> בקסטר, לעומת זאת, נועד להיות בטוח יחסית לאינטראקציה עם.
ואז אני יכול לדחוף על הרובוט הזה.
ואתה יכול לראות שזה קצת קצת גמיש כפי שהוא נע סביב.
ואני יכול למקם אותה מחדש שבו הייתי רוצה אותו ללכת.
עכשיו במערכת רובוטית נורמלית, תהיה לנו קבוצה של מפרקים כאן
זה יהיה ישירות להגיב לפקודות עמדה.
והם לא היו אכפת לי בהכרח אם הם עוברים דרך אוויר פתוח,
או אם הם נעו דרך בית החזה שלי.
>> אוקיי.
ובדרך כלל, אם היית כאן עם מערכת תעשייתית,
היית הולך לשום מקום לידו.
יהיה צהוב קלטת בטיחות סביבו.
במערכת זו יש עיצוב מעט שונה
להיות ידידותי יותר וקל יותר לאנשים לתקשר עם,
שבכל מפרק, יש אביב.
ולא שליטה מיקום מדויק,
אנו שולטים בכמות מסוימת של מומנט, כמות מסוימת של כוח,
כי אנחנו רוצים להיות באביב ש.
בסדר, אז תנו לי לקחת המתנדבים שלנו כאן.
היי מה שמך?
>> קהל: לואי.
>> דובר: לואי.
טוב לראות אותך.
ו?
>> קהל: דוד.
>> דובר: דוד.
נחמד לפגוש אותך.
אם אתם יחכו כאן לרגע,
אני הולך לתת לך הזדמנות לעשות את זה.
אז הרובוט הזה, אם אתה בא ואם אתה דוחף בעדינות על זה,
אתה הולך לראות ש הוא נע קצת.
ואם אתה תופס את זה נכון כאן על פרק כף היד פשוט
מעל איפה הכפתורים האלה, זה נראה שאתה צריך לתפוס את הכפתורים,
אבל לתפוס ממש מעליו במקום, תוכל תוכל לתפעל אותו בעדינות רבה
בחלל.
לואי, אתה רוצה לנסות את זה?
אז נותן לו רק קצת לדחוף להתחיל עם.
ואז אם אתה שם את האצבעות שלך ממש שם ולהחזיק לה,
כי זה יעבור לך אז.
בסדר, אתה רוצה לנסות את זה?
בואו למעלה.
אז נותן לו רק עדין לדחוף לשם כדי להתחיל.
אתה יכול להרגיש איך זה.
ואז אם אתה תופס אותו שם, תוכל לתמרן סביב ב.
>> אוקיי.
אז בדרך כלל, של רובוט מסוג זה היית לשמש לייצור בקנה מידה קטן.
ואני הולך להזיז את יד זה רק למטה מהדרך קצת כאן.
אבל היום, אנחנו הולכים להשתמש ב אותה מערכת נגינה איקס עיגול
המבוסס על minimax שנבנינו קודם לכן.
אוקיי?
אז, אתם כל הולך לשחק את משחק.
לואי, אתה הולך להיות ראשון.
תן לי רק להחזיק עד כאן לרגע.
אני הולך יש לך לעמוד תקין כאן, רק כדי שכולם יכול לראות אותך.
האם אתם הקימו כאן?
>> רובוט: ברוכים הבאים.
בואו לשחק איקס עיגול.
לא לתפוס האסימון שלך לפני ש אני אומר שזה התור שלך.
אני מתחיל את המשחק.
זה התור שלי.
דובר: עכשיו, אם אתה יכול לקחת את אחד מ החתיכות שלך וללכת קדימה ולמקם אותו.
רובוט: זה התור שלך.
[צְחוֹק]
זה התור שלי.
[צְחוֹק]
זה תורך.
דובר: המין האנושי הוא סומך עליך כאן, לואיס.
>> רובוט: זה התור שלי.
>> דובר: אז בקסטר נחסם בהצלחה כאן.
>> רובוט: זה התור שלך.
זה התור שלי.
זה תורך.
זה התור שלי.
דובר: ואנחנו אתן בקסטר לסיים את המהלך האחרון שלה כאן.
>> [צְחוֹק]
>> רובוט: זה עניבה.
אני אנצח בפעם הבאה.
>> [צְחוֹק]
>> דובר: בסדר, תודה רבה, לואיס.
תודה.
אתה יכול ללכת בדרך זו.
>> רובוט: אני מתחיל את המשחק.
דובר: אז תן לי להסביר לך אחד קטן יותר
קצת לפני שאנחנו מקבלים משחק גומלין שלנו כאן.
מה בדיוק קורה?
אז הרובוט יש מצלמה עליונה עד כאן.
וזה הביט בלוח.
וזה לראות אם יש לו O אדום או כחול
וX. הלבן כמו אלה לקבל להציב ב לוח, זה בעצם אותו דבר הקלט
שהיו קוראים מ מבנה הנתונים שלנו מהמסך שלנו.
זה פועל באותה אלגוריתם minimax להיות
תוכל למצוא בו ל מקום אסימון טוב.
>> ואז אנחנו נותנים פקודה על שבו אנחנו רוצים אסימון כדי להיות ממוקם.
הזרוע נעה החוצה.
זה באמצעות תפסן ואקום ליישם כמה יניקה שלפיסת עץ,
להרים אותו, להעביר אותו לצד ימין מקום, ולאחר מכן שחרר את היניקה
ושחרר אותו.
בסדר, אנחנו הולכים כדי לתת לו ירייה אחת יותר
עם שחקן מעט חכמה יותר כאן.
אתה מוכן?
בסדר, אם היית עומד ממש עד כאן ולתת לזה-- להתברר בדרך זו
כך שאתה יכול לראות את כולם.
ואז [לא ברור].
>> רובוט: זה התור שלי.
>> הדובר: קסטר יתחיל.
זה תורך.
זה התור שלי.
זה תורך.
זה התור שלי.
>> [צְחוֹק]
>> דובר: [לוחש] רק תן לו ללכת קדימה ולנצח.
רובוט: זה התור שלך.
דובר: זה בסדר.
>> רובוט: זה התור שלי.
>> [צְחוֹק]
>> אני ניצחתי.
>> [צְחוֹק]
>> אני מתחיל את המשחק.
>> דובר: בסדר, תודה רבה לך.
בסדר, אני חושב שיש לנו זמן ל שחקן איקס עיגול מעולה יותר אחד,
מישהו שיכול לשים את הדבר הזה ל להתאים, מי יודע מה הם עושים.
>> [צְחוֹק]
>> מי הולך להיות האלוף שלנו כאן?
בסדר, החברים שלך התנדבו.
זה מספיק טוב בשבילי.
תגיד לי את השם שלך שוב.
קהל: תמיר.
הדובר: תמיר, נחמד לראות אותך.
בסדר, שוב, אנחנו הולכים לשים אותך ממש עד לכאן כדי שכולם יכול לראות אותך.
אתה הנציג שלנו במשחק הזה עכשיו.
בקסטר הוא אחד והו הו ו.
או מצטער, אחד הו ואחד.
וזה תלוי בך כאן.
בקסטר יקבל לנוע ראשון, אם כי.
כָּך.
רובוט: זה התור שלי.
>> [צְחוֹק]
>> זה תורך.
זה התור שלי.
זה תורך.
זה התור שלי.
זה תורך.
>> [צְחוֹק]
רובוט: זה התור שלי.
דובר: זה הרבה יותר קשה כאשר אתה עומד כאן, רבותיי.
[צְחוֹק]
רובוט: אתה האדם כל כך קל לנצח.
[שחוק ומחיאות כפות]
דובר: תודה רבה.
רובוט: אני מנצח.
אני מתחיל את המשחק.
>> דובר: בסדר, אז תודה מאוד הרבה אוליבייה, ואלסנדרו,
ולחן מינג.
>> [תְשׁוּאוֹת]
>> אני רוצה להבהיר את הנקודה אחרונה.
אז בקסטר במאוד נגמרתי שם, רימה.
וזה היה בלתי צפוי.
אחד הפנטסטי דברים על AI הם ש
לעשות את העבודה בAI, כדי שנוכל לבנות באמת מעניין ואינטיליגנטי
מכשירים.
אבל אנחנו גם עושים את העבודה בAI כי זה אומר לנו משהו
על איך בני האדם אינטליגנטיים.
>> אחד האהוב מחקרים מהמעבדה שלי הוא
מסתכל על מה שקורה כש מכונות לרמות באופן בלתי צפוי.
אנחנו עשינו את זה במקור לא עם בקסטר שיחק איקס עיגול,
אבל עם רובוט קטן בשם נאו, ששיחק אבן נייר ומספריים.
ולפעמים אחרי משחק המון המון
של משעמם משחקי אבן נייר ומספריים, הרובוט היה זורק מחווה,
להפסיד, ואז פתאום לשנות מחווה ו אומרת, אני מנצח.
>> [צְחוֹק]
>> עכשיו, לפעמים הייתי גם יש לנו את הרובוט, רק כביקורת, לזרוק מחווה,
לנצח, ולשנות את חוויתה לאבד, לזרוק את המשחק,
רמות כדי להפסיד.
וזה לא משכנע כמעט כמו.
הרובוט שבגידות כדי לזכות אנשים
להגיב לכאילו זה כדי להשיג אותם, כמו אותו
מחפש באופן פעיל להשמדתם.
>> [צְחוֹק]
>> זה הופך להיות סוכן.
זה כמו אדם.
יש לו אמונה וכוונה.
וזה לא כוונה טובה.
והרובוט שזורק משחק הוא רק תקלה.
זה פשוט מכשיר שבור.
תן לי להראות לך כמה דוגמאות של שמכמה מהמשתתפים שלנו.
אז הנה רמאות כדי להפסיד.
>> [וידאו השמעה]
- [לא ברור] לנצח.
בוא נשחק.
>> -רגע מה?
>> - [לא ברור] לנצח.
בוא נשחק.
>> [לא ברור] לנצח.
בוא נשחק.
>> דובר: והנה רמאות כדי לנצח.
>> -כן, אני מנצח.
בוא נשחק.
>> 'אתה לא יכול לעשות את זה.
>> [צְחוֹק]
>> -כן, אני מנצח.
'אתה רימית.
אתה רימית עכשיו.
>> -כן, אני מנצח.
>> היי, אתה רמאי.
אתה מרמה, לרמות סופר.
>> [סוף ההשמעה]
>> דובר: אלה שונים תגובות במהירות
לשנות את התפיסה של המכשיר שלנו.
האם זה אומר ש אנחנו בכוונה לבנות
מכונות שמרמות כי זה ההנדסה הטובה ביותר שאנחנו יכולים לעשות?
לא, אבל זה אומר לנו משהו באמת מעניין על אנשים.
הדבר הזה שאתה בוגד ו גונב הנצחון שלך, זה
משהו שהוא בחיים, זה להנפיש, זה החוצה כדי לקבל אותך.
יש לו מצבו הנפשי.
יש לו אמונה.
יש לו כוונה.
>> הדבר הזה שמוסר משחק לך, זה לא.
זה רק תקלה.
זה הוא במובנים רבים למה זה קל לזרוק את המשחק עם ילדים.
אבל אם אתה מנסה לרמות אותם וסוג של לטעון לנצחון
כאשר, אתה יודע, רק כדי לקצר את משחק, שיתפסו אתכם מייד.
אלו סוגים של השפעות ש אנו רואים שיוצאים מAI,
הם מלמדים אותנו הרבה על עצמנו.
>> בסדר, זהו זה להיום.
תודה רבה לדוד ו צוות ההפקה של הרווארד
ליורד.
>> [תְשׁוּאוֹת]
>> אנחנו אראה אותך לחידון אחד, ולאחר מכן להרצאה אחת האחרונה.
שיהיה לך יום טוב.
>> [תְשׁוּאוֹת]
>> [השמעת מוסיקה]
דוד J מלאן: ובכן, אנחנו כנראה צריכים כדי להציג סוג מסוים של הצפנה,
יָמִינָה?
כי אז הכותרות של בקשות HTTP אלה יהיו
מקושקשת כך שכל אחד מנסה לרחרח את התנועה שלך
לא ממש תוכל לראות אותם.
אז מה הפתרון לבעיה זו?
ובכן, אנחנו צריכים להציג למעשה הצפנה בנוסחה,
כך שכאשר האדם שהוא העברת נתונים מA ל- B,
אנחנו יכולים באופן מאובטח send--
>> [צְחוֹק]
>> המידע באופן ש יריב לא יכול, למעשה, רואה את זה.