[CHWARAE CERDDORIAETH] SIARADWR: Croeso yn ôl, bawb. Mae hyn yn CS50. A heddiw, mae gennym lawer o bethau diddorol i siarad am. Yn gyntaf, fodd bynnag, mae'n rhaid i mi atgoffa chi o ychydig o bethau gweinyddol. Mae'r wythnos hon yn un cwis, dydd Mercher neu ar gyfer yr adran Yale ar ddydd Mawrth a dydd Iau, ar ddydd Iau. Mae adolygiadau cwis heno yn Iâl, 5:30-07:00. Yn Harvard, maent yn cofnodi un ddoe. A gall pawb weld bod ar-lein. Hefyd, yr wythnos hon neu ddechrau'r wythnos nesaf, yr ydym wedi ein darlith CS50 diwethaf. [Griddfan] Yr wyf yn gwybod. Daeth mor fuan. Bydd myfyrwyr Iâl yn cael byw ddarlithio yma yn yr ysgol y gyfraith awditoriwm ar ddydd Gwener. Bydd yna teisen. Bydd myfyrwyr Harvard yn cael y Darlith olaf yn Sanders ar ddydd Llun. Bydd hefyd cacen. Hefyd, yr wythnos hon ar ddydd Gwener, ar gyfer y rhai ohonoch sydd yn dod i New Haven, mae gennym y Expo CS50. Mae gennym fwy na 30 gwahanol grwpiau cofrestredig i ddangos popeth yr ydych yn o hwylio ymreolaethol, i systemau sy'n cydnabod portreadau digidol, i gyfrifiadur cerddoriaeth a cherddoriaeth a gynhyrchir gan gyfrifiadur. Felly, os gwelwch yn dda ymuno â ni. Rwy'n credu ei fod yn mynd i fod yn amser gwych. Heddiw, fodd bynnag, rydym yn dod i parhau i siarad am AI, am deallusrwydd artiffisial. Ac un o'r pethau y rydym yn mynd i gael i heddiw yw'r syniad o sut i defnyddio AI i ddatrys problemau. Yn awr, fel bob amser, gadewch i ni ddechrau gyda rhywbeth syml. Ac rydym yn mynd i ddechrau gyda syniad syml. A dyna defnyddio chwiliad. Felly dychmygwch am funud fy mod cael tasg sydd angen i mi berfformio. Ac fe hoffwn i gael y dasg awtomataidd gan rai asiant meddalwedd. Dychmygwch fy mod i'n ceisio archebu set o teithiau o, gadewch i ni ddweud, Boston i San Francisco. Gallwn fynd drwy'r ac y gallwn i eu defnyddio un o'r chwilio ar-lein gwych offer, sydd yn mynd i wneud yn y bôn yr un broses ein bod mynd i gerdded trwy'r heddiw. Ond os nad oedd yn rhaid eich bod yn offeryn, beth fyddech chi'n ei wneud? Wel, gallech edrych a gweld ac yn dweud, Im 'yn Boston. Pa teithiau sydd ar gael i mi? Yn awr, efallai gen i dri hedfan posibl y tu allan i Boston a fydd yn cyd-fynd yr amser pan fydd angen i mi adael. Gallwn i hedfan i Chicago. Neu gallwn i hedfan i Miami. Neu gallwn i hedfan i Efrog Newydd. Gallwn i yna edrych o bob un un o ddinasoedd cyrchfan rhai a meddwl am yr hyn y lleoliadau Allwn yn fy myw cyrraedd o bob un o ddinasoedd unigol hynny. Felly efallai o Chicago, gallaf gael hedfan yn uniongyrchol i San Francisco. Mae hynny'n ardderchog. Neu gallwn i gael hedfan i Denver. Yn awr, efallai y hedfan i San Francisco yw'r ateb perffaith i mi, ond efallai na. Efallai fy mod yn chwilio am rywbeth mae hynny'n ychydig yn rhatach neu ychydig yn well ar gyfer fy amserlen. Ac felly gallwn i edrych am yr hyn eraill Efallai y posibiliadau fod allan yno. Felly, gallwn i edrych ar Denver. Ac o Denver, wel, efallai Gallaf gael hedfan i Austin. Ac o Austin, efallai y gallaf gael hedfan i Phoenix, ac o Phoenix i San Francisco. Nawr, dydw i ddim yn ei wneud eto. Oherwydd efallai mae 'na hedfan yn uniongyrchol o Efrog Newydd i San Francisco mae hynny'n berffaith i mi. Neu efallai mae 'na hedfan o Miami drwy Denver hynny'n llawer rhatach. Felly, yr wyf yn dal rhaid i chi fynd. Ac yn dal yn rhaid i mi edrych ar yr holl o'r rhai a dinasoedd nad wyf wedi ymchwilio eto. Mae'n rhaid i mi wirio drwyadl bob un y posibiliadau y gallai gen i. Felly, o Efrog Newydd, efallai y gallaf gael hedfan i Nashville, ac o Nashville i Austin. Ac yna yr wyf yn gwybod lle yr wyf. Ac yna yr wyf yn gwybod o Austin, gallaf hedfan i Phoenix, ac o Phoenix i San Francisco. Os byddaf yn hedfan yn gyntaf i Miami, fodd bynnag, efallai y gallaf gael hedfan o Miami i Nashville, neu o Miami i Austin. Ac yn awr yr wyf wedi rhoi cynnig ar bob o'r posibiliadau. Rwyf wedi adeiladu i fyny graff hwn sy'n dangos i mi yr holl lwybrau posibl y gallai fy mod yn gallu cymryd. Pan rydym yn cynrychioli rhain mathau o broblemau, Nid ydym yn mynd i gynrychioli hwy benodol fel y graff hwn, oherwydd nad yw graff yn cynrychioli hanes o ble yr ydym wedi mynd. Mae gwybod fy mod yn hedfan o Ffenics i San Francisco Nid ddweud wrthyf a mi ddod drwy Nashville, neu drwy Denver, neu drwy Miami. Felly beth 'n annhymerus' yn ei wneud yn lle hynny yn Byddaf yn cymryd un broblem hon, a byddaf yn cynrychioli fel coeden. Ac wrth wraidd y goeden, yn y top, 'n annhymerus' rhoi'r lle i mi ddechrau, Boston. Ac o Boston, 'n annhymerus' yn edrych ar pob un o'r lleoliadau posibl y gallaf deithio i. Wel, yn yr achos hwn, roedd gen tri, Chicago, Efrog Newydd, a Miami. Ac yna byddaf yn archwilio pob un o'r plant hyn yn y goeden. O Chicago, gwelais fy mod wedi dwy daith. Gallwn i hedfan yn uniongyrchol i San Francisco neu i Denver. Nawr San Francisco, dyna fy nod. Dyna fy cyrchfan. Mae hynny'n mynd i fod deilen o goeden hon. Hynny yw, nid wyf erioed i'n mynd i fynd rhywle ar ôl San Francisco. O Denver, fodd bynnag, Gallaf hedfan o Denver i Austin, o Austin i Phoenix, ac o Phoenix i San Francisco. Ac yn awr eto, yr wyf wedi cyrraedd ddeilen. Gallwn wedyn fynd yn ôl i'r nesaf dinas nad wyf wedi harchwilio'n llawn. Byddai hynny'n Efrog Newydd, yn mynd yn ôl i fyny i ben fy goeden, dod i lawr i Efrog Newydd. O Efrog Newydd, gallaf hedfan i Nashville, o Nashville i Austin, o Austin i Phoenix, a o Phoenix i San Francisco. Ac yn olaf, un ddinas yr wyf yn Nid wedi edrych ar eto, Miami. Wel, o Miami dywedais, roedd dau posibiliadau, Nashville neu Austin. Os byddaf yn hedfan i Nashville, yn dda yna rwyf yn hedfan o Nashville, i Austin, i Phoenix, i San Francisco. Os byddaf yn hedfan i Austin, yr wyf yn hedfan Austin, i Phoenix, i San Francisco. Ac yn awr mae gen i goeden. Mae'n goeden cyflawn. Mae hyn i gyd o'r posibiliadau a pob un o'r llwybrau y gallwn eu cymryd. Hynny yw, os byddaf yn dechrau yn y gwraidd y goeden ar y brig ac yr wyf yn mynd i lawr i un o'r dail, mae'n dweud wrthyf, nid yn unig lle roeddwn i'n mynd i yn y pen draw, San Francisco, ond mae'n dweud wrthyf y llwybr sy'n Angen i mi gymryd i gyrraedd yno. Yn awr, pa un o'r rhain yw'r gorau? Wel, dim am hyn problem ac eto yn dweud wrthyf pa un o'r rheini yw'r ateb gorau. Efallai fy poeni fwyaf am faint o amser rwy'n yn yr awyr, neu'r pellter a Im 'yn hedfan. Yn yr achos hwnnw, Chicago i San Gallai Francisco fydd y nifer byrraf o filltiroedd yn yr awyr. Efallai fy poeni am gost. Ac rydym i gyd yn gwybod hedfan uniongyrchol fel arfer yn ddrutach. Felly efallai os byddaf yn cymryd hyn fath o lwybr yn ôl drwy Miami, Nashville, Austin, Phoenix, efallai wedyn Yr wyf yn cael pris is. Ond allwn i optimize ar unrhyw meini prawf sy'n Rwy'n poeni am. Pwy sy'n cael y gorau yn hedfan Wi-Fi, neu sy'n meysydd awyr yn cael y bwyd gorau sydd ar gael. Ac mae pob un o'r rhai a allai rhoi ateb gwahanol i mi fy mod yn gweld fel y gorau. Mae'r mathau hyn o broblemau, ble rydym yn mynd i adeiladu allan goeden hon o posibiliadau, ac yna edrych ar bob un o'r rheini llwybrau unigol, ac archwilio pa un o'r cyflawni'r rheini meini prawf i ni, rydym yn mynd i alw problemau chwilio rheini. Ac rydym yn cael llawer o algorithmau, rhai ohonynt rydym wedi gweld yn barod, i fynd ac archwilio coed hynny. Gallem wneud hynny yn y ffordd yr wyf yn yn unig oedd, i chwilio manwl-gyntaf, mynd i lawr mor bell ag y gallwn hyd nes y byddwn daro ddeilen, ac yna dod yn ôl i fyny, ac yn mynd i'r dde yn ôl i lawr. Neu gallem wneud yr hyn sydd Gelwir Chwilio lled-gyntaf. Gallem ehangu'r bopeth ar y brig, ac yna popeth un llinell dan hynny, ac yna popeth un llinell o dan hynny. Mae'r rhai coed chwilio yn sylfaenol i AI. Ond nid ydynt yn hollol cael yn iawn drwy'r amser. Yn wir, mewn llawer o achosion ein bod wir yn poeni am, rydym yn awyddus i adeiladu coeden, ond nid ydym yn ei wneud mewn gwirionedd cael i wneud yr holl benderfyniadau. Mae'r rhain yn sefyllfaoedd o'r enw chwilio wrthwynebus, a elwir hefyd fel sut i ysgrifennu chwarae gemau systemau a chael eich talu ar ei gyfer. Ond mae'r rhain yn y math systemau lle rwy'n Efallai yn cael dewis pan fyddaf yn mynd o Boston, a oedd yn y ddinas yr wyf yn mynd i nesaf. Ond ar ôl hynny, gallai rhywun arall ei gael i wneud y penderfyniad ynghylch lle rwy'n hedfan. Felly, i adeiladu y rhain strwythurau fath, rydym yn mynd i gael i gymryd ychydig agwedd wahanol iddo. Nid ydym yn mynd i fod yn gallu dim ond chwilio drwy y goeden anymore, oherwydd ein bod yn peidio yr un sydd mewn rheolaeth o bob un o'r pwyntiau penderfynu hynny. Felly gadewch i ni dychmygu syml gêm fel tic-tac-blaen. Gallwn i ddechrau â bwrdd hollol wag. Ac yn tic-tac-blaen, X yn cael i chwarae yn gyntaf. Ac felly y gallwn i feddwl am yr holl symudiadau bosibl y gallai X wneud. Ac os fi yw'r un chwarae yr X, mae hynny'n wych. Mae gen i naw bosibl yn symud y gallaf wneud. Gallwn roi X yn unrhyw un o'r rhai a naw o swyddi. Ac yna o bob un o'r rheini, yr wyf yn Gallai ddychmygu beth sy'n digwydd nesaf. Wel, yn yr achos hwn, y llall Byddai chwaraewr yn cael i gymryd eu tro. Byddai O gael i gymryd eu tro. Ac o bob un o'r rheini, mae fyddai wyth lle gwahanol Gallai fod O osod eu marcio. Lets 'ddeud, penderfynais fy mod yn mynd i roi X yn y ganolfan. Mae hynny bob amser yn ymddangos fel symudiad agoriadol da. Gallwn edrych ar dan hynny, mae'r wyth symudiadau posibl y O wneud. Yn awr, os wyf i'n chwarae X, mae hynny'n wych. Rwy'n cael i ddewis pa un yr wyf ewch i, yr un yn y canol. Ond yn awr O cael dewis. Ac nid oes gennyf reolaeth dros y penderfyniad hwnnw. Ond o bob un o'r rheini swyddi bwrdd bosibl, mae yna un arall set o bosibiliadau. Pan ddaw i fod yn Fy trowch eto, fyddwn i cael i ddewis a dweud, wel, os O symud i mewn i'r, wel, y fan a'r lle canol ar y chwith, ac yna Mae gen i set o bosibiliadau lle gallaf gymryd fy cam nesaf. O'r rheini, gallwn i ystyried pob un y posibiliadau oddi tanynt. Ac yna byddai O gael i ddewis ymhlith y rhai. A gallai wyf yn cadw adeiladu'r hyn coeden allan hyd nes i mi gyrraedd y pwynt naill ai lle rywun yn ennill y game-- dyna got i gael ei ystyried deilen node-- neu'r bwrdd yn gwbl llawn ac nid oes unrhyw un wedi ennill. A bod hefyd yn mynd i fod yn nod deilen. Mae hynny'n mynd i fod yn gyfartal. Ond y peth anodd gyda hyn yw os yw hyn yn unig oedd chwiliad rheolaidd problem, byddwn i'n gallu dyweder, yn dda, dylai X ewch yma. A dylai O fynd ffordd dros yno. Ac yna dylai X yn mynd dros yma. Ac yna dylai O fynd ffordd dros yno. Ac yna gall X gael tri yn olynol, ac yr wyf yn ennill. A byddai y gêm fod dros mewn pum symudiadau, tri i mi, dau ar gyfer fy gwrthwynebydd. Ond nid wyf yn bob amser yn cael dewis hynny. Felly, yn hytrach, yr hyn rydym yn mynd i gael i wneud yn rydym yn mynd i gael cael strategaeth newydd. A'r strategaeth sy'n algorithmau gem-chwarae yn aml yn defnyddio yw'r hyn a elwir minimax. Y syniad canolog minimax yw ein bod mynd i ddewis y symudiad sy'n rhoi ein gwrthwynebydd y set gwaethaf posibl o symud y gallant wneud. Nid yw'n gwneud i mi unrhyw da i ddewis symud lle Efallai fy mod yn gallu ennill ar ôl hynny, oherwydd nid fy gwrthwynebydd yn mynd i roi y cyfle i mi. Maent yn mynd i ddewis rhai canlyniad ofnadwy i mi. Felly dw i'n mynd i wneud y symud sydd yn gorfodi fy gwrthwynebydd i wneud rhywbeth yn well i mi. Iawn. Gadewch i ni weld sut mae hynny'n ei chwarae allan. Felly dyma ein algorithm yn pseudocode. Rydym yn mynd i gynhyrchu y goeden gêm gyfan. Rydym yn mynd i adeiladu mae'r strwythur cyfan. Ac yna byddwn yn mynd drwy. Ac ar yr union waelod ym mhob un o'r nodau terfynell, ym mhob un o'r dail, byddwn yn gwerthuso sut y gwerthfawr yw hynny i mi? Ac rydym yn mynd i werth pethau sy'n yn dda i mi fel rhai cadarnhaol. Pethau nad ydynt yn dda i mi yn llai cadarnhaol, neu sero, neu hyd yn oed yn negyddol. Felly, yn tic-tac-blaen, efallai buddugoliaeth i mi yn dda. Dyna un. A thei yn sero. Ac mae rhywbeth sy'n 'na golled ar gyfer mi, efallai mai dyna un negyddol. Mae'r holl sy'n bwysig yw bod y gwell mater i mi, yr uwch yn y sgôr mae'n ei dderbyn. O posibiliadau hynny ar y gwaelod, yna byddwn yn hidlo i fyny. A phan mae'n fy gyfle i ddewis ymysg set o ddewisiadau amgen, 'N annhymerus' yn dewis yr un sydd cael y sgôr uchaf. A phryd bynnag mae'n fy gwrthwynebwyr droi at ddewis, 'N annhymerus' yn cymryd yn ganiataol eu bod yn mynd i dewiswch yr un â'r sgôr isaf. Ac os wyf yn gwneud hyn yr holl ffordd i fyny i ben y goeden, 'N annhymerus' wedi dewis llwybr sy'n rhoi 'm' r canlyniad gorau y gallaf ei gael, gan dybio bod fy gwrthwynebydd yn gwneud yr holl symudiadau cywir. Mae pob hawl, felly gadewch i ni weld hyn ar waith yn gyntaf. Ac yna rydym annhymerus 'mewn gwirionedd edrych ar y cod ar ei gyfer. Felly dychmygwch gen i goeden fawr hon. Ac yn awr Dydw i ddim yn chwarae tic-tac-blaen. Roeddwn i eisiau rhoi i chi rhywbeth ychydig yn gyfoethocach. Felly, yr wyf wedi cael rhai gêm lle mae llawer o wahanol sgorau y gallwn i gael ar y diwedd. Ac felly yr wyf yn adeiladu coeden cyflawn hwn. Ac yr wyf yn cael symud yn gyntaf. Rwy'n wrth wraidd y goeden. Ac yr wyf yn cael dewis that-- felly yr wyf yn ei gael i wneud y gorau ar draws y nod cyntaf. Ac yna fy gwrthwynebydd yn cael i fynd. Ac yna yr wyf yn cael mynd unwaith eto. Felly i lawr ar y gwaelod, mae gen i set o posibiliadau y gallaf ddewis o'u plith, nodi gwahanol terfynol y gêm. Os ydw i'n i lawr yn y pellaf ar y chwith gornel, a gwelaf fod gen i ddewis rhwng wyth, saith, ac mae dau, yn dda, fi yw'r un sy'n cael dewis. Felly dw i'n mynd i ddewis yr un gorau o'r rheiny. Rydw i'n mynd i ddewis yr wyth. Felly, yr wyf yn gwybod os byddaf byth mynd i lawr at y pwynt hwnnw, 'N annhymerus' yn gallu cael hynny wyth pwynt. Os byddaf yn y diwedd ar y pwynt nesaf drosodd, y nôd nesaf dros, naw, yn un, neu chwech, yn dda, rwy'n mynd i ddewis y gorau o'r rheiny. 'N annhymerus' yn dewis y naw. Os byddaf yn cael dewis rhwng dau, a phedwar, ac un, 'N annhymerus' yn dewis y pedwar, yr uchaf. Yn awr, os wyf yn edrych ar y lefel ychwanegol at hynny, mae fy gwrthwynebydd yw'r un yn cael i wneud y dewis hwnnw. Felly, fy gwrthwynebydd yn cael i dewis, ydw i am roi iddo y peth sy'n mynd i gael wyth pwynt iddo, neu ydw i'n rhoi'r peth dyna iddo mynd i roi naw pwynt iddo, neu'r peth sy'n mynd i roi pedwar pwynt iddo? A fy gwrthwynebydd, sef rhesymegol, yn mynd i ddewis y lleiaf o'r rheini, yn mynd i ddewis y pedwar. A gallaf wneud hyn drwy'r goeden gyfan. Gallaf fynd i lawr i'r hyn a set canol o dri. A gallaf ddewis rhwng un, tri, a phump. Ac yr wyf yn cael dewis. Felly, yr wyf yn dewis pump. Gallaf ddewis tri, naw, neu ddau. Yr wyf yn cael dewis, felly yr wyf yn dewis y naw. Chwech, pump, neu ddau, yr wyf yn dewis. Yr wyf yn cael dewis y chwech. Lefel uwch na hynny, pwy sy'n cael i ddewis? Pwy sy'n cael i ddewis? Y dyn arall, fy gwrthwynebydd. Felly, maent yn dewis pump, naw, neu chwech, pa un? GYNULLEIDFA: Y pump. SIARADWR: Maent yn dewis y pump. Maent yn cael dewis y lleiaf. Ac yna yr un olaf, dewis un, dau, neu dri. Yr wyf yn cael dewis, felly yr wyf yn dewis tri. Naw, saith, neu ddau, yr wyf yn dewis naw. A 11, chwech, neu bedwar, yr wyf yn dewis 11. Mae fy gwrthwynebydd wedyn yn dewis tri, naw, neu 11, yn dewis y lleiaf. Mae'n rhoi i mi tri. Ac yna yn olaf ar ben y goeden, yr wyf yn cael dewis eto. Ac yr wyf yn cael dewis rhwng pedwar, pump, neu dri. Felly, yr wyf yn cymryd y pump. Os Ges i reoli popeth, byddwn i'n dilynwch y llwybr a arweiniodd at y 11. Ond dwi ddim yn cael i wneud y dewis hwnnw. Os byddaf yn mynd i lawr y llwybr hwnnw. Bydd fy gwrthwynebydd ngorfodi i mewn y dewis sy'n arwain at dri. Felly, y gorau y gallaf ei wneud yw i gymryd y gangen canol, wneud y dewis hwnnw dyna yn y pen draw mynd i arwain fi i bum pwynt. Dyna beth minimax ei wneud. Iawn. Gadewch i ni edrych ar hynny. Felly dyma yn y CS50 IDE yn rhaglen sy'n gweithredu minimax i chwarae tic-tac-blaen. Rydym yn mynd i adeiladu i fyny cynrychiolaeth. Rydym yn mynd i gael dau opponent-- neu ddau o chwaraewyr, ein cyfrifiadur chwaraewr a chwaraewr dynol. Rhif Chwaraewr bydd un yn chwarae mae'r O. Fe hynny fod y chwaraewr peiriant. Maent yn cael i symud yn ail. Ac mae'r chwaraewr arall, mae ein chwaraewr dynol, yn X. Ac i wneud fy mywyd Ychydig syml, dw i'n mynd i labelu bod un negyddol chwaraewr. Felly, gallaf luosi gan un negyddol i gyfnewid rhwng un chwaraewr a'r llall. Mae pob hawl, felly gadewch i ni edrych ar hyn yr ydym yn wir yn mynd i'w wneud. Rydym yn mynd i ddiffinio ein bwrdd. Mae'n mynd i fod, yn dda, rydym yn mynd i'w alluogi i fod yn dri gan dri, neu gallwn chwarae hyd yn oed pump gan bump neu saith gan saith o tic-tac-blaen os byddech yn fel, yn seiliedig ar rai dimensiwn D. A byddwn yn cael un neu ddau swyddogaethau cynorthwy-ydd bydd hynny'n gwneud pethau fel ymgychwyn y screen-- neu ddrwg gennym, ymgychwyn ein newidynnau, clirio'r sgrin, tynnu y bwrdd ar y sgrin, un sy'n gwirio bwrdd i weld a yw mae 'na enillydd, un sy'n parses drwy'r llinell orchymyn, dim ond i roi help llaw, un sy'n darllen yn mewnbwn, ac un swyddogaeth o'r enw minimax. A dyna un byddwn yn gofalu fwyaf am. Ond gadewch i ni edrych yn gyntaf ar y prif. Beth ydym yn ei wneud? Wel, rydym yn mynd i dosrannu ein llinell gorchymyn, newydd ddarllen mewn a gweld beth bwrdd dimensiwn byddem yn hoffi cael. Byddwn yn ymgychwyn ein bwrdd. Ac yna byddwn yn rhan o un dolen gwyllt mawr, dro ar ôl tro derbyn yn symud nes bod y gêm yn Enillodd, neu does dim symudiadau ar ôl. Bob tro y byddwn yn mynd drwy hynny dolen, byddwn yn glir y sgrin. Byddwn yn tynnu y bwrdd ar y sgrin. Ac rydym yn fwriadol fath o tynnu hyn oddi wrth is-reolweithiau, fel nad oes raid i chi boeni gormod am y manylion am sut y maent yn digwydd. Byddwch yn cael y cod yn ddiweddarach heddiw. Ac os ydych chi am edrych drwy a dod o hyd allan, gallwch eu gweld i gyd. Ond byddwn yn tynnu bwrdd ar y sgrin. Ac yna byddwn yn gwirio ac yn gweld, mae gennym enillydd? A yw rhywun ennill y gêm? Os oes ganddynt, byddwn yn argraffu neges fuddugoliaeth. A byddwn yn dod i ben y gêm. Byddwn hefyd yn gwirio a weld os oes tei. Bydd yn hawdd i weld a oes 'na tei. Mae'n golygu bod yr holl leoedd yn llawn, ond ni fu enillydd eto. Gallwn ddatgan tei a yn cael ei wneud. Yna y meat-- go iawn os ei fod yn chwaraewr beiriant, byddwn yn caniatáu hynny chwaraewr peiriant i chwilio drwy ddefnyddio'r algorithm minimax, i ddod o hyd y symud gorau o fewn ei allu. Ac yna byddwn yn roi hynny yn symud i fyny. Fel arall, os yw'n chwaraewr dynol, byddwn yn darllen rhywfaint o gyfraniad gan y dyn. Ac yna boed yn y dynol chwaraewr neu y chwaraewr peiriant, byddwn yn gwneud cwpl bach darnau o wirio gwall, gwnewch yn siŵr ei fod yn aros o fewn ffiniau o ddimensiynau gwirioneddol y bwrdd bod gennym, gwnewch yn siŵr bod y lle yn wag, nad oes neb yn rhoi darn yn yno eisoes. Ac yna byddwn dim ond rhoi darn ar y bwrdd, newid y chwaraewr i'r haen nesaf, a cynyddiad faint o symudiadau wedi digwydd. Dyna'r prif ddolen ar gyfer ein gêm tic tac--blaen. Minimax, yna, yn union yr algorithm yr ydym o'r blaen. Yr unig addasiad sydd rydym wedi gwneud er mwyn i ni yn gallu chwarae yn uwch byrddau dimensiwn yn rydym wedi Cedwir y paramedr ychwanegol o'r enw ddyfnder. A dyfnder yn unig yn dweud, os ydw i'n chwilio am i lawr drwy'r coed ac rwy'n cael hyd yn hyn i lawr y tu hwnt peth dyfnder lefel fy mod nid yn unig yn dymuno i fynd ymhellach, Rydw i'n mynd i stopio a dim ond gwerthuso'r bwrdd ar y pwynt hwnnw. 'N annhymerus' gwirio i weld os oes enillydd. Os oes enillydd, yr wyf yn eu dychwelyd. Fel arall, byddaf yn mynd drwy ddolen. A byddaf yn dweud, ar gyfer pob un y lleoliadau posibl hynny gallwn o bosibl cymryd fel fy symud, byddaf adeiladu bwrdd damcaniaethol sy'n yn cynnwys fy symud ar y bwrdd hwnnw, ac yna recursively galwadau minimax. Os yw'n fy symud, yr wyf yn cael dod o hyd i'r un sy'n cael y sgôr mwyaf. Os yw'n symud fy gwrthwynebydd, rydym yn dod o hyd i yr un sy'n cael y sgôr isaf. Ac mae popeth arall yn jyst cadw cofnodion. Mae pob hawl, felly gadewch i ni weld redeg hwn. Mewn gwirionedd, efallai y gallwn cael un neu ddau o wirfoddolwyr i ddod i fyny a chwarae tic-tac-blaen. [Anghlywadwy] un, ac un mwy, dau, iawn yno. Dewch ar i fyny. Felly gadewch i ni fynd yn ei flaen ac ailgychwyn hyn yn gyfan gwbl. Felly, hi. GYNULLEIDFA: Hi. SIARADWR: Beth yw eich enw? GYNULLEIDFA: Gorav. SIARADWR: Gorav. GYNULLEIDFA: Rwy'n Layla. SIARADWR: A Layla, a Layla, mae'n ddrwg gennyf. Dewch ar i fyny. Gorav, rydym yn mynd i gael i chi fynd yn gyntaf. Ac yr wyf i'n mynd i ofyn i chi fod yn peidio chwaraewr tic tac--blaen ofnadwy dda. Iawn, felly mae'r holl bwysau oddi arnoch chi. Gadewch i ni weld, fodd bynnag, bod ein peiriant Gall chwaraewr mewn gwirionedd yn gwneud rhywbeth smart. Felly mynd yn ei flaen. Rydych yn mynd i deipio lle cydlynu hoffech chi roi eich X i mewn. A0, OK, a'r peiriant wedi mynd ar unwaith ac yn rhoi ei farc yn A1. Rhowch y O ar y bwrdd. Mae pob hawl, yn awr yn mynd yn ei flaen. Ble fyddech chi'n hoffi mynd? C2. Mae ein peiriant chwaraewr wedi cymryd y sgwâr canol, blocio chi. Felly yr oedd hynny'n dda, beth smart iddo wneud. Rydych chi wedi blocio iddo. Mae hynny'n ardderchog. Mae'n cymryd y gornel yno. Ac mae'n mynd i eich gorfodi i cymryd y un lle olaf, B0. Ac yn y gêm yn dod i ben yn un cyfartal. Ond mae'n chwarae rhesymol gêm yn eich erbyn, dde? Mae pob hawl, diolch yn fawr iawn, Gorav. [Cymeradwyaeth] Mae pob hawl, Layla, rydym yn mynd i fyny y gêm ar chi yma. GYNULLEIDFA: O, gwych. SIARADWR: Rydym yn mynd i roi ydych pedwar gan bedwar tic tac--blaen. Yn awr, mewn pedwar gan bedwar, mae'n rhaid i chi ennill gyda phedwar yn olynol, nid oedd tri yn olynol. Ac mae hyn i gyd eich un chi. Felly cymerodd Layla D1. Rydym yn awr yn mynd i ddilyn ein chwaraewr cyfrifiadur yma. Mae tri gan dri tic tac-blaen-yw'r math o beth sy'n hawdd i bob un ohonom. Ond mae'n dal i fod yn braf gweld y chwaraewr cyfrifiadur yn gwneud symudiadau smart. Mae pedwar gan bedwar yn cael i fod ychydig yn fwy anodd. Gwneud 'n glws. Mae pob hawl, felly Layla yn gorffen i ffwrdd. O, a dylem fod wedi dod i ben yno. Ond gadewch i ni wneud un yn fwy i fyny yma. Felly Layla, diolch i chi. Gwneud 'n glws. [Cymeradwyaeth] Felly mae ein chwaraewr tic tac-blaen-mynd trwy ac yn canfod lleoliadau, datrys eu defnyddio minimax hwn. Ac yr wyf wedi cael lleoliad ddyfnder ar hynny fel ei fod yn Ni fyddai rhedeg yn rhy gyflym, sydd yn ôl pob tebyg pam Layla yn gallu mynd yn ei flaen 'n glws fel y gwnaeth hi, ac yn gwneud yn dda iawn. Ond mae systemau hyn mai dim ond mynd drwy a 'n ysgrublaidd dreisio mynd yn ddyfnach, ac yn ddyfnach, ac yn ddyfnach, a chadw dod o hyd i'r ateb sydd eu hangen arnynt, mathau hynny o systemau yn eithaf llwyddiannus yn hyn, yn dda, gemau bwrdd safonol. Ac yn wir, os edrychwn ar tri gan dri gêm tic tac-blaen-, mae hyn yn y bôn yn broblem ei datrys. Ac mae hyn yn diagram bendigedig o Randall Munroe yn XKCD, yn dangos pa symud dylech cymryd, o ystyried symud eich gwrthwynebydd. Mae hyn yn rhywbeth y gallem hawdd pennu o flaen amser. Ond beth sy'n digwydd wrth i ni fynd i fwy gemau cymhleth, gemau mwy cymhleth, lle mae byrddau mwy, mwy posibiliadau, strategaeth ddyfnach? Mae'n ymddangos bod hyn 'n ysgrublaidd dreisio chwilio o hyd yn gwneud yn weddol dda, ac eithrio pan fyddwch yn cyrraedd y pwynt lle y goeden mor fawr na allwch cynrychioli y cyfan. Pan na allwch gyfrifo y goeden gyfan, pan nad ydych yn gallu mynd ymlaen ac yn gwthio eich hun at y pwynt lle rydych chi wedi gotten y goeden gyfan er cof, neu a allwch chi ei gael mewn cof ac bydd yn jyst mynd â chi ffordd gormod o amser i chwilio drwy iddo, rhaid i chi wneud rhywbeth yn fwy craff. Er mwyn gwneud hynny, rydych yn rhaid i ni wneud dau beth. Yn gyntaf, mae'n rhaid i chi ddod o hyd i ffordd o gyfyngu ar eich ddyfnder. Wel, mae hynny'n iawn. Gallwn ddod o hyd i 'n glws, mymryn lleiaf a dweud, gallwch fynd mor ddwfn. Ond pan fyddwch yn gwneud hynny, mae hynny'n golygu eich rhaid i'r byrddau rhannol anghyflawn. Ac yn rhaid i chi ddewis, ydw i'n hoffi y bwrdd rhannol anghyflawn, neu y bwrdd rhannol anghyflawn? Ac ar ein pedwar gan pedair gêm tic tac-blaen-, ein chwaraewr cyfrifiadurol got i lawr i'r gwaelod a mae'n dweud, Mae gen i ddau fwrdd gwahanol. Nid un yn ennill. Nid un yn golled. Nid un yn tei. Sut ydw i'n dewis rhyngddynt? Ac nid oedd ganddynt ffordd smart o wneud hynny. Rydym yn gweld y math hwn o gwerthusiad yn digwydd drwy'r amser wrth i ni fynd i mewn i gemau mwy cymhleth. Gwyddbwyll yn enghraifft wych. Yn gwyddbwyll, yr ydym, yn gyntaf oll, bwrdd mwy. Mae gennym lawer mwy o ddarnau. A safle'r darnau hyn a'r ffordd y darnau hyn yn symud yn hanfodol bwysig. Felly, os wyf am ei ddefnyddio minimax, Mae angen i mi fod yn gallu nodi a dweud, bwrdd hwn, lle nid oes neb wedi ennill neu golli eto, rywsut yn well na hyn eraill bwrdd, lle nad oes neb wedi ennill neu golli. I wneud hynny, efallai y byddwn yn ei wneud pethau fel wyf yn gallai jyst yn cyfrif faint o ddarnau sydd gen i a faint o ddarnau sydd gennych chi? Neu efallai y byddaf yn rhoi gwahanol darnau gwahanol bwyntiau. Mae fy frenhines yn werth 20 pwynt. Mae eich gwystl yn werth un pwynt. Pwy sydd cyfanswm fwy o bwyntiau? Neu efallai y byddwn yn ystyried pethau yn hoffi, sydd wedi cael y sefyllfa bwrdd yn well? Ei dro pwy yw hi nesaf, unrhyw beth y gallaf peidiwch gwerthuso yn fwy cywir pa rai o'r posibiliadau hyn yn well heb ystyried yn drwyadl pob symudiad a allai dod ar ôl hynny. Nawr i wneud y gwaith hwnnw, un o'r pethau sy'n mynd i fod yn bwysig iawn am beidio â ni yn unig yw symud yn syth i lawr i ddyfnder penodol terfyn, ond yn gallu dweud, un o'r syniadau hyn yr wyf yn cael mor ddrwg ei fod yn Nid yw werth ystyried pob un o'r ffyrdd posibl y gall pethau fynd o ddrwg i waeth. I wneud hynny, byddwn yn ychwanegu i mewn minimax egwyddor a elwir alph-beta. Ac alffa-beta yn dweud, os oes gennych chi syniad drwg, peidiwch â gwastraffu eich amser yn ceisio cael gwybod pa mor ddrwg yn union ydyw. Felly, dyma beth rydym yn mynd i'w wneud. Rydym yn mynd i gymryd yr un fath egwyddorion a oedd gennym o'r blaen, yr un math minimax o chwilio, dim ond rydym yn mynd cadw golwg, nid yn unig o'r gwerthoedd gwirioneddol sydd gennym, ond yr ydym chi helpu cadw golwg ar y gorau posibl gwerth y gallwn i ei gael, a'r gwaethaf posibl canlyniad y gallwn i gael. Ac unrhyw bryd y gwaethaf posibl peth yn edrych yn debygol, 'N annhymerus' rhoi'r gorau y rhan honno o'r goeden. Ac ni fydd hyd yn oed yn trafferthu i mi edrych arno anymore. Mae pob hawl, felly dychmygwch ein bod yn dechrau gyda hyn un goeden gêm union. Ac yn awr rydym yn mynd i fynd i lawr unwaith eto, yr holl ffordd i lawr at y gornel chwith isaf. Ac yn y gwaelod ar y chwith cornel, rydym yn edrych ac rydym yn gwerthuso bwrdd hwn. Efallai ei fod yn bedwar gan bedwar tic tac--blaen bwrdd, neu efallai ei fod yn fwrdd gwyddbwyll. Ond rydym yn edrych arno, ac rydym yn gwerthuso iddo, ac rydym yn cael gwerth o wyth. Ar yr adeg honno, rydym yn gwybod bod rydym yn mynd i gael o leiaf wyth pwynt o hyn benderfyniad gwaelod. Does dim ots beth y llall dau ohonynt, bod saith a bod dau. Gallent fod yn unrhyw werthoedd eu bod eisiau bod. Rydym yn mynd i gael o leiaf wyth pwynt. Mae pob hawl, ond gallem mynd yn ei flaen a gwirio. Efallai un ohonynt yn well nag wyth. Rydym yn edrych ar y saith. A yw bod yn well nag wyth? Na, nid yw hynny'n newid ein barn o gwbl. Rydym yn edrych ar y ddau. A yw bod yn well nag wyth? Na, nid yw hynny'n newid ein barn o gwbl. Felly nawr rydym yn gwybod ein bod wedi blino'n lân pob un o'r posibiliadau yno. Nid ydym yn mynd i gael unrhyw beth yn well nag wyth. Rydym yn mynd i gael yn union wyth. Ac felly yr ydym yn newid y nôd a dyweder, sydd bellach yn sicrwydd. Rydym yn mynd i fyny un lefel yn uwch hynny. Ac yn awr rydym yn gwybod rhywbeth am y lefel honno lleihau. Rydym yn gwybod nad ydym erioed yn mynd i gael mwy nag wyth o bwyntiau os ydym yn mynd i lawr cyfeiriad hwnnw. Oherwydd hyd yn oed os bydd y rhai dwy gangen arall yn troi allan i fod yn wych ac yn werth miloedd o pwynt yr un, Bydd ein gwrthwynebydd yn rhoi i ni y leiaf, ac yn rhoi i ni yr wyth. Mae pob hawl, yn dda, gadewch i ni weld. Byddwn yn dal i fynd i lawr y llwybr hwnnw. Rydym yn mynd i lawr at y canol ar y chwith. Rydym yn edrych i lawr ac rydym yn gweld mae 'na naw. Rydym yn gwybod ein bod yn mynd i gael o leiaf naw pwynt drwy fynd i lawr ffordd honno canol. Ac yn y fan hon, gallwn jyst oedi. Ac gallwn ddweud, edrych, yr wyf yn yn gwybod yn lefel uchod, Rydw i'n mynd i gael dim mwy nag wyth pwyntiau drwy fynd i lawr i'r cyfeiriad hwn. Ond os wyf yn mynd i lawr y canol llwybr yn hytrach na'r llwybr ar y chwith, Byddwn yn cael o leiaf naw pwynt. Byth Mae fy gwrthwynebydd yn mynd i gadewch i mi fynd i lawr y llwybr hwnnw canol. Maent yn cael dewis. Ac maen nhw'n mynd i ddewis y llwybr i'r chwith i gyfeiriad yr wyth, yn hytrach nag i lawr y canol tuag at beth sydd o leiaf naw pwynt. Felly, ar y pwynt hwnnw, byddaf yn stopio. A byddaf yn dweud, eich bod yn gwybod beth? Nid oes rhaid i mi chwilio unrhyw yn fwy i lawr yn y cyfeiriad hwnnw. Oherwydd nid wyf erioed i'n mynd i gyrraedd yno. Gallaf neidio dros y un, a gallaf neidio dros y chwech, oherwydd nad ydynt erioed yn mynd i ddigwydd. Felly, byddaf yn mynd i lawr ac byddaf ystyried y posibilrwydd nesaf. Yr wyf yn mynd i lawr yno ac yr wyf yn dweud, yr wyf yn gweld dau. Yr wyf yn gwybod os ydw i'n cael i fan hyn, rwy'n mynd i gael o leiaf dau. IAWN. Yr wyf yn cadw i fynd. Rwy'n gweld pedwar. Rwy'n gwybod fy mod i'n mynd i gael o leiaf bedwar. Mae dal i fod llawer rhwng pedair ac wyth, er. Felly, yr wyf yn dal i fynd. Yr wyf yn edrych i lawr ac yr wyf yn gweld mae un. Mae pob hawl, yr wyf yn gwybod os Yr wyf yn mynd i lawr y llwybr hwn, Rydw i'n mynd i fod yn gallu dewis y pedwar. Beth sy'n fy gwrthwynebydd yn mynd i'w wneud? Rhwng rywbeth sy'n rhoi i mi wyth, rhywbeth sy'n rhoi i mi bedwar, a rhywbeth y rhoi i mi o leiaf naw, yn dda, mae'n mynd i roi i mi y pedwar. Ac yr wyf yn gwybod yn awr yn y iawn top, dw i'n mynd i allu cael o leiaf pedwar pwynt allan o gêm hon. Mae'r holl syniad o alffa-beta yw i dorri i ffwrdd y rhannau y goeden felly nad wyf yn edrych arnynt anymore. Ond mae'n dal i edrych fel fy mod i wedi bod gan edrych ar lawer o'r goeden. Gadewch i ni gadw i fynd i lawr. Byddwn yn mynd i lawr yr un nesaf yn awr. I lawr ar y gwaelod, yr wyf yn dod o hyd i un. Rwy'n gwybod fy mod i'n mynd i gael o leiaf un. Yr wyf yn cadw yn edrych. Yr wyf yn dod o hyd i dri. Rwy'n gwybod fy mod i'n mynd i gael o leiaf tri. Yr wyf yn cadw i fynd. Yr wyf yn dod o hyd i bump. Rwy'n gwybod fy mod i'n mynd i gael pump os byddaf yn cael i lawr yn y llwybr hwnnw. Ac yr wyf hefyd yn gwybod wedyn bod fy gwrthwynebydd, os wyf yn dewis y canol y tri dewis mawr, mae'n mynd i roi i mi rhywbeth sy'n pump neu lai. IAWN. Gallaf gadw mynd yno. Gallaf edrych i lawr ac yr wyf yn gallu dweud, beth ydw i'n mynd i fynd os wyf yn mynd i lawr y llwybr canol? Rydw i'n mynd i gael, wel, tair yno. Rydw i'n mynd i gael rhywbeth dyna o leiaf dair. Mae yna bethau rhwng dal tair a phum, felly yr wyf yn cadw yn edrych. O, mae naw, 'n annhymerus' yn bendant cymryd hynny dros gyfnod o dair. Rydw i'n mynd i gael o leiaf naw os byddaf yn mynd i lawr y llwybr hwnnw canol. Nawr mae fy gwrthwynebydd yn stopio ac yn dweud, edrych, does dim pwynt anymore. Gwn fod fy gwrthwynebydd lleihau, ei fod yn mynd i roi y peth dyna fi llai na neu'n hafal i bump, yn hytrach na'r peth sy'n fwy na neu'n hafal i naw. Yr wyf yn stopio. Dydw i ddim yn edrych mwy ar hynny. Yr wyf yn cadw i fynd. Yr wyf yn edrych i lawr ar yr un yma. I lawr i waelod, yr wyf yn dod o hyd i chwech. Rwy'n gwybod fy mod i'n mynd i gael o leiaf chwech. A beth allaf ei wneud? Gallaf roi'r gorau iddi. Oherwydd mae dewis rhwng rhywbeth sy'n o leiaf chwe a rhywbeth sy'n llai na phump, mae'n mynd i roi y peth i mi mae hynny'n llai na phump. Ac yn awr yr wyf yn gwybod fy mod i'n mynd i fynd yn union y dewis hwnnw. Rydw i'n mynd i gael y pum dewis. Yr wyf yn mynd yn ôl i fyny i ben. Pa ydw i'n mynd i ddewis rhwng rhywbeth mae hynny'n fwy na neu'n hafal i bedwar, neu rhywbeth sy'n hafal i bum? Rydw i'n mynd i gymryd rhywbeth dyna o leiaf bump. Yr wyf yn mynd i lawr y llwybr diwethaf, mae pob y ffordd i lawr i'r gwaelod. Mae 'na un. OK, o leiaf yr wyf i'n mynd i gael un pwynt. Yr wyf yn cadw i fynd. Dau, oh, sy'n well nag un. Rydw i'n mynd i gael o leiaf dau. Yr wyf yn dod o hyd i dri. Rwy'n gwybod fy mod i'n mynd i gael tri. A'r pwynt ychwanegol at hynny, fy gwrthwynebydd yn mynd i roi rhywbeth dyna fi llai na neu'n hafal i dri. Ac yn awr y gallaf stopio. Oherwydd yn y dewis rhwng fy mod gallu cael pump ac mae fy gwrthwynebydd rhoi rhywbeth llai na thri mi, Rwyf bob amser i'n mynd i gymryd y pump. Felly, nid wyf yn gwerthuso hynny rhan waelod y goeden o gwbl. Yn awr, gall hyn ymddangos mân. Ond pan darnau bach o rifyddeg, fwy na a llai na, Gall torri ymaith rhannau cyfan o coeden yn tyfu gynt a chynt hyn, sy'n arwain at enfawr faint o gynilion, cynilion sy'n ddigon mawr i mi Gall ddechrau chwarae yn gystadleuol mewn gemau mwy cymhleth. Mae pob hawl, os edrychwn ar faint a chymhlethdod gemau gwahanol, tic tac--blaen oedd ein henghraifft hawdd. Mae gennym fwrdd bychan, tri gan dri. Rydym yn cael, ar y mwyaf, cyfartaledd o tua phedair dewisiadau gwahanol wrth i ni fynd drwy'r gêm. Mae gennym rhywle tua 10 i'r pumed ddail gwahanol posibl. Ac adeiladu tic tac--blaen chwaraewr, yn dda, rydym yn unig yn gwneud hynny. Mae'n hawdd. Os ydym yn mynd i fyny at rywbeth mwy cymhleth, fel Connect Four. Ydych chi'n cofio y gêm hon lle byddwch yn gollwng y tocynnau bach i mewn? Mae'n chwech o saith bwrdd, Nid yw bod llawer mwy, yn dal i Mae tua'r un canghennog ffactor fel tic-tac-blaen. Mae gen i tua bedwar dewis lle gallaf roi pethau mewn. Ond nawr, mae gen i lawer mwy o yn arwain, 10 i 21 pŵer. Mae hynny'n rhywbeth sy'n hawdd digon ein bod yn datrys yn iawn i ffwrdd. Gwirwyr, yn fwy complex-- chi got an wyth wyth bwrdd. Rydych yn unig ar hanner y nhw ar unrhyw adeg, er. Rydych chi wedi got a canghennog ffactor sy'n ymwneud â 2.8. Wel, mae gennym gwpl yn symud y gallwch eu cymryd. Rydych chi wedi cael tua 10 i 31 y dail, mannau mwy o faint, a mwy, ac yn fwy. Gan fod rhaid i mi chwilio drwy lleoedd fwy ac yn fwy rheini, dyna pryd pethau fel alffa-beta a y gallu i dorri i ffwrdd canghennau cyfan yn dod yn hanfodol. Yn awr, gwirwyr yn ddigon rhwydd yn 1992. Mae rhaglen gyfrifiadurol o'r enw Chinook guro'r gwirwyr byd hyrwyddwr, Marion Tinsley. Ac ers hynny, nid oes meistr chwaraewr dynol wedi gallu curo'r gorau systemau cyfrifiadurol. Os edrychwn ar rywbeth fel gwyddbwyll, yn awr eto, mae gennym wyth erbyn wyth bwrdd. Ond mae gennym lawer mwy cymhleth darnau, symudiadau llawer mwy cymhleth. Mae gennym ffactor ganghennog o tua 35, 35 symudiadau posibl ar gyfartaledd y gallaf gymryd, a cyflwr gofod, mae nifer o ddail sy'n tyfu i 10 i rym 123, niferoedd enfawr o bosibiliadau. Hyd yn oed yn dal, proseswyr modern yn gallu gwneud hyn yn llwyddiannus. Yn 1995 ac yna yn 1997, cyfrifiadur rhaglen o'r enw Deep Blue a adeiladwyd gan IBM a oedd yn rhedeg ar uwchgyfrifiadur mawr guro'r pencampwr y byd ar hyn o bryd, Garry Kasparov. Roedd hwn yn drobwynt. Heddiw, fodd bynnag, bod yr un prosesu pŵer yn eistedd ar fy MacBook. Cyflymder prosesu yn cadw mynd yn gynt ac yn gynt. Gallwn werthuso'n fwy a mwy byrddau yn gyflymach ac yn gyflymach. Ond yn bwysicach, mae gennym well swyddogaethau gwerthuso a gwell tocio ddulliau. Felly gallwn chwilio'r mwy o le complexly. Mae mwyaf y bwrdd gemau y gallwn feddwl, rhywbeth fel Go dyna got a 19 erbyn 19 bwrdd, yn awr yn sydyn, rydym yn heibio'r pwynt lle y gall systemau cyfrifiadurol ennill. Does dim cyfrifiannol system i maes 'na sy'n gallu curo a Go chwaraewr proffesiynol. Mae'r systemau heddiw rheng gorau iddo am y math o lefel amatur da. Felly mae yna dal i fod gryn dipyn allan mae na allwch gyrraedd eto. Mae pob hawl, mae'r rhain gemau bwrdd traddodiadol, mathau hyn o systemau lle'r ydym adeiladu minimax hwn, boed 'i' got alffa-beta neu beidio, algorithmau hyn yn gweithio oherwydd bod cyfyngiadau penodol. Mae gennym wybodaeth perffaith am y byd. Rydym yn gwybod ble yr holl ddarnau yn cael eu. Mae'r byd yn statig. Does neb yn cael i symud y darnau o gwmpas tra fy mod yn eistedd yno yn meddwl, gan gymryd fy nhro. Mae gofod weithredu sy'n arwahanol. Gallaf roi fy gwystlo yma, neu gallaf roi fy gwystl yma. Dydw i ddim yn cael rhoi fy gwystlo ar y llinell rhwng y ddau sgwâr. Ac yn olaf, mae'r camau gweithredu yn benderfynedig. Yr wyf yn gwybod os wyf yn dweud, Rook i farchog tri, fy Rook yn mynd i roi diwedd ar i fyny yn y marchog tri, ar yr amod ei fod yn symud dilys. Does dim ansicrwydd am hynny. Yn awr, gan fy mod yn mynd i fwy gwahanol fathau o gemau, mae'n rhaid i ni dorri tybiaethau hynny. Beth os byddaf yn mynd i rywbeth fel gemau fideo clasurol? Dyma ddetholiad o fideo gemau o'r Atari 2600. Beth sydd gen i fyny yno? Mae gen i Frogger, Gofod Oresgynwyr, Perygl, a Pac-Man. Pa fath o amgylcheddau sydd gennyf yma nawr? Pa un o'r tybiaethau hyn oes rhaid i mi dorri? Wel, mae'n dibynnu ar y gêm. Gallwn i chwarae gwyddbwyll ar y 2600, a byddai'n union fel yr oedd o'r blaen. Ar gyfer y rhan fwyaf o'r systemau hyn, mae ' gwybodaeth gyflawn am y byd. Does gwbl camau gweithredu benderfynedig. Ond fel arfer, yn y byd dim statig yn hirach. Hynny yw, er fy mod i'n eistedd yno aros, rhywbeth yn symud. Mae'r ysbrydion yn dod ar fy ôl. Mae'r sgorpion yn dilyn fi oddi tano. Mae'r goresgynwyr gofod yn dod yn nes ac yn nes. Pa mor dda y gallwn ei wneud yn erbyn y rhain? Ychydig flynyddoedd yn ôl, Google Roedd prosiect o'r enw DeepMind, lle maent wedi'u hyfforddi cyfrifiadur rhaglen i chwarae Atari 2600 gemau. Ac os ydych yn credu nad yw hyn yn ddifrifol busnes, canlyniadau eu hastudiaeth Cyhoeddwyd yn Nature, felly dim ond am cystal gyhoeddiad fel y gallwch o bosibl ei gael. A dyma pa mor dda y maent yn perfformio. Mae ganddynt algorithm yn eistedd ac yn gwylio dim ond y mewnbynnau sgrin. Mae'n cael unrhyw gyfarwyddiadau o gwbl am y rheolau'r gêm. Ac yr oedd i fod i chyfrif i maes, ei sgôr yn seiliedig, pa mor dda y mae'n ei wneud. Roedd hwn yn system a ddefnyddir rhywbeth Gelwir dysgu atgyfnerthu. Hynny yw, yr oedd yn edrych ar ei sgôr. Ac os yw'n cael sgôr da, meddai, Ddylwn i gofio pethau hynny. A ddylwn i wneud hynny eto. Ac os yw'n cael sgôr gwael, mae'n dweud, Ni ddylwn i wneud y pethau hynny eto. Mae hyn yn y perfformiad o systemau wedi'u hyfforddi rhai cael chwarae am ychydig oriau ar bob gêm, cymharu yn erbyn gamers proffesiynol. Felly, ar gyfer pob un o'r gemau sy'n cael eu i ochr chwith y llinell hon, y rhaglen gyfrifiadurol hunan-hyfforddedig perfformio'n well na'r gamers proffesiynol. Ac ar gyfer popeth i'r dde, mae'r gamers proffesiynol yn dal y gorau. Ar gyfer rhywbeth na wyddai dim am y rheolau, y yn gwybod dim am strwythur y gemau, mae hyn yw perfformiad trawiadol. A dyma beth rydym yn gallu ei wneud heddiw. OK, yr ydych yn dweud, ond os ydym meddwl am AI mewn gemau, Fel arfer, rydym yn meddwl am y pethau y gallwn mewn gwirionedd eistedd i lawr ac yn chwarae yn erbyn. Os byddaf yn eistedd i lawr ac yr wyf yn chwarae Starcraft, neu yr wyf yn chwarae rhad ac am ddim Hidlo'r, mae'r gwrthwynebydd cyfrifiadur yn y person sy'n rheoli'r Zerg, neu reoli y gwareiddiad arall. Sut mae chwaraewyr hynny mewn gwirionedd yn dod o hyd i'w symud? Wel, gemau hyn yn cael eu strwythuro yr un modd ag y mae ein gemau bwrdd, gemau hyn yr ydym chi helpu cyd ffoniwch pedair gêm X, archwilio, expand-- anghofio y rhai. Beth ydyn nhw? Explore, ehangu, a diffodd, Yr wyf yn meddwl yw'r un olaf. Ond maen nhw'n bôn archwilio a gorchfygu gemau. Yn nodweddiadol, mae'r gwrthwynebydd cyfrifiadur bu gwybodaeth gyfyngedig. Nid ydynt yn gwybod yn union beth sydd mynd ymlaen y tu ôl i'r niwl y rhyfel. Nid ydynt yn cael i weld beth gennych yn eich rhestr. Mae amgylchedd sy'n ddeinamig. Mae popeth yn newid drwy'r amser. Nid ydych yn cael i eistedd a aros i gymryd eich symud. Ond yn y rhan fwyaf o bethau yn dal i fod ar wahân. Mae'n rhaid i mi roi fy ninas yma. Neu rhaid i mi roi fy ninas yma. Ac mae popeth yn benderfynedig. Pan fyddaf yn dweud, yn symud fy uned yma, fy uned yn symud yma, oni bai bod rhwystr yn sydyn yn dod i chwarae. Nawr, nid dyna'r cyfan cyfrifiadur gemau sydd allan yno heddiw. Os byddaf yn mynd ac yr wyf yn chwarae math person cyntaf gêm, rhywbeth fel Lleidr neu Fallout neu Skyrim, neu Halo, yn awr Mae gen i gwrthwynebwyr cyfrifiadurol sydd allan yno sydd wedi sefyllfa wahanol iawn. Mae ganddynt, unwaith eto, gwybodaeth gyfyngedig. Gallant ond weld maes penodol o farn. Mae'r amgylchedd yn dal i fod yn ddeinamig. Mae pethau'n newid drwy'r amser. Ond yn awr mae gen i lawer mwy gofod gweithredu parhaus. Gallaf fod yn jyst peeking mewn ychydig bach allan o'r drws. Ac mae rhai gemau, fy gweithredoedd yn stocastig. Rwy'n cael i geisio neidio dros y wal, ond mae gen i siawns o fethu. Mae'r mathau hyn o gemau yn dod yn nes ac yn nes at y mathau o reolwyr ein bod yn adeiladu mewn roboteg. Yn roboteg, mae'n rhaid i ni gymryd yn ganiataol bod gennym wybodaeth gyfyngedig. Mae gennym synwyryddion sy'n ddweud wrthym am y byd. Mae gennym-newid bob amser, amgylchedd dynamig. Mae gennym byd lle y gofod yn barhaus, yn hytrach nag ar wahân. Ac mae ein gweithredoedd, pan geisiwn nhw, yn cael cyfle o fethu. Ac yn wir, gêm fodern rheolwyr ar gyfer eich gwrthwynebydd Halo, neu ar gyfer NPCs rhai yn Skyrim, yn y bôn rhedeg saernïaeth roboteg bach. Maent yn synhwyro y byd. Maent yn adeiladu model o'r byd. Maent gyfrifo yn seiliedig ar set o nodau yr hoffent ei gyflawni. Maent yn cynllunio camau gweithredu sy'n seiliedig ar ar yr hyn y maent yn ei wybod. A'r rhai yn union yr un mathau o systemau yr ydym yn adeiladu mewn roboteg. Felly pensaernïaeth hyn, i yn dod yn ôl yma at ei gilydd, yn aml yn hollol yr un fath. Felly, gadewch i ni weld os gallwn weld bod. Gadewch i ni fynd yn ôl at ein tic tac--blaen esiampl. Ac yr wyf i'n mynd i ofyn i un neu ddau o fy ôl-docs i ddod i fyny ac yn fy helpu. Felly Chen Ming, ac Alessandro, ac Olivier, pe byddech yn guys yn dod i fyny. Ac yr wyf i'n mynd i angen un neu ddau o wirfoddolwyr OK, gwelais hawl llaw i fyny yno yn y canol. Gadewch i mi gymryd un yn fwy, rhywun ymhellach yn y cefn efallai. Mae pob hawl, dros yno. Dewch ar i fyny. Iawn. Felly gadewch i ni gymryd y clawr i lawr. Ac os ydych yn guys yn dod i'r dde yn ôl o gwmpas fan hyn i mi, ffantastig. Felly, mae hyn yn robot o'r enw Baxter. A Baxter yn robot mae hynny'n llwyfan masnachol, a gynlluniwyd gan gwmni o'r enw Rethink. Ac mae robot hwn wedi ei gynllunio ar gyfer gweithgynhyrchu ar raddfa fach. Ond heddiw rydym ni'n mynd i ei ddefnyddio i chwarae tic-tac-blaen. Yn awr, robot hwn hefyd yn rhywbeth mae hynny'n weddol unigryw. Oherwydd os wyf yn sefyll yn unrhyw le agos at awtomeiddio ffatri safonol system, byddwn i yn iawn bedd perygl o gael eu hanafu. Baxter, fodd bynnag, yn cael ei gynllunio i fod yn gymharol ddiogel i ryngweithio â nhw. Ac felly y gallaf wthio ar y robot hwn. A gallwch weld ei fod yn ychydig yn bit hyblyg wrth iddo symud o gwmpas. A gallaf ail-leoli ei lle byddwn yn hoffi i fynd. Nawr yn system robotig arferol, byddai gennym set o gymalau yma byddai hynny'n uniongyrchol gan ymateb i orchmynion sefyllfa. Ac na fyddent o reidrwydd yn gofalu os oeddent yn symud drwy'r awyr agored, neu os ydynt yn symud drwy fy cawell asennau. IAWN. Ac fel arfer, os oeddech yn yma gyda system diwydiannol, byddech yn mynd yn agos iddo. Byddai felyn tâp diogelwch o amgylch iddo. Mae'r system hon yn cael dylunio ychydig yn wahanol i fod yn fwy cyfeillgar ac yn haws i bobl ryngweithio â, yn hynny ym mhob cyd, mae 'na gwanwyn. Ac yn hytrach na rheoli union safle, rydym yn rheoli rhywfaint o torque, swm penodol o rym, y byddem yn hoffi i fod ar y gwanwyn. Mae pob hawl, felly gadewch i mi cymryd ein gwirfoddolwyr yma. Hi, beth yw eich enw? GYNULLEIDFA: Louis. SIARADWR: Louis. Nice i'ch gweld. A? GYNULLEIDFA: David. SIARADWR: David. Neis i gwrdd â chi. Os hoffech chi guys yn aros dde yma am eiliad, Rydw i'n mynd i roi i chi cyfle i wneud hyn. Felly robot hwn, os byddwch yn dod i fyny ac os ydych yn gwthio yn ysgafn arno, eich bod yn mynd i weld bod mae'n symud ychydig. Ac os ydych yn cydio yn iawn yma ar yr arddwrn yn unig uchod os botymau hynny, mae'n edrych yn debyg y dylech fanteisio ar y botymau, ond yn cydio yn iawn uwch ei ben yn lle hynny, wnewch chi helpu yn gallu trin ysgafn iawn drwy gofod. Louis, byddwch am roi cynnig arni? Felly rhowch ei fod dim ond ychydig gwthio i ddechrau. Ac yna os byddwch yn rhoi eich bysedd iawn yno a dal ymlaen iddo, gan y bydd yn symud i chi bryd hynny. Mae pob hawl, ydych am roi cynnig arni? Dewch ar i fyny. Felly rhowch 'i jyst yn ysgafn gwthio yno i ddechrau. Gallwch deimlo sut brofiad. Ac yna os byddwch yn cydio yn iawn yno, byddwch yn gallu i symud o gwmpas. IAWN. Felly fel arfer, y math hwn o robot byddai ei ddefnyddio ar gyfer gweithgynhyrchu ar raddfa fach. Ac yr wyf i'n mynd i symud braich hyn yn unig i lawr allan o'r ffordd ychydig yma. Ond heddiw, rydyn ni'n mynd i ddefnyddio'r un system chwarae tic-tac-blaen yn seiliedig ar minimax a adeiladwyd yn gynharach. IAWN? Felly, rydych guys yn bob un mynd i chwarae gêm. Louis, rydych yn mynd i fod yn gyntaf. Gadewch i mi ddal i fyny yma am eiliad. Rydw i'n mynd i gael i chi sefyll yn iawn yma, dim ond er mwyn i bawb weld chi. A ydych yn guys a sefydlwyd yma? ROBOT: Croeso. Gadewch i ni chwarae tic-tac-blaen. Peidiwch â gafael eich tocyn cyn Yr wyf yn dweud ei fod yn eich tro. I'n dechrau y gêm. Mae'n fy tro. SIARADWR: Yn awr, os ydych gallai gymryd un o eich darnau a mynd yn ei flaen a'i osod. ROBOT: Eich tro. [Chwerthin] Mae'n fy tro. [Chwerthin] [Chwerthin] Mae'n eich tro. SIARADWR: Y hil ddynol yn cyfrif ar chi yma, Louis. ROBOT: Mae'n fy tro. SIARADWR: Felly Baxter blocio yn llwyddiannus yma. ROBOT: Eich tro. Mae'n fy tro. Mae'n eich tro. Mae'n fy tro. SIARADWR: A byddwn yn gadael i Baxter gorffen ei symudiad olaf yma. [Chwerthin] ROBOT: Mae hynny'n tei. Byddaf yn ennill y tro nesaf. [Chwerthin] SIARADWR: pob hawl, diolch yn fawr iawn, Louis. Diolch. Gallwch fynd y ffordd hon. ROBOT: Dechreuaf y gêm. SIARADWR: Felly, gadewch i mi egluro i chi un yn fwy bach bit cyn i ni gael ein rematch yma. Beth yn union sy'n digwydd? Felly, y robot yn cael top camera i fyny fan hyn. Ac mae'n edrych i lawr ar y bwrdd. Ac mae'n gweld a 'i' got a O coch neu las a X. gwyn Fel y rhai yn cael eu rhoi ar y bwrdd, dyna yn y bôn yr un mewnbwn y byddem yn darllen i mewn o ein strwythur data o'n sgrin. Mae'n rhedeg yr un fath minimax algorithm i fod yn gallu dod o hyd ble i rhoi arwydd da. Ac yna rydym yn rhoi gorchymyn ynghylch lle hoffem tocyn i gael eu lleoli. Mae'r fraich yn symud allan. Mae'n defnyddio gripper gwactod i wneud cais rhywfaint o sugno i hynny darn pren, ei godi, symud i'r dde fan a'r lle, ac yna rhyddhau'r sugno a gollwng ef. Mae pob hawl, rydym yn mynd i roi un ergyd mwy gyda chwaraewr ychydig yn fwy craff yma. Rydych yn barod? Mae pob hawl, os byddech yn sefyll i'r dde i fyny yma ac yn rhoi a-- troi allan y ffordd hon fel y gallwch weld pawb. Ac yna [Anghlywadwy]. ROBOT: Mae'n fy tro. SIARADWR: Bydd Baxter yn dechrau. Mae'n eich tro. Mae'n fy tro. Mae'n eich tro. Mae'n fy tro. [Chwerthin] SIARADWR: [WHISPERING] Just gadewch iddo fynd yn ei flaen ac yn ennill. ROBOT: Eich tro. SIARADWR: Mae hynny'n iawn. ROBOT: Mae'n fy tro. [Chwerthin] Yr wyf yn ennill. [Chwerthin] I'n dechrau y gêm. SIARADWR: pob hawl, diolch yn fawr iawn. Mae pob hawl, yr wyf yn meddwl ein bod wedi cael amser ar gyfer un chwaraewr tic tac-blaen-yn fwy rhagorol, rhywun sy'n gallu rhoi peth hyn i yn cyd-fynd, pwy a ŵyr beth maen nhw'n ei wneud. [Chwerthin] Pwy sy'n mynd i fod yn ein bencampwr yma? Mae pob hawl, eich ffrindiau wedi gwirfoddoli i chi. Mae hynny'n ddigon da i mi. Dywedwch wrthyf eich enw eto. GYNULLEIDFA: Tamir. SIARADWR: Tamir, braf gweld chi. Mae pob hawl, unwaith eto, rydyn ni'n mynd i roi i chi i'r dde i fyny yma er mwyn i bawb weld chi. Rydych yn ein cynrychiolydd yn y gêm yn awr. Baxter yn un a oh oh a. Neu ddrwg gennym, un oh ac un. Ac mae i fyny i chi yma. Bydd Baxter cael symud yn gyntaf, er. So. ROBOT: Mae'n fy tro. [Chwerthin] Mae'n eich tro. Mae'n fy tro. Mae'n eich tro. Mae'n fy tro. Mae'n eich tro. [Chwerthin] ROBOT: Mae'n fy tro. SIARADWR: Mae'n llawer anoddach pan eich bod yn sefyll i fyny yma, Folks. [Chwerthin] ROBOT: Rydych bodau dynol mor hawdd i guro. [Chwerthin a chymeradwyaeth] SIARADWR: Diolch yn fawr iawn. ROBOT: Yr wyf yn ennill. I'n dechrau y gêm. SIARADWR: pob hawl, felly diolch iawn llawer i Olivier, ac i Alessandro, ac i Chen Ming. [Cymeradwyaeth] Yr wyf am wneud un pwynt olaf. Felly Baxter ar yr union yn dod i ben yno, twyllo. A dyna oedd yn annisgwyl. Un o'r ffantastig pethau am AI yw ein bod yn gwneud gwaith yn AI fel y gallwn adeiladu yn ddiddorol iawn a deallus dyfeisiau. Ond rydym hefyd yn gwneud gwaith mewn AI oherwydd ei fod yn dweud rhywbeth wrthym am sut mae pobl yn ddeallus. Un o hoff astudiaethau o fy labordy yn edrych ar yr hyn sy'n digwydd pan peiriannau annisgwyl twyllo. Gwnaethom hyn yn wreiddiol nid gyda Baxter yn chwarae tic-tac-blaen, ond gyda robot llai o'r enw Nao, a chwaraeodd graig-bapur-siswrn. Ac weithiau ar ôl chwarae llawer a llawer o ddiflas gemau graig-bapur-siswrn, byddai'r robot taflu arwydd, yn colli, ac yna newid yn sydyn ei ystum a dweud, yr wyf yn ennill. [Chwerthin] Yn awr, weithiau byddem hefyd yn cael y robot, yn union fel rheolaeth, taflu ystum, ennill, a newid ei ystum i golli, taflu y gêm, twyllo er mwyn colli. Ac nid yw bod bron mor anorchfygol. Mae'r robot sy'n twyllo er mwyn ennill pobl ymateb iddynt fel pe ei fod yn allan i'w cael, yn ei hoffi yn mynd ati i geisio eu dinistrio. [Chwerthin] Mae'n dod asiant. Mae fel person. Mae ganddo cred a bwriad. Ac nid yw'n fwriad da. Ac mae'r robot sy'n taflu'r gêm yn unig malfunctioning. Mae'n dim ond dyfais torri. Gadewch i mi ddangos i chi ychydig o enghreifftiau o hynny o rai o'n cyfranogwyr. Felly dyma twyllo er mwyn colli. [VIDEO Playback] - [Anghlywadwy] ennill. Gadewch i ni chwarae. -Wait, Beth? - [Anghlywadwy] ennill. Gadewch i ni chwarae. [Anghlywadwy] ennill. Gadewch i ni chwarae. SIARADWR: A dyma sy'n twyllo i ennill. -Yes, Yr wyf yn ennill. Gadewch i ni chwarae. Ni -Gallwch wneud hynny. [Chwerthin] -Yes, Yr wyf yn ennill. -Gallwch Twyllo. Rydych yn twyllo yn awr. -Yes, Yr wyf yn ennill. -Hey, Byddwch yn Cheater. Ydych yn twyllo, twyllo super. [DIWEDD Playback] SIARADWR: Mae'r rhain yn wahanol adweithiau gyflym newid ein canfyddiad y ddyfais. A yw hynny'n golygu y rydym yn adeiladu yn fwriadol peiriannau sy'n twyllo oherwydd dyna peirianneg gorau y gallwn ei wneud? Nac oes, ond mae'n dweud rhywbeth wrthym wirioneddol ddiddorol am bobl. Y peth sy'n twyllo chi ac dwyn eich fuddugoliaeth, dyna rhywbeth sy'n fyw, dyna animeiddio, dyna allan i fynd â chi. Mae ganddo cyflwr meddyliol. Mae ganddo gred. Mae ganddo fwriad. Bod peth sy'n dwylo y gêm i chi, nid yw hynny'n. Mae hynny'n unig malfunctioning. Mae hyn yn mewn nifer o ffyrdd pam ei fod yn hawdd i daflu y gêm gyda phlant. Ond os ydych yn ceisio twyllo nhw a math o hawlio buddugoliaeth pan, chi'n gwybod, dim ond i leihau'r gêm, byddant yn dal i chi ar unwaith. Mae'r mathau hyn o effeithiau rydym yn ei weld yn dod allan o AI, maent yn eu haddysgu llawer am ein hunain ni. Mae pob hawl, dyna ni ar gyfer heddiw. Diolch yn fawr iawn i David a mae'r tîm cynhyrchu Harvard am ddod i lawr. [Cymeradwyaeth] Byddwn yn eich gweld am gwis un, ac yna ar gyfer un ddarlith olaf. Cael diwrnod gwych. [Cymeradwyaeth] [CHWARAE CERDDORIAETH] DAVID J Malan: Wel, yr ydym yn ôl pob tebyg mae angen i gyflwyno rhyw fath o amgryptio, iawn? Gan fod yna bydd y penawdau o Bydd ceisiadau HTTP rhain yn sgramblo fel bod unrhyw un ceisio arogli eich traffig Ni fydd mewn gwirionedd yn gallu eu gweld. Felly beth yw'r ateb i'r broblem hon? Wel, mae angen i ni gyflwyno mewn gwirionedd amgryptio yn y fformiwla, fel bod pan fydd y person yn trosglwyddo data o A i B, y gallwn send-- ddiogel [Chwerthin] Mae'r wybodaeth mewn ffordd y mae'r Ni all gwrthwynebwr, mewn gwirionedd, yn ei weld.