>> [Muzika]
>> SPEAKER: Mirë se vini mbrapa, të gjithë.
Kjo është CS50.
Dhe sot, ne kemi një shumë të gjëra interesante për të folur rreth.
Së pari, edhe pse, unë kam për të kujtuar ju e disa gjëra administrative.
Këtë javë është kuiz një, e mërkurë ose për pjesën Yale
të martën dhe të enjteve, të enjten.
Ka komente quiz sonte në Yale, 5:30 deri 7:00.
Në Harvard, ata regjistrohen një dje.
Dhe të gjithë mund të shikojnë atë në internet.
>> Po ashtu, gjatë kësaj jave ose në fillim të javës së ardhshme, ne kemi ligjëratë fundit tonë CS50.
[Rënkon] Unë e di.
Ai erdhi kaq shpejt.
Yale studentët do të kenë një të jetojnë leksion këtu në shkollë të ligjit
auditor të premten.
Nuk do të jetë tortë.
Studentët e Harvardit do të ketë leksion të fundit në Sanders të hënën.
Nuk do të jetë gjithashtu tortë.
>> Po ashtu, gjatë kësaj jave të premten, për ata prej jush që vijnë në New Haven,
ne kemi Expo CS50.
Ne kemi më shumë se 30 grupet e ndryshme të regjistruar
për të ju tregojnë gjithçka nga Sailboats autonome,
për sistemet që njohin portrete dixhitale, në kompjuter
muzikë dhe kompjuter-prodhuar muzikë.
Kështu që ju lutemi bashkohuni me ne.
Unë mendoj se kjo do të jetë një kohë e madhe.
>> Sot, megjithatë, ne kemi marrë për vazhdojë duke folur për UA,
rreth inteligjencës artificiale.
Dhe një nga gjërat që ne jemi duke shkuar për të marrë në sot
është ideja se si të përdorin UA për të zgjidhur problemet.
Tani, si gjithmonë, le të fillojë me diçka të thjeshtë.
Dhe ne jemi duke shkuar për të filluar me një ide të thjeshtë.
Dhe kjo është duke përdorur search.
>> Pra, imagjinoni për një minutë se unë kanë një detyrë që kam nevojë për të kryer.
Dhe unë do të doja që të ketë këtë detyrë automatizuar nga disa agjent software.
Paramendoni se unë jam duke u përpjekur për të librit një grup i fluturimeve nga, le të themi, Boston
në San Francisko.
Unë mund të shkoj nëpër dhe unë mund të përdorni një kërkim të mrekullueshme online
mjete, e cila do të bëjë në thelb i njëjti proces që ne jemi
do të ecin nëpër sot.
Por në qoftë se ju nuk keni se mjet, çfarë do të bëni?
>> E pra, ju mund të shikoni dhe të shohin dhe them: Unë jam në Boston.
Cilat fluturime janë në dispozicion për mua?
Tani, ndoshta unë kam tre fluturime të mundshme nga Bostonit
që do të përshtaten kohës kur kam nevojë për të lënë.
Unë mund të fluturojnë në Çikago.
Ose unë mund të fluturojnë në Miami.
Ose unë mund të fluturojnë për në Nju Jork.
Unë pastaj mund të shohim nga secila një nga ato qytete destinacionit
dhe mendoni se çka lokacionet Unë ndoshta mund të arrijë
nga njëri prej këtyre qyteteve individuale.
>> Pra, ndoshta nga Çikago, unë mund të merrni një fluturim të drejtpërdrejtë në San Francisko.
Kjo është e shkëlqyer.
Ose unë mund të merrni një fluturim për në Denver.
Tani, ndoshta se fluturimi në San Francisko është zgjidhje e përkryer për mua,
por ndoshta jo.
Ndoshta unë jam duke kërkuar për diçka kjo është pak më të lirë
ose pak më të mirë për orarin tim.
Dhe kështu që unë mund të shikoni për atë që të tjera mundësi mund të jetë atje.
Kështu që unë mund të shikoni në Denver.
Dhe nga Denver, mirë, ndoshta Unë mund të merrni një fluturim për në Austin.
Dhe nga Austin, ndoshta unë mund të merrni një fluturimit në Phoenix, dhe nga Phoenix
në San Francisko.
Tani, unë nuk jam bërë ende.
Sepse ndoshta ka një fluturim direkt nga Nju Jorku
në San Francisko që është e përkryer për mua.
Apo ndoshta ka një fluturim nga Miami përmes Denver kjo është një shumë më të lirë.
Kështu që unë ende kanë për të shkuar.
Dhe unë ende duhet të shikoni në të gjithë ata qytetet që unë nuk kam hulumtuar ende.
Unë duhet të shteruese të kontrolluar të gjithë mundësitë që unë mund të ketë.
>> Pra, nga Nju Jorku, ndoshta unë mund të merrni një fluturimit në Nashville, dhe nga Nashville
në Austin.
Dhe atëherë unë e di se ku jam.
Dhe atëherë unë e di nga Austin, unë mund të fluturojnë në Phoenix, dhe nga Phoenix
në San Francisko.
Nëse unë të fluturojnë për herë të parë në Miami, edhe pse, ndoshta unë mund të merrni një fluturim nga Miami
në Nashville, ose nga Miami në Austin.
>> Dhe tani unë kam provuar të gjitha nga mundësitë.
Unë e kam ndërtuar këtë grafik që tregon mua të gjitha rrugët e mundshme
që të mund të jetë në gjendje për të marrë.
Kur ne përfaqësojmë këto llojet e problemeve,
ne nuk jemi duke shkuar për të përfaqësuar ato në mënyrë të qartë si ky grafik,
sepse kjo grafik nuk përfaqëson historia e ku kemi shkuar.
Duke ditur se unë fluturoi nga Phoenix në San Francisko
nuk më thoni nëse unë kam ardhur nëpërmjet Nashville, ose nëpërmjet Denver, ose nëpërmjet Miami.
>> Pra, çfarë unë do të bëj në vend të kësaj është Unë do të marrë këtë të njëjtin problem,
dhe unë do të përfaqësojë atë si një pemë.
Dhe në rrënjë të pemës, në nivel lartë, unë do të vënë në vendin që kam filluar,
Boston.
Dhe nga Bostoni, unë do të shikojmë në të gjitha vendet e mundshme
që unë mund të udhëtojnë në.
E pra, në këtë rast, unë kam tre, Çikago, Nju Jork, dhe Miami.
Dhe atëherë unë do të shqyrtojë secilin nga këta fëmijë në pemë.
>> Nga Çikago, kam parë që kam pasur dy fluturime.
Unë mund të fluturojnë direkt San Francisco apo në Denver.
Tani San Francisco, ky është qëllimi im.
Ky është destinacioni im.
Kjo do të jetë një fletë e kësaj peme.
Kjo është, unë jam duke shkuar për të shkuar kurrë diku pas San Francisko.
Nga Denver, edhe pse, Unë mund të fluturojnë nga Denver
për Austin, nga Austin në Phoenix, dhe nga Phoenix në San Francisko.
Dhe tani përsëri, unë kam arritur në një fletë.
>> Unë pastaj mund të kthehem për të ardhshëm qytet që unë nuk e kam eksploruar plotësisht.
Kjo do të jetë New York, shko përsëri deri në majë të pemës sime,
zbresë në Nju Jork.
Nga Nju Jorku, unë mund të fluturojnë në Nashville, nga Nashville në Austin,
nga Austin në Phoenix, dhe nga Phoenix në San Francisko.
Dhe së fundi, një qytet i nuk e kanë shikuar akoma, Miami.
>> E pra, nga Miami thashë unë kam dy mundësitë, Nashville ose Austin.
Nëse unë fluturojnë në Nashville, edhe atëherë unë fluturojnë nga Nashville, në Austin, në Phoenix,
në San Francisko.
Nëse unë fluturojnë në Austin, unë fluturojnë Austin, në Phoenix, në San Francisco.
Dhe tani kam një pemë.
Kjo është një pemë të plotë.
Kjo është e gjitha nga mundësitë dhe të gjitha shtigjet që unë mund të marrë.
Kjo është, në qoftë se unë të fillojë në nivel rrënja e pemës në krye
dhe unë të zbres në një nga lë, ajo tregon mua jo vetëm
ku unë jam duke shkuar për përfundojnë, San Francisco,
por ajo tregon mua rrugën që Unë kam nevojë për të marrë për të arritur atje.
>> Tani, që një nga këto është më e mira?
E pra, asgjë në lidhje me këtë Problemi ende tregon mua
cili prej tyre është zgjidhja më e mirë.
Ndoshta unë intereson më për sa herë që unë jam në ajër,
ose distanca që unë jam duke fluturuar.
Në këtë rast, Chicago në San Francisco mund të jetë numri i shkurtër
milje në ajër.
>> Ndoshta më intereson kosto.
Dhe ne të gjithë e dimë fluturime direkte janë zakonisht më të shtrenjta.
Pra, ndoshta, nëse unë të marrë kjo lloj i rrugës prapa
përmes Miami, Nashville, Austin, Phoenix, ndoshta atëherë
Unë të marrë një çmim më të ulët.
Por unë mund të zgjedh në ndonjë Kriteret që më intereson.
Kush e mori më të mirë në fluturimi Wi-Fi, ose që
aeroportet kanë ushqimi më i mirë në dispozicion.
Dhe secili prej atyre fuqisë më jepni një zgjidhje të ndryshme
që unë shoh si më të mirë.
>> Këto lloje të problemeve, ku ne jemi duke shkuar
për të ndërtuar këtë pemë të mundësitë, dhe pastaj
shikojnë njëri nga ata shtigjet individuale, dhe të shqyrtojë
e cila i plotëson këto një kriter për ne,
ne jemi duke shkuar për të thirrur këto probleme kërkimit.
Dhe ne kemi shumë algoritme, disa prej të cilave
ne kemi parë tashmë, për të shkuar dhe të eksplorojnë ato pemë.
Ne mund të bëjë atë në mënyrë që unë vetëm e bëri, një kërkim thellësi-së pari,
duke shkuar poshtë aq sa mundemi deri sa ne goditi një fletë, dhe pastaj të vijnë lart,
dhe duke shkuar drejtë mbrapa poshtë.
Ose ne mund të bëjmë çfarë është quajtur kërko gjerësia-për herë të parë.
Ne mund të zgjerohet gjithçka në krye dhe pastaj
çdo gjë një linjë poshtë se, dhe pastaj
çdo gjë nën një linjë që.
Këto pemë e kërkimit janë themelore për të UA.
Por ata nuk e mjaft të merrni kjo e drejtë gjatë gjithë kohës.
Në fakt, në shumë raste që ne me të vërtetë kujdeset për,
ne duam të ndërtojmë një pemë, por ne nuk e bëjmë në fakt
merrni për të bërë të gjitha vendimet.
>> Këto janë situata të quajtur Kërkimi kundërshtuese, i njohur gjithashtu
se si të shkruaj lojë duke luajtur sistemet dhe paguhen për të.
Por këto janë llojet i sistemeve ku unë
mund të merrni për të zgjedhur, kur unë shkoj nga Boston, që qyteti të shkoj për të ardhshëm.
Por pas kësaj, dikush tjetër mund të merrni për të marrë vendimin se ku unë fluturojnë.
Pra, për të ndërtuar këto llojet strukturat, ne jemi
do të duhet të marrë një pak qasje të ndryshme për të.
Ne nuk do të jetë në gjendje për të kërko vetëm nëpër pemë
më, sepse ne nuk jemi ai që është në kontroll
e secilit prej këtyre pikave vendim.
>> Pra, le të imagjinojmë një të thjeshtë lojë si TIC-TAC-shputë.
Unë mund të fillojë me një Bordi krejtësisht bosh.
Dhe në TIC-TAC-shputë, X merr për të luajtur për herë të parë.
Dhe kështu që unë mund të mendoj për të gjithë lëvizjet e mundshme që mund të bëjë. X
Dhe në qoftë se unë jam ai lojës X, kjo është e madhe.
Unë kam nëntë jetë e mundur lëviz që unë mund të bëjë.
I mund të vënë në një X cdonjerit e këtyre nëntë pozicione.
>> Dhe pastaj nga njëri prej atyre, unë mund të imagjinojmë se çfarë ndodh më pas.
E pra, në këtë rast, të tjera Lojtar do të merrni për të marrë një kthesë.
O do të merrni për të marrë një kthesë.
Dhe nga secili nga ata, atje do të jetë tetë vende të ndryshme
se o mund të zhvillohet shënues tyre.
>> Le të thonë se unë vendosa se isha do të vënë një X në qendër.
Që gjithmonë duket si një masë e mirë e hapjes.
Unë mund të shikoni në nën kësaj, tetë lëvizjet e mundshme që bën. O
Tani, në qoftë se unë jam duke luajtur X, kjo është e mrekullueshme.
I merrni për të zgjedhur të cilat e unë shkoni në, një në mes.
Por tani, o merr për të zgjedhur.
Dhe unë nuk kam kontroll mbi atë vendim.
>> Por nga njëri prej atyre pozicionet e mundshme bordit,
ka pastaj një tjetër vendosur të mundësive.
Kur vjen puna për jetë im të kthehet përsëri, unë do të
shkoj të marr dhe të thonë, mirë, nëse O lëviz në të, mirë,
vend mesme në të majtë, atëherë Unë kam një grup të mundësive
ku unë mund të marrë veprim tim të ardhshëm.
Nga ata, unë mund të konsiderojnë të gjithë mundësitë nën to.
Dhe pastaj o do të merrni të zgjedhin në mesin e atyre.
>> Dhe unë mund të mbajë ndërtuar këtë pemë jashtë deri sa kam marrë në pikën
ku ose dikush fiton game-- që është
Got për të konsiderohet si një gjethe node-- ose bordi është tërësisht i plotë
dhe askush nuk e ka fituar.
Dhe kjo gjithashtu do të jetë një nyje gjethe.
Kjo do të jetë një kravatë.
>> Por gjëja e ndërlikuar me këtë është në qoftë se kjo ishte vetëm një kërkim të rregullt
problem, unë do të jetë në gjendje për të të themi, pra, X duhet të shkoni këtu.
Dhe o duhet të shkojnë rrugën atje.
Dhe pastaj X duhet të shkoni këtu.
Dhe pastaj, o duhet të shkojnë rrugën atje.
Dhe pastaj X mund të merrni tre në një rresht, dhe unë të fitojë.
Dhe loja do të jetë mbi në pesë lëvizje, tre për mua,
dy për kundërshtarin tim.
Por unë nuk gjithmonë merrni për të zgjedhur atë.
>> Pra, në vend, ajo që ne jemi do të keni për të bërë
po ne do të kemi të ketë një strategji të re.
Dhe strategjia që algoritme lojë-playing shpesh përdorin
është ajo që quhet Minimax.
Ideja qendrore e Minimax është se ne jemi
do të marr veprim që i jep Kundërshtari ynë tërësia e keqe e mundshme
të lëviz që ata mund të bëjnë.
Ajo nuk ka të bëjë më ndonjë të mirë për të zgjedhur një lëvizje ku
Unë mund të jetë në gjendje për të fituar pas se, për shkak se kundërshtari im nuk është
do të më japë atë shans.
Ata do të zgjedhin disa Rezultati i tmerrshëm për mua.
Kështu që unë jam duke shkuar për të bërë veprim që forcat kundërshtarin tim
për të bërë diçka më të mirë për mua.
Në rregull.
Le të shohim se si ajo luan jashtë.
Kështu që këtu është algorithm tonë në pseudokod.
Ne jemi duke shkuar për të gjeneruar të gjithë pemë lojë.
Ne jemi duke shkuar për të ndërtuar gjithë struktura.
Dhe pastaj ne do të shkojnë përmes.
Dhe në fund shumë në secilin nga nyje terminal, në secilin nga gjethet,
ne do të vlerësojë se si e vlefshme është që për mua?
Dhe ne jemi duke shkuar për vlerë të gjërave që janë të mira për mua si pozitiv.
Gjëra që nuk janë të mira për mua do të jetë më pak pozitiv, ose zero,
apo edhe negative.
>> Pra, në TIC-TAC-shputë, ndoshta një fitore për mua është e mirë.
Kjo është një.
Dhe një kravatë është zero.
Dhe diçka që është një humbje për mua, ndoshta kjo është një negativ.
Të gjitha që ka rëndësi është se më mirë kjo është për mua, aq më i lartë rezultati
ajo merr.
Prej këtyre mundësive më së në fund, atëherë ne do të filtruar lart.
Dhe kur është shansi im për të zgjedhur në mesin e një sërë alternativash,
Unë do të zgjedhin atë që është mori rezultatin më të lartë.
>> Dhe sa herë që My Kundërshtarët të kthehet për të zgjedhur,
Unë do të supozojmë se ata do të zgjidhni një me rezultatin më të ulët.
Dhe në qoftë se unë bëj këtë gjatë gjithë rrugës deri në majë të pemës,
Unë do të keni zgjedhur një rrugë që i jep mua rezultati më i mirë që unë mund të merrni,
duke supozuar se kundërshtarin tim bën të gjitha lëvizjet e duhura.
>> Të gjithë të drejtë, kështu që le të shohim këtë në veprim për herë të parë.
Dhe pastaj ne do të vërtetë shikoni në kodin për të.
Pra, imagjinoni unë kam këtë pemë të madhe.
Dhe tani unë nuk jam duke luajtur TIC-TAC-shputë.
Unë të kërkuar për të ju jap diçka pak më të pasur.
Kështu që unë kam marrë disa lojë ku ka shumë rezultate të ndryshme
që unë mund të ketë në fund.
Dhe kështu që unë të ndërtuar këtë pemë të plotë.
Dhe unë të marrë për të lëvizur për herë të parë.
Unë jam në rrënjë të pemës.
>> Dhe të shkoj për të zgjedhur that-- kështu që unë shkoj për të maksimizuar të gjithë atë nyje të parë.
Dhe pastaj kundërshtari im merr për të shkuar.
Dhe pastaj të shkoj për të shkuar një herë më shumë.
Pra, poshtë në fund, unë kam një grup të Mundësitë që unë mund të zgjidhni nga,
shtete të ndryshme terminal të lojës.
Në qoftë se unë jam poshtë në atë tani majtas qoshe dore,
dhe unë shoh se kam një zgjedhje midis një tetë, një shtatë dhe një dy,
mirë, unë jam ai që merr për të zgjedhur.
Kështu që unë jam duke shkuar për të zgjedhur një më të mirë nga ata.
Unë jam duke shkuar për të zgjedhur tetë.
>> Kështu që unë e di se në qoftë se unë ndonjëherë merrni deri në këtë pikë,
Unë do të jetë në gjendje për të marrë se tetë pikë.
Nëse unë të përfundojë deri në pikën e ardhshme mbi, nyja tjetër gjatë,
një nëntë, një njeri, apo një gjashtë, pra, unë jam duke shkuar për të zgjedhur më të mirë nga ata.
Unë do të zgjedhin nëntë.
Nëse unë kam një zgjedhje midis dy, dhe katër, dhe një,
Unë do të zgjidhni katër, më e larta.
>> Tani, në qoftë se unë shoh në nivel më lart se, kundërshtari im
është ai merr për të bërë këtë zgjedhje.
Pra, kundërshtari im merr për zgjidhni, nuk dua të jap atë
gjë që po ndodh për të marrë atë tetë pikë,
ose mund t'i japë atij gjë që është duke shkuar për të dhënë atij nëntë pikë,
apo ajo që po ndodh për t'i dhënë atij katër pikë?
Dhe kundërshtari im, duke u racional, po shkon
për të zgjedhur minimumin e atyre, do të zgjedhin katër.
>> Dhe unë mund ta bëjë këtë nëpër tërë pema.
Unë mund të shkoj poshtë në atë grup mes të tre.
Dhe unë mund të zgjedhin në mes një, tre, dhe pesë.
Dhe të shkoj për të zgjedhur.
Kështu që unë zgjedh një pesë.
Unë mund të zgjedhin tre, nëntë, ose dy.
I merrni për të zgjedhur, kështu që unë zgjedh nëntë.
Gjashtë, pesë, ose dy, unë zgjedh.
I merrni për të zgjedhur gjashtë.
Nivel më lart se, i cili merr për të zgjedhur?
Kush e merr për të zgjedhur?
Djalë tjetër, kundërshtari im.
Kështu që ata zgjedhin pesë, nëntë ose gjashtë, e cila një?
>> Audienca: Pesë.
>> SPEAKER: Ata zgjedhin pesë.
Ata marrin për të zgjedhur minimale.
Dhe pastaj e fundit, zgjidhni një, dy, ose tre.
I merrni për të zgjedhur, kështu që unë zgjedh tre.
Nëntë, shtatë, ose dy, unë zgjedh nëntë.
Dhe 11, gjashtë apo katër, unë zgjedh 11.
Kundërshtari im pastaj zgjedh tre, nëntë, ose 11, zgjedh minimale.
Ai jep mua një tre.
Dhe pastaj në fund në krye pema, unë shkoj për të zgjedhur përsëri.
Dhe të shkoj për të zgjedhur midis a katër, një pesë, ose nje tre.
Kështu që unë të marrë pesë.
>> Nëse unë kam për të kontrolluar çdo gjë, unë do të marrë rrugën që çoi në 11.
Por unë nuk do të marrë për të bërë këtë zgjedhje.
Nëse unë shkoj poshtë atë rrugë.
Kundërshtari im do të detyrojë mua në zgjedhja që të çon në një tre.
Në mënyrë më të mirë që unë mund të bëj është për të marrë atë degë të mesme,
bëjnë këtë zgjedhje që është përfundimisht do të më çojë në pesë pikë.
Kjo është ajo që e bën Minimax.
>> Në rregull.
Le të marrin një vështrim në atë.
Pra, këtu në CS50 IDE është një program që
zbaton Minimax për të luajtur TIC-TAC-shputë.
Ne jemi duke shkuar për të ndërtuar deri një përfaqësim.
Ne do të kemi dy opponent-- ose dy lojtarë, kompjuteri ynë
lojtar dhe një lojtar të njeriut.
Numër lojtar nuk do të luajnë O. Kjo do të jetë lojtar makinë.
Ata marrin për të lëvizur të dytë.
Dhe lojtari tjetër, tonë lojtar të njeriut, do të jetë X.
>> Dhe për të bërë jetën time pak të thjeshtë, unë jam duke shkuar
për emërtim që player njeri negativ.
Kështu që unë vetëm mund të shumohen nga një negativ të bie në ujdi
midis një lojtar dhe të tjera.
Të gjithë të drejtë, kështu që le të marrin një vështrim në ajo që ne jemi të vërtetë do të bëjë.
Ne jemi duke shkuar për të përcaktuar bordit tonë.
Ajo do të jetë, mirë, ne jemi duke shkuar të lejojë që ajo të jetë tre nga tre,
ose ne mund të luajë edhe pesë nga pesë ose shtatë
nga shtatë TIC-TAC-shputë në qoftë se ju do të si, në bazë të disa dimension D.
>> Dhe ne do të kemi një çift e funksioneve ndihmëse
që do të bëjnë gjëra të tilla si nisja e screen-- apo keq,
nisja variablave tanë, të pastruar ekran, barazim bordit në ekran,
ai që kontrollon një bord për të parë nëse janë apo jo
ka një fitues, ai që parses nëpërmjet command line,
vetëm për të ndihmuar jashtë, ai që lexon në input, dhe një funksion të quajtur Minimax.
Dhe kjo është një ne do të kujdesemi më për të.
Por le të shohim së pari në kryesore.
>> Çfarë bëjmë ne?
E pra, ne jemi duke shkuar për analizimi linjë tonë komanduese,
vetëm lexuar në dhe të shohim se çfarë Bordi dimension ne do të donim që të ketë.
Ne do të nisja bordit tonë.
Dhe pastaj ne do të hyjë në një loop e madhe e egër, në mënyrë të përsëritur
pranojë lëviz derisa loja është fitoi, apo nuk ka asnjë lëvizje mbetur.
Sa herë që ne do të shkojmë nëpër atë loop, ne do të qartë në ekran.
Ne do të tërheqë bordit në ekran.
Dhe ne jemi me qëllim lloj abstraguar këto larg si subroutines,
kështu që ne nuk duhet të shqetësohen shumë në lidhje me detajet se si ata të ndodhë.
>> Ju do të keni kodin sot më vonë.
Dhe në qoftë se ju doni të shikoni përmes dhe për të gjetur jashtë, ju mund të shihni të gjithë ata.
Por ne do të tërheqë një bord në ekran.
Dhe pastaj ne do të kontrolloni dhe shohim, nuk kemi një fitues?
Ka dikush fitoi këtë lojë?
Nëse ata kanë, ne do të shtypura një mesazh të fitores.
Dhe ne do të përfundojë lojën.
>> Ne gjithashtu do të kontrolloni dhe të shohim nëse ka një kravatë.
Ajo do të jetë e lehtë për të parë nëse ka një kravatë.
Kjo do të thotë se të gjitha hapësirat janë plot, por nuk ka pasur një fitues ende.
Ne mund të deklarojë një kravatë dhe të bëhet.
Pastaj meat-- e vërtetë në qoftë se kjo është një lojtar makinë,
ne do të lejojmë që lojtar makinë për të kërkuar
përmes përdorimit të këtij algoritmi Minimax, për të gjetur lëvizjen më të mirë se ajo mund.
Dhe pastaj ne do të vënë atë të shkojë deri.
>> Përndryshe, në qoftë se kjo është një lojtar i njeriut, ne do të lexoni disa të dhëna nga njeriut.
Dhe atëherë nëse kjo është e njeriut lojtar ose lojtar makinë,
ne do të bëjmë një çift të vogël pjesë të kontrollit të gabimit,
sigurohuni që ajo qëndron brenda kufijve nga dimensionet aktuale bordi
që ne kemi, sigurohuni që kjo hapësirë ​​është e zbrazët,
se askush nuk e vënë një copë në atje tashmë.
Dhe pastaj ne do të vënë vetëm një pjesë në bord,
ndryshojë lojtar në shtresa tjetër, dhe ardhura Sa lëvizje kanë ndodhur.
>> Kjo është lak kryesor për ynë lojë TIC-TAC-shputë.
Minimax, pra, është pikërisht algoritmi që kemi përpara.
Vetëm rregullim e vetme që ne kemi bërë në mënyrë që ne
mund të luajë më i lartë Bordet dimensionale është ne kemi
mbajtur këtë parametër shtesë të quajtur thellësi.
Dhe thellësi vetëm thotë, në qoftë se unë jam i kërkim në rënie me atë pemë
dhe unë të marrë deri tani poshtë përtej disa thellësi të nivelit
që unë thjesht nuk dua për të shkuar më tej,
Unë jam duke shkuar për të ndaluar dhe vetëm vlerësimin e bordit në atë pikë.
Unë do të kontrolloni dhe të shohim nëse ka një fitues.
Nëse ka një fitues, i kthehen ato.
Përndryshe, unë do të shkoj nëpër një lak.
Dhe unë do të them, për të gjithë lokacionet e mundshme
që unë ndoshta mund të marrë si lëvizje tim, unë do të
të ndërtuar një bord hipotetike që përfshin lëvizje timen në atë bord,
dhe pastaj Recursively quan Minimax.
>> Në qoftë se kjo është lëvizje e mia, unë shkoj për të gjetur ai që e mori rezultatin më të madhe.
Në qoftë se kjo është lëvizja kundërshtarit tim, ne gjejmë ai që e mori rezultatin minimal.
Dhe çdo gjë tjetër është Mbajtja vetëm rekord.
Të gjithë të drejtë, kështu që le të shohim këtë të kandidojë.
Në fakt, ndoshta ne mund të të marrë një çift të vullnetarëve
për të dalë dhe të luajnë TIC-TAC-shputë.
[Padëgjueshme] një, dhe një më shumë, dy, të drejtë atje.
Eja up.
>> Pra, le të shkojnë përpara dhe të rinisni këtë plotësisht.
Pra, hi.
>> Audienca: Hi.
>> SPEAKER: Si e keni emrin?
>> Audienca: Gorav.
SPEAKER: Gorav.
>> Audienca: Unë jam Layla.
>> SPEAKER: Dhe Layla, dhe Layla, sorry.
Eja up.
Gorav, ne do të kemi të shkoni në fillim.
Dhe unë jam duke shkuar për të ju pyes për të jetë një jo tmerrësisht mirë lojtar TIC-TAC-shputë.
OK, kështu që të gjithë presioni është jashtë për ju.
Le të shohim, edhe pse, se makina jonë lojtar në fakt mund të bëjë diçka zgjuar.
Kështu që të shkojnë përpara.
Ju jeni do të shkruani në të cilin të koordinuar ju do të donte për të vënë X tuaj në.
A0, OK, dhe makinë ka shkuar menjëherë dhe të vënë shenjën e saj në A1.
>> Vendos O në bord.
Të gjithë të drejtë, tani të shkojnë përpara.
Ku do të dëshironit të shkoni?
C2.
Lojtari ynë makinë ka marrë sheshi mesme, bllokuar ju.
Kështu që ishte një e mirë, gjë e zgjuar që ajo të bëjë.
Ju keni bllokuar atë.
Kjo është e shkëlqyer.
Ajo merr qoshe atje.
>> Dhe ajo do të detyrojë që të të marrë një hapësirë ​​të kaluar, B0.
Dhe loja përfundon në barazim.
Por ajo luajti një të arsyeshme lojë kundër teje, e drejtë?
Të gjithë të drejtë, faleminderit shumë, Gorav.
>> [Duartrokitje]
>> Të gjithë të drejtë, Layla, ne jemi duke shkuar deri lojë për ju këtu.
>> Audienca: Oh, e madhe.
>> SPEAKER: Ne jemi duke shkuar për të dhënë ju katër nga katër TIC-TAC-shputë.
Tani, në katër nga katër, ju keni për të fituar me katër në një rresht, jo tre në një rresht.
Dhe kjo është e gjitha juaja.
Pra, Layla mori D1.
Ne jemi tani duke shkuar për të ndjekur kompjuter lojtar ynë këtu.
Tre nga tre TIC-TAC-shputë është lloj gjë që është e lehtë për të gjithë ne.
Por është ende e bukur për të parë lojtar kompjuter duke bërë lëvizje të zgjuar.
Katër nga katër merr për të jetë pak e komplikuar.
>> Bërë mirë.
Të gjithë të drejtë, kështu që Layla-së përfundoi.
Oh, dhe ne duhet të kemi përfunduar atje.
Por le të bëjë një më shumë deri këtu.
Pra Layla, faleminderit.
Bërë mirë.
>> [Duartrokitje]
>> Pra jonë lojtar TIC-TAC-shputë shkon përmes dhe gjen vende,
zgjidh ato duke përdorur këtë Minimax.
Dhe kam pasur një mjedis thellësi në atë që ajo
nuk do të kandidojë shumë shpejt, e cila është ndoshta arsyeja pse
Layla ishte në gjendje për të shkuar mirë përpara si ajo e bëri, dhe e bëri shumë mirë.
Por këto sisteme që vetëm shkoni nëpër dhe forca brutale
të shkojnë më thellë dhe më të thellë, dhe më thellë, dhe për të mbajtur gjetjen e zgjidhjes
se ata kanë nevojë, ato llojet e sistemeve të janë mjaft të suksesshëm në këto, mirë,
lojërat standarde bordit.
>> Dhe në fakt, nëse ne shikojmë në një tre nga tre lojë TIC-TAC-shputë,
kjo është në thelb një problem i zgjidhur.
Dhe kjo është një diagram i mrekullueshëm nga Randall Munroe në XKCD,
tregon që lëvizin ju duhet marrë, duke pasur parasysh lëvizjet e kundërshtarit tuaj.
Kjo është diçka që ne mund të lehtësisht të specifikojë para kohe.
Por çfarë ndodh si ne të merrni më shumë lojëra komplekse, lojra më shumë ndërlikuar,
ku ka borde të mëdha, më shumë mundësi, strategji më të thellë?
>> Ajo rezulton se kjo forca brutale në kërkim ende
e bën mjaft mirë, me përjashtim të kur ju merrni deri në pikën
ku kjo pemë është aq i madh që ju nuk mund të përfaqësojnë të gjitha.
Kur ju nuk mund të llogaritin të gjithë pemë, kur ju nuk mund të shkoni përpara dhe shtytje
veten në pikën ku ju keni marrë të gjithë pemë në kujtim,
ose nëse ju mund të merrni atë në kujtesën dhe ajo do të vetëm
të marrë ju rrugë shumë e gjatë për të kërkuar përmes ajo, ju duhet të bëni diçka më të zgjuar.
>> Në mënyrë që të bëni këtë, ju duhet të bëjë dy gjëra.
Së pari, ju duhet të gjeni disa mënyrë për të kufizuar thellësi tuaj.
E pra, kjo është në rregull.
Ne mund të përpiquni të bukur, minimum dhe të thonë, ju vetëm mund të shkojnë në mënyrë të thellë.
Por kur ju bëni këtë, që të të thotë kanë këto borde pjesërisht jo të plota.
Dhe ju duhet të zgjidhni, nuk më pëlqen ky bord pjesërisht i paplotë,
apo ky bord pjesërisht paplotë?
>> Dhe në tonë katër nga katër lojë TIC-TAC-shputë,
lojtari ynë kompjuter mori poshtë në fund dhe ajo tha:
Unë kam marrë dy bordet e ndryshme.
As njëra është një fitore.
As njëra është një humbje.
As njëra është një kravatë.
Si mund të zgjedh mes tyre?
Dhe kjo nuk kishte një mënyrë e zgjuar për të bërë atë.
>> Ne e shohim këtë lloj të Vlerësimi i ndodh gjithë kohës
si ne të merrni në lojëra më komplekse.
Shahu është një shembull i madh.
Në shah, ne kemi, për herë të parë së gjithash, një bord të mëdha.
Ne kemi shumë më shumë pjesë.
Dhe pozicionimin e këtyre pjesëve dhe mënyra se si këto pjesë të lëvizur
është me rëndësi kritike.
Pra, nëse unë dua të përdorni Minimax, Unë duhet të jenë në gjendje të specifikojë
dhe thonë se, ky bord, ku askush nuk ka fituar apo humbur akoma,
është disi më e mirë se kjo të tjera bordi, ku askush nuk ka fituar ose humbur.
>> Për ta bërë këtë, unë mund të bëj gjëra të tilla si unë mund vetëm
numëruar sa copa nuk kam dhe sa copa keni?
Ose unë mund të jap të ndryshme copë pika të ndryshme.
Mbretëresha ime është me vlerë 20 pikë.
Peng juaj është me vlerë një pikë.
Kush ka më shumë pikë gjithsej?
Ose unë mund të konsiderojnë gjëra të tilla si, i cili e mori postin më të mirë e bordit?
Kthehet e të cilit është ajo e ardhshme, çdo gjë që unë mund të
do të vlerësojë më të saktë cila prej këtyre mundësive
është më e mirë pa shteruese parasysh
çdo veprim që mund të vijnë pas kësaj.
>> Tani për të bërë këtë punë, një nga gjërat që është
duke shkuar për të bërë me të vërtetë e rëndësishme për ne nuk është vetëm duke lëvizur drejt
poshtë në një thellësi të veçantë Kufiri, por janë në gjendje për të thënë,
një nga këto ide që unë kanë është aq e keqe se kjo është
mos e konsideruar vlerë të gjitha mënyrat e mundshme
se gjërat mund të shkojnë keq e më keq.
Për ta bërë këtë, ne do të shtoni në Minimax një parim të quajtur alph-beta.
Dhe alfa-beta thotë: në qoftë se ju keni një ide e keqe,
mos e humbni kohën tuaj duke u përpjekur të të gjetur me saktësi se sa e keqe është.
>> Kështu që këtu është ajo që ne jemi duke shkuar për të bërë.
Ne jemi duke shkuar për të marrë të njëjtën gjë Parimet që kishim përpara,
i njëjti tip Minimax e kërkimit, vetëm ne jemi
do të mbajnë gjurmët, jo vetëm nga vlera aktuale që ne kemi, por ne do
mbajnë gjurmët e të mirë të mundshme Vlera që unë mund të merrni,
dhe më e keqja e mundshme Rezultati unë mund të ketë.
Dhe çdo herë më e keqja të jetë e mundur gjë është në kërkim të ngjarë,
Unë do të braktisin atë pjesë të pemës.
Dhe unë nuk do të shqetësojë edhe duke kërkuar në atë më.
>> Të gjithë të drejtë, kështu që të imagjinojmë që të fillojmë me këtë të njëjtën pemë saktë lojë.
Dhe tani ne jemi duke shkuar për të shkuar poshtë përsëri, të gjithë rrugën poshtë
në atë këndin e poshtëm të majtë.
Dhe në atë fund majtas qoshe, ne duken dhe ne vlerësojmë këtë bord.
Ndoshta kjo është një nga katër katër TIC-TAC-shputë bordit, apo ndoshta kjo është një bord shahut.
Por ne e shohim atë, dhe ne vlerësojmë ajo, dhe ne kemi marrë një vlerë prej tetë.
>> Në këtë pikë, ne e dimë se ne jemi duke shkuar për të marrë të paktën
tetë pikë nga ky vendim e poshtme.
Nuk ka rëndësi se çfarë tjetër dy janë, se shtatë dhe se dy.
Ato mund të jenë çfarëdo vlera ata donin të ishin.
Ne jemi duke shkuar për të marrë në paku tetë pikë.
Të gjithë të drejtë, por ne mund të të shkojnë përpara dhe të kontrolloni.
Ndoshta një prej tyre është më e mirë se tetë.
>> Ne shikojmë në shtatë.
A është kjo më mirë se tetë?
Jo, kjo nuk do të ndryshojë mendimi ynë në të gjitha.
Ne shikojmë në dy.
A është kjo më mirë se tetë?
Jo, kjo nuk do të ndryshojë mendimi ynë në të gjitha.
Pra, tani ne e dimë që kemi shteruar të gjitha mundësitë atje.
Ne nuk jemi duke shkuar për të marrë diçka më të mirë se tetë.
Ne jemi duke shkuar për të marrë saktësisht tetë.
>> Dhe kështu që ne ndryshojë këtë nyje dhe të themi, që tani është një siguri.
Ne do të shkojmë deri një nivel më lart se.
Dhe tani ne e dimë diçka në lidhje me atë nivel minimizimin.
Ne e dimë se ne nuk jemi duke shkuar për të marrë më shumë se tetë pikë, nëse ne do të shkojmë poshtë
këtë drejtim.
Sepse edhe në qoftë se ata dy degë të tjera të kthehet
të jetë fantastike dhe me vlerë mijëra pikë secili,
kundërshtari ynë do të na japë minimum, dhe na jep tetë.
Të gjithë të drejtë, mirë, le të shohim.
Ne do të vazhdojmë duke shkuar poshtë këtë rrugë.
Ne do të shkojmë poshtë në atë mes në të majtë.
Ne shikoni poshtë dhe ne shohim ka një nëntë.
Ne e dimë se ne jemi duke shkuar për të marrë të paktën nëntë pikë duke shkuar poshtë
kjo rrugë e mesme.
Dhe në këtë pikë, ne vetëm mund të pauzë.
Dhe ne mund të themi, shikoni, unë di në nivel të lartë,
Unë jam duke shkuar për të marrë jo më shumë se tetë pikë duke shkuar poshtë këtë drejtim.
Por në qoftë se unë shkova poshtë e mesme rrugë në vend të rrugës majtë,
Unë do të marrë të paktën nëntë pikë.
>> Kundërshtari im kurrë nuk do të më lejoni të shkoj poshtë këtë rrugë të mesme.
Ata marrin për të zgjedhur.
Dhe ata do të zgjedhin rrugë të majtë në drejtim të tetë,
sesa në qëndër drejt çfarë është të paktën nëntë pikë.
Pra, në këtë pikë, unë do të ndalet.
Dhe unë do të them, ju e dini se çfarë?
Unë nuk duhet të shikoni ndonjë më poshtë në këtë drejtim.
Sepse unë jam kurrë nuk do të merrni atje.
>> Unë mund të kaloni mbi atë një, dhe unë mund të kaloni mbi atë gjashtë,
sepse kjo nuk do të ndodhë.
Kështu që unë do të shkoj poshtë dhe unë do të konsiderojnë mundësinë e ardhshëm.
Unë shkoj atje poshtë dhe unë them, unë shoh një dy.
Unë e di nëse unë shkoj në këtu, unë jam shkuar për të marrë të paktën dy.
NE RREGULL.
Unë do të mbajë.
Unë shoh një katër.
Unë e di unë jam duke shkuar për të marrë të paktën katër.
Ka ende shumë mes katër dhe tetë, edhe pse.
Kështu që unë do të mbajë.
Unë shikoj poshtë dhe unë shoh se ka një.
Të gjithë të drejtë, unë e di nëse Unë shkoj poshtë këtë rrugë,
Unë jam do të jetë në gjendje të zgjedhin katër.
Çfarë është kundërshtari im, do të bëjë?
Në mes të diçka që më jep tetë, diçka që më jep katër,
dhe diçka që më jep të paktën nëntë,
mirë, ai do të më jepni katër.
Dhe unë e di tani në shumë i lartë, unë jam duke shkuar
të jetë në gjendje për të marrë të paktën katër pikë nga kjo loje.
>> E gjithë ideja e alfa-beta është për të prerë pjesët pema kështu
që unë nuk i shikon ato më.
Por ajo ende duket si unë kam qenë duke kërkuar në një shumë të pemës.
Le të mbajë poshtë.
Ne do të shkojnë poshtë një tjetër tani.
Poshtë në fund, unë gjej një të.
Unë e di unë jam duke shkuar për të marrë të paktën një.
Unë mbaj në kërkim.
>> Kam gjetur një tre.
Unë e di unë jam duke shkuar për të marrë të paktën tre.
Unë do të mbajë.
Kam gjetur një pesë.
Unë e di unë jam duke shkuar për të marrë pesë në qoftë se unë të marrë poshtë në këtë rrugë.
Dhe unë gjithashtu e di pastaj që kundërshtari im, në qoftë se unë
të zgjedhin mes të tre zgjedhje të mëdha,
ai do të më jepni diçka që është pesë ose më pak.
>> NE RREGULL.
Unë mund të mbani duke shkuar atje.
Unë mund të shikoni poshtë dhe unë mund të themi, çfarë jam unë do
për të marrë në qoftë se unë shkoj poshtë në rrugën e mesme?
Unë jam duke shkuar për të marrë, mirë, tre atje.
Unë jam duke shkuar për të marrë diçka kjo është të paktën tre.
Ka ende gjëra në mes të tre dhe pesë, kështu që unë mbajtur në kërkim.
Oh, një nëntë, unë patjetër do të marrë atë mbi një tre.
Unë jam duke shkuar për të marrë të paktën nëntë në qoftë se unë të shkojnë poshtë këtë rrugë të mesme.
>> Tani kundërshtari im ndalet dhe thotë: shikoni, nuk ka asnjë pikë më.
Unë e di se im Kundërshtari minimizimin, ai është
do të më jepni gjë që është me pak se ose te barabarte me pesë,
sesa gjë që është më e madhe se ose e barabartë me nëntë.
I ndaluar.
Unë nuk shikoj asnjë më shumë në atë.
Unë do të mbajë.
>> Unë shikoj poshtë në këtë një të tillë.
Poshtë në fund, unë gjej një gjashtë.
Unë e di unë jam duke shkuar për të marrë të paktën gjashtë.
Dhe çfarë mund të bëj?
Unë mund të ndalet.
Sepse nuk ka një zgjedhje në mes diçka që është të paktën gjashtë
dhe diçka që është më pak se pesë, ai është
do të më jepni gjënë që është më pak se pesë.
Dhe tani unë e di unë jam duke shkuar për të marrë saktësisht atë zgjedhje.
Unë jam duke shkuar për të marrë se pesë zgjedhje.
>> Unë kthehem deri në krye.
Cili jam unë do të zgjedhin midis diçka
që është më e madhe se ose e barabartë me katër, ose diçka që është e barabartë me pesë?
Unë jam duke shkuar për të marrë diçka kjo është të paktën pesë.
Unë shkoj në rrugën e fundit, të gjithë rruga poshtë në fund.
Ka një.
OK, të paktën unë jam duke shkuar për të marrë një pikë.
Unë do të mbajë.
Dy, oh, kjo është më mirë se një.
Unë jam duke shkuar për të marrë të paktën dy.
Kam gjetur një tre.
Unë e di unë jam duke shkuar për të marrë tre.
>> Dhe pikë më lart se, Kundërshtari im po shkon
të më jepni diçka që është me pak se ose te barabarte me tre.
Dhe tani unë mund të ndalet.
Sepse në zgjedhjen midis meje qenit gjendje për të marrë një pesë dhe kundërshtarin tim
mua duke i dhënë diçka më pak se tre, Unë jam gjithmonë duke shkuar për të marrë se pesë.
Kështu që unë nuk e vlerësoj se pjesa e poshtme e pemës në të gjitha.
>> Tani, kjo mund të duket i vogël.
Por, kur pjesë të vogël të aritmetike, madh se dhe më pak se,
mund të prerë larg pjesë të tëra të kjo pemë në rritje eksponenciale,
që të çon në një të madhe shuma e kursimeve, kursimeve
që janë mjaft të mëdha që unë mund të fillojnë të luajnë konkuruese
në lojëra më komplekse.
>> Të gjithë të drejtë, nëse ne shikojmë në madhësinë dhe kompleksitetin e lojra të ndryshme,
TIC-TAC-shputë ishte shembulli ynë i lehtë.
Ne kemi marrë një bord të vogël, tre nga tre.
Ne kemi marrë, më së shumti, një mesatare prej rreth katër zgjedhje të ndryshme
si të shkojmë përmes lojës.
Ne kemi diku rreth 10 të pestë e mundshme gjethe të ndryshme.
Dhe ndërtimin e një TIC-TAC-shputë lojtar, mirë, ne vetëm e bëri atë.
Është e lehtë.
>> Në qoftë se ne do të shkojmë deri në diçka më shumë kompleks, si Connect Four.
A ju kujtohet këtë lojë Ku ju drop argumentet pak në?
Kjo është një nga gjashtë shtatë bordit, jo se shumë më të madhe, ende
ka afërsisht të njëjtën bronkial si faktor TIC-TAC-shputë.
Unë kam rreth katër zgjedhje ku unë mund të vënë gjërat në.
Por tani, unë kam marrë shumë më tepër çon, 10 në fuqinë e 21.
Kjo është diçka që është e lehtë e mjaftueshme që ne të zgjidhur atë menjëherë.
>> Damë, më shumë ju complex-- mori një tetë nga tetë bord.
Ju jeni vetëm në gjysmën e ata në çdo kohë, edhe pse.
Ju keni marrë një bronkial faktor që është rreth 2.8.
E pra, ne kemi marrë një çift lëviz ju mund të merrni.
Ju keni marrë rreth 10 deri lë 31, hapësira të mëdha, dhe të mëdha, dhe më të mëdha.
Si unë duhet të kërkoni përmes këto hapësira më të mëdha,
kjo është kur gjëra të tilla si alfa-beta dhe duke qenë në gjendje për të prerë larg degët gjithë
bëhet e domosdoshme.
>> Tani, damë ishte e lehtë të mjaftueshme në vitin 1992.
Një program kompjuterik i quajtur Chinook mundi damë botërore
kampion, Marion Tinsley.
Dhe që nga atëherë, nuk ka lojtar mjeshtër njerëzore ka
qenë në gjendje të mundë të mirë sistemet kompjuterike.
Nëse ne shikojmë në diçka si shah, tani përsëri, ne kemi një tetë nga tetë bord.
Por ne kemi shumë më komplekse copë, shumë lëvizjet më komplekse.
Ne kemi një faktor bronkial prej rreth 35, 35 lëvizjet e mundshme mesatarisht
që unë mund të marrë, dhe një shtet hapësirë, një numër i lë
që është rritur në 10 për fuqinë 123, Numrat e mëdha të mundësive.
>> Por ende procesorë moderne janë në gjendje për ta bërë këtë me sukses.
Në vitin 1995 dhe më pas në vitin 1997, një kompjuter Programi i quajtur Deep Blue ndërtuar nga IBM
që u zhvillua në një Superkompjuteri gjigand mundi kampionin aktual botëror,
Garry Kasparov.
Kjo ishte një pikë kthese.
Sot, megjithatë, që të njëjtën përpunimi Fuqia ulet në MacBook tim.
>> Shpejtësi të përpunimit mban duke marrë më të shpejtë dhe më të shpejtë.
Ne mund të vlerësojnë gjithnjë e më shumë bordet më të shpejtë dhe më të shpejtë.
Por më e rëndësishmja, ne kemi më të mirë Funksionet e vlerësimit dhe tëharrje mirë
metodat.
Pra, ne mund të kërkoni në hapësirë ​​më mënyrë komplekse.
Më i madh i bordit lojëra që ne mund të mendoni,
diçka e tillë Shko kjo është mori një 19 nga 19 bordit,
tani papritmas, ne jemi e kaluara në pikën ku sistemet kompjuterike mund të fitojë.
Nuk ka kompjuterike sistem atje
që mund të mundi një lojtar profesionist Go.
Të mirë të sistemeve sot Rank atë për lloj niveli të mirë amator.
Pra, ka ende mjaft pak jashtë atje se ju nuk mund të merrni për të ende.
>> Të gjithë të drejtë, këto lojërat tradicionale bordit,
këto lloje të sistemeve ku ne ndërtuar këtë Minimax, nëse atë e mori
alfa-beta apo jo, këto algoritme punë sepse ka kufizime të caktuara.
Ne kemi informacion të përsosur rreth botës.
Ne e dimë se ku të gjitha pjesët janë.
Bota është statike.
Askush nuk e merr për të lëvizur copa rreth ndërsa unë jam i
i ulur aty duke menduar, duke marrë nga ana ime.
Ka një hapësirë ​​veprim që është diskret.
Unë mund të vënë peng tim këtu, ose unë mund të vënë peng tim këtu.
Unë nuk jam i lejuar për të vënë peng time në vija në mes të dy sheshet.
>> Dhe në fund, veprimet janë determinist.
Unë e di se në qoftë se unë them, Sorrë për kalorës tre,
Sorrë ime do të përfundojë deri në kalorës tre, për sa kohë që kjo është një veprim i vlefshëm.
Nuk ka asnjë pasiguri në lidhje me atë.
Tani, ndërsa unë shkoj në më shumë lloje të ndryshme të lojrave,
ne kemi për të thyer këto supozime.
>> Çka nëse unë shkoj në diçka si video games klasike?
Ja një përzgjedhje e videos lojra nga Atari 2600.
Çfarë mund të ketë deri atje?
Unë kam marrë Frogger, Hapësirë Pushtuesit, kurth dhe Pac-Man.
Çfarë lloje të mjediseve a kam këtu tani?
Cila nga këto supozime nuk kam për të thyer?
>> E pra, kjo varet lojës.
Unë mund të luajë shah në 2600, dhe ajo do të jetë ashtu siç ishte më parë.
Për shumicën e këtyre sistemeve, ka njohuri të plotë rreth botës.
Ka plotësisht Veprimet determinist.
Por zakonisht, në botë nuk statike.
Kjo është, ndërsa unë jam i ulur aty duke pritur, diçka po lëviz.
Fantazmat po vijnë për të marrë mua.
Akrepi është duke ndjekur më poshtë.
Pushtuesit hapësirë ​​janë vijnë më afër dhe më afër.
Sa mirë mund të bëjmë kundër tyre?
>> Disa vjet më parë, Google kishte një projekt i quajtur
DeepMind, ku ata të trajnuar një kompjuter Programi për të luajtur Atari 2600 lojra.
Dhe në qoftë se ju mendoni se kjo nuk është serioze biznes, rezultatet e studimit të tyre
janë botuar në Nature, kështu vetëm për aq i mirë një botim
si ju ndoshta mund të merrni.
Dhe këtu është se sa mirë ata kryer.
>> Ata kanë një algoritëm që kalëronte dhe shikuar vetëm inputeve ekran.
Ajo mori asnjë instruksionet whatsoever për rregullat e lojës.
Dhe kjo është dashur të kuptoj se, bazuar rezultatin e saj, sa mirë ajo ishte duke bërë.
Ky ishte një sistem që përdoret diçka quajtur mësuarit përforcim.
Kjo është, ajo dukej në rezultatin e saj.
Dhe në qoftë se ajo mori një rezultat të mirë, ajo tha: Unë duhet të mbani mend këto gjëra.
Dhe unë duhet të bëjë ato përsëri.
Dhe në qoftë se ajo mori një rezultat të keq, ajo tha: Unë nuk duhet të bëjë këto gjëra përsëri.
>> Kjo është performanca e atyre sistemeve të trajnuar
lejohet të luajë për një Disa orë në çdo lojë,
krahasuar kundër lojtarë profesional.
Pra, për të gjithë lojrat që janë në anën e majtë të kësaj linje,
ky vetë-trajnuar program kompjuterik tejkaluar lojtarë profesionale.
Dhe për çdo gjë në drejtë, lojtarë profesionale
ishin ende më të mirë.
Për diçka që e dinte asgjë për rregullat, që
nuk dinte asgjë në lidhje me strukturën e lojra, kjo është performanca mbresëlënëse.
Dhe kjo është ajo që ne jemi në gjendje të bëjmë sot.
>> OK, ju thoni, por nëse ne mendoni rreth AI në lojëra,
normalisht ne mendojmë në lidhje me gjëra që ne mund të vërtetë të
ulen dhe të luajë kundër.
Nëse unë ulem dhe unë të luajë StarCraft, ose unë luaj Lirë sitë,
kundërshtari kompjuteri është Personi kontrollin e Zerg,
ose kontrollin e civilizimin tjetër.
Si mund ata lojtarë në fakt të gjetur lëvizjet e tyre?
>> E pra, këto lojëra janë të strukturuara shumë të njëjtën mënyrë si lojrat tona bordit,
këto lojëra që ne do të kolektivisht quajmë katër X Games,
shqyrtuar, expand-- harrojnë ato.
Cilat janë ato?
Explore, të zgjeruar, dhe shuajnë, Unë mendoj se është e fundit.
Por ata janë në thelb eksplorimit dhe sundo lojërat.
Në mënyrë tipike, kundërshtari kompjuter nuk ka informacion të kufizuar.
Ata nuk e dinë saktësisht se çfarë është ndodh pas atë mjegull e luftës.
Ata nuk e merrni për të parë se çfarë ju keni në inventarin tuaj.
>> Ka një mjedis që është dinamik.
Çdo gjë po ndryshon gjatë gjithë kohës.
Ju nuk e merrni për të ulur dhe të presim për të marrë lëvizje tuaj.
Por gjërat më janë ende diskrete.
Unë kam për të vënë qytetin tim këtu.
Ose unë kam për të vënë qytetin tim këtu.
Dhe çdo gjë është determinist.
Kur them, lëvizin njësi e mia këtu, njësi e mia lëviz këtu, nëse një pengesë papritmas
vjen në lojë.
Tani, kjo nuk është e gjitha kompjuter lojëra që janë atje sot.
>> Nëse unë shkoj dhe unë të luajë një lloj të parë personi lojë, diçka si Thief ose Grindja
ose Skyrim, apo Halo, tani Unë kam kundërshtarët kompjuter
se janë atje që kanë një situatë shumë të ndryshme.
Ata kanë, përsëri, informacion të kufizuar.
Ata vetëm mund të shohin një fushë të caktuar të mendimit.
Mjedisi është ende dinamik.
Gjërat po ndryshojnë gjatë gjithë kohës.
>> Por tani unë kam një shumë më të hapësirë ​​vazhdueshëm veprim.
Unë mund të jetë vetëm një peeking pak nga porta.
Dhe disa lojëra, im veprime janë stochastic.
I merrni për të përpiqet të hidhen mbi atë mur, por unë kam marrë një shans për të dështuar.
Këto lloje të lojrave po afrohet dhe më afër llojet e kontrollorëve
që ne ndërtojmë në robotikë.
>> Në robotikë, ne duhet të supozojmë se ne kemi informacion të kufizuar.
Ne kemi sensorë që na thoni në lidhje me botën.
Ne kemi një gjithmonë në ndryshim, mjedis dinamik.
Ne kemi një botë në të cilën hapësirë ​​është i vazhdueshëm, në vend se diskrete.
Dhe veprimet tona, kur ne përpiqemi ata, kanë një shans për të dështuar.
Dhe në fakt, lojë moderne kontrolluesit për kundërshtarin tuaj Halo,
ose për ato NPCs në Skyrim, në thelb drejtuar arkitekturave të vogla robotikës.
>> Ata ndjejnë botën.
Ata ndërtojnë një model të botës.
Ata llogaritin bazuar mbi një sërë Qëllimet se ata do të donim për të kryer.
Ata planifikojnë veprime të bazuara në atë që ata e dinë.
Dhe ata janë pikërisht të njëjtat lloje të i sistemeve që ne të ndërtojmë në robotikë.
Pra këto arkitektura, për të sjell këtë përsëri së bashku,
janë shpesh mjaft të njëjta.
>> Pra, le të shohim nëse ne mund të shohim se.
Le të kthehemi në tonë TIC-TAC-shputë shembull.
Dhe unë jam duke shkuar për të kërkuar një çift të mia post-docs për të dalë dhe për të ndihmuar mua.
Pra Chen Ming, dhe Alessandro, dhe Olivier, në qoftë se ju djema do të dalë.
Dhe unë jam duke shkuar për nevojë një çift i vullnetarëve
>> OK, unë pashë një e djathtë lart atje në mes.
Më lejoni të marr një më shumë, dikush më tej në shpinë ndoshta.
Të gjithë të drejtë, atje.
Eja up.
Në rregull.
Pra, le të marrë atë poshtë mbuluar.
Dhe në qoftë se ju djema do të vijë të drejtë mbrapa rreth këtu për mua, fantastike.
>> Pra, kjo është një robot të quajtur Baxter.
Dhe Baxter është një robot që është një platformë komerciale, i projektuar
nga një kompani e quajtur Rishikimi i.
Dhe ky robot është projektuar për prodhimin në shkallë të vogël.
Por sot ne jemi duke shkuar për e përdorin atë për të luajtur TIC-TAC-shputë.
Tani, ky robot është gjithashtu diçka kjo është relativisht unik.
Sepse në qoftë se unë ishin në këmbë kudo në afërsi të një automatizimi fabrikës standarde
sistem, unë do të jetë në shumë e rëndë rrezik për të qenë të plagosur.
>> Baxter, megjithatë, është projektuar të jetë relativisht të sigurt për të bashkëvepruar me.
Dhe kështu që unë mund të shtyjë në këtë robot.
Dhe ju mund të shihni se është pak bit fleksibël si ajo lëviz përreth.
Dhe unë mund të reposition atë ku unë do të doja që ajo të shkojë.
Tani në një sistem normal robotik, ne do të kemi një sërë nyjeve këtu
që do të jetë drejtpërdrejt përgjigjur komandave pozicion.
Dhe ata nuk do domosdoshmërisht të kujdesit në qoftë se ata ishin duke lëvizur nëpër ajër të hapur,
ose në qoftë se ata ishin duke lëvizur përmes ribcage tim.
>> NE RREGULL.
Dhe zakonisht, në qoftë se keni qenë këtu me një sistem industrial,
ju do të shkoni askund afër saj.
Nuk do të jetë e verdhë shirit të sigurisë të gjithë rreth tij.
Ky sistem ka një dizajn pak më të ndryshme
të jenë më miqësore dhe më e lehtë për njerëzit për të bashkëvepruar me,
në se në çdo të përbashkët, ka një pranverë.
Dhe në vend se kontrollin një pozicion të saktë,
ne kontrollojnë një sasi të caktuar të çift ​​rrotullues, një sasi të caktuar të forcës,
që ne do të dëshironim që të jetë në këtë pranverë.
Të gjithë të drejtë, kështu që le të më marrë vullnetarët tanë këtu.
Pershendetje si quheni?
>> Audienca: Louis.
>> SPEAKER: Louis.
Kenaqesi qe te shoh.
Dhe?
>> Audienca: David.
>> Kryetari: David.
Gëzohem që u njohëm.
Në qoftë se ju djema do të presë këtu për një të dytë,
Unë jam duke shkuar për të ju jap një shans për të bërë këtë.
Pra ky robot, në qoftë se keni ardhur deri dhe në qoftë se ju shtyjnë të butë në të,
ju jeni do të shihni se ajo lëviz pak.
Dhe në qoftë se ju kap atë të drejtë këtu në dore vetëm
sipër ku këto butona janë, atë duket sikur ju duhet të kap butonat,
por kap drejtë mbi këtë vend të kësaj, ju do të të jetë në gjendje për të manipuluar atë shumë të butë
nëpër hapësirë.
Louis, ju doni të jepni një provoni?
Pra, t'i jepte pak të shtyjë për të filluar me.
Dhe pastaj nëse ju vënë gishtat ka të drejtë dhe të mbajë mbi të,
sepse ai do të shkojë për ju pastaj.
Të gjithë të drejtë, ju doni të jepni një provoni?
Eja up.
Pra, t'i jepte vetëm një i butë shtytje atje për të filluar.
Ju mund të ndjeni se çfarë është si.
Dhe pastaj në qoftë se ju kap atë të drejtë atje, ju do të jetë në gjendje për të manovruar në rreth.
>> NE RREGULL.
Pra në mënyrë tipike, ky lloj i një robot do të të përdoret për prodhimin në shkallë të vogël.
Dhe unë jam duke shkuar për të lëvizur këtë krah vetëm poshtë nga rruga pak këtu.
Por sot, ne jemi duke shkuar për të përdorur njëjtë TIC-TAC-shputë sistem playing
bazuar në Minimax që kemi ndërtuar më herët.
NE RREGULL?
Pra, ju djema janë secila do të luajë një lojë.
Louis, ju jeni do të jetë i pari.
Më lejoni vetëm të mbajë deri këtu për një të dytë.
Unë do të ketë të drejtë të qëndrojë këtu, vetëm kështu që të gjithë mund të shoh ty.
Janë të vendosur ju djema deri këtu?
>> ROBOT: Mirë se vini.
Le të luajnë TIC-TAC-shputë.
Mos kuptoj shenjë tuaj para Unë them se është rradha juaj.
Unë të fillojë lojën.
Është radha ime.
SPEAKER: Tani, në qoftë se ju mund të marrë një nga copa tuaj dhe të shkojnë përpara dhe vendin e saj.
ROBOT: Kjo është rradha juaj.
[Qeshura]
Është radha ime.
[Qeshura]
Kjo është rradha juaj.
SPEAKER: Raca njerëzore është numëruar mbi ju këtu, Louis.
>> ROBOT: Është radha ime.
>> SPEAKER: Pra Baxter bllokuar me sukses këtu.
>> ROBOT: Kjo është rradha juaj.
Është radha ime.
Kjo është rradha juaj.
Është radha ime.
SPEAKER: Dhe ne do të le Baxter përfundojë jashtë lëvizjen e saj të fundit këtu.
>> [Qeshura]
>> ROBOT: Kjo është një kravatë.
Unë do të fitojë herën tjetër.
>> [Qeshura]
>> SPEAKER: Të gjithë të drejtë, Thanks very much, Louis.
Faleminderit.
Ju mund të shkoni në këtë mënyrë.
>> ROBOT: Unë të fillojë lojën.
SPEAKER: Pra më lejoni të shpjegoj për ju një pak më shumë
bit para se të merrni rematch tonë këtu.
Çfarë saktësisht po ndodh?
Pra robot ka një kamera deri të lartë këtu.
Dhe është duke kërkuar poshtë në bord.
Dhe kjo është duke parë nëse atë e mori një O të kuqe ose një blu
dhe X. bardhë si ato të vendoset në bordit, kjo është në thelb e njëjtë të dhëna
se ne do të jetë e lexuar nga Struktura jonë e të dhënave nga ekrani tonë.
Kjo është drejtimin e njëjtë Minimax algoritmi të jetë
gjendje për të gjetur se ku për të vendosni një shenjë të mirë.
>> Dhe pastaj ne jemi duke i dhënë një urdhër për ku ne do të donim një shenjë që do të vendosen.
Krahu është duke lëvizur jashtë.
Është përdorur një gripper vakum për të aplikuar disa thithje në atë copë druri,
marr atë, lëvizin atë në të djathtë vend, dhe pastaj lirimin e thithje
dhe të heqë atë.
Të gjithë të drejtë, ne jemi duke shkuar për të dhënë atë një e shtënë më shumë
me një lojtar pak të zgjuar këtu.
Jeni gati?
Të gjithë të drejtë, në qoftë se ju do të qëndroni të drejtë deri këtu dhe të japin a-- kthehet në këtë mënyrë
kështu që ju mund të shihni të gjithë.
Dhe pastaj [e padëgjueshme].
>> ROBOT: Është radha ime.
>> SPEAKER: Baxter do të fillojë.
Kjo është rradha juaj.
Është radha ime.
Kjo është rradha juaj.
Është radha ime.
>> [Qeshura]
>> SPEAKER: [WHISPERING] Vetëm le të shkojë përpara dhe të fitojë.
ROBOT: Kjo është rradha juaj.
SPEAKER: Kjo është në rregull.
>> ROBOT: Është radha ime.
>> [Qeshura]
>> Unë fitoj.
>> [Qeshura]
>> Unë të fillojë lojën.
>> SPEAKER: Të gjithë të drejtë, thank you very much.
Të gjithë të drejtë, unë mendoj se ne kemi marrë kohë për një më të shkëlqyer lojtar TIC-TAC-shputë,
dikush që mund të bëjnë këtë gjë për ndeshje, kush e di se çfarë ata po bëjnë.
>> [Qeshura]
>> Kush do të jetë kampion ynë këtu?
Të gjithë të drejtë, miqtë tuaj vullnetarisht ju.
Kjo është mjaft e mirë për mua.
Tell me emrin tuaj përsëri.
Audienca: Tamir.
SPEAKER: Tamir, të këndshme për të parë ty.
Të gjithë të drejtë, përsëri, ne jemi duke shkuar për të vënë ty të drejtë deri këtu kështu që të gjithë mund të shoh ty.
Ju jeni përfaqësuesi ynë në këtë ndeshje tani.
Baxter është një dhe oh dhe oh.
Ose keq, një oh dhe një.
Dhe kjo e deri tek ju këtu.
Baxter do të merrni për të lëvizur për herë të parë, edhe pse.
Kështu që.
ROBOT: Është radha ime.
>> [Qeshura]
>> Kjo është rradha juaj.
Është radha ime.
Kjo është rradha juaj.
Është radha ime.
Kjo është rradha juaj.
>> [Qeshura]
ROBOT: Është radha ime.
SPEAKER: Është shumë e vështirë kur ju jeni duke qëndruar këtu, folks.
[Qeshura]
ROBOT: Ju njerëzit janë kaq të lehtë për të rrahur.
[Qeshura dhe duartrokitje]
SPEAKER: Faleminderit shumë.
ROBOT: Unë fitojë.
Unë të fillojë lojën.
>> Kryetari: Të gjithë të drejtë, kështu që falë shumë shumë për Olivier, dhe të Alessandro,
dhe për Chen Ming.
>> [Duartrokitje]
>> Dua të bëj një pikë të fundit.
Pra Baxter në shumë përfundojë atje, mashtruar.
Dhe kjo ishte e papritur.
Një nga fantastik gjëra në lidhje me AI është që ne
të bërë punë në UA në mënyrë që ne mund të ndërtojmë me të vërtetë interesante dhe inteligjente
pajisje.
Por ne gjithashtu bëjmë punën në UA sepse ajo na tregon diçka
për mënyrën se si njerëzit janë inteligjente.
>> Një nga preferuar Studimet nga laboratorin tim është
duke kërkuar në çfarë ndodh kur makina papritur mashtrojnë.
Ne nuk e bëri këtë në fillim me Baxter luajtur TIC-TAC-shputë,
por me një robot të vogël të quajtur Nao, i cili luajti rock-letër-gërshërë.
Dhe ndonjëherë pas duke luajtur shumë dhe shumë
i mërzitshëm rock-letër-gërshërë lojra, robot do të hedhin një gjest,
humbasin, dhe pastaj papritmas të ndryshojë gjest i saj dhe them: Unë të fitojë.
>> [Qeshura]
>> Tani, nganjëherë ne do të kemi robot, vetëm si një kontroll, hedhin një gjest,
të fitojë, dhe për të ndryshuar gjest saj për të humbur, të hedhur ndeshjen,
mashtrojnë në mënyrë që të humbasin.
Dhe kjo nuk është gati si bindëse.
Roboti që cheats në mënyrë që të fitojë njerëz
përgjigjen si në qoftë se ajo është e jashtë për të marrë ato, si ajo
po kërkon aktivisht shkatërrimin e tyre.
>> [Qeshura]
>> Kjo bëhet një agjent.
Ajo është si një person.
Ajo ka besim dhe qëllimin.
Dhe kjo nuk është qëllimi i mirë.
Dhe robot që hedh lojë është vetëm mosfunksionimi.
Është vetëm një pajisje të thyer.
Më lejoni t'ju tregoj disa shembuj e që nga disa prej pjesëmarrësve tanë.
Kështu që këtu është cheating në mënyrë që të humbasin.
>> [VIDEO rishikim]
- [E padëgjueshme] fitojë.
Le të luajmë.
>> -Wait, Çfarë?
>> - [E padëgjueshme] fitojë.
Le të luajmë.
>> [Padëgjueshme] fitojë.
Le të luajmë.
>> SPEAKER: dhe këtu e mashtrimit për të fituar.
>> -Po, Unë të fitojë.
Le të luajmë.
>> -ju Nuk mund ta bëjë këtë.
>> [Qeshura]
>> -Po, Unë të fitojë.
-ju Mashtruar.
Ju mashtruar tani.
>> -Po, Unë të fitojë.
>> Hej, ju cheater.
Ju mashtrojnë, super mashtrojnë.
>> [END rishikim]
>> SPEAKER: Këto ndryshme Reagimet me shpejtësi
ndryshojë perceptimin tonë të pajisjes.
A do të thotë se ne qëllimisht ndërtojmë
makina që mashtrojnë, sepse kjo është inxhinieri më i mirë që ne mund të bëjmë?
Jo, por ai na tregon diçka me të vërtetë interesante në lidhje me njerëzit.
Kjo gjë që ju dhe cheats vjedh fitorja juaj, kjo është
diçka që është e gjallë, kjo është animate, kjo është jashtë për të marrë ju.
Ajo ka gjendjen mendore.
Ajo ka besim.
Ajo ka ndërmend.
>> Kjo gjë që duart e lojë për ju, kjo nuk është.
Kjo është vetëm mosfunksionimi.
Kjo është në shumë mënyra pse është e e lehtë për të hedhur lojën me fëmijët.
Por nëse ju përpiqeni të mashtrojnë ato dhe lloj pretendojnë fitoren
kur, ju e dini, vetëm për të shkurtuar lojë, ata do të kapur ju menjëherë.
Këto lloje të efekteve që ne shohim që vijnë nga UA,
ata na mësojnë shumë për veten.
>> Të gjithë të drejtë, kjo është ajo për sot.
Faleminderit shumë për Davidin dhe ekipi i prodhimit Harvard
për të ardhur poshtë.
>> [Duartrokitje]
>> Ne do të shohim ju për quiz një, dhe pastaj për një leksion të fundit.
Kalofsh nje dite te mire.
>> [Duartrokitje]
>> [Muzika]
DAVID J Malan: E pra, ndoshta ne kemi nevojë për të futur një lloj të encryption,
e drejtë?
Sepse atëherë headers të këto HTTP kërkesa do të jetë
fërguara në mënyrë që kushdo duke u përpjekur për të gërhas trafikun tuaj
në fakt nuk do të jetë në gjendje të shohin ato.
Pra, çfarë është zgjidhje për këtë problem?
E pra, ne kemi nevojë që në fakt të futur kodimi në formulë,
kështu që kur ai person është i transmetimit të të dhënave nga A në B,
ne mund të sigurtë send--
>> [Qeshura]
>> Informacioni në një mënyrë që kundërshtari nuk mund, në fakt, e shohin atë.