>> [Bermain muzik]
>> SPEAKER: Selamat kembali, semua orang.
Ini adalah CS50.
Dan hari ini, kita mempunyai banyak perkara yang menarik untuk dibincangkan.
Pertama, walaupun, saya perlu mengingatkan anda tentang beberapa perkara pentadbiran.
Minggu ini adalah kuiz satu, Rabu atau seksyen Yale yang
pada hari Selasa dan Khamis, pada Khamis.
Terdapat ulasan kuiz malam ini di Yale, 5:30-7:00.
Di Harvard, mereka mencatatkan satu semalam.
Dan semua orang boleh menonton dalam talian itu.
>> Juga, minggu ini atau awal minggu depan, kita ada kuliah CS50 terakhir kami.
[Meminta pertolongan] saya tahu.
Ia datang tidak lama lagi.
Pelajar Yale akan mempunyai sebenar bersyarah di sini di sekolah undang-undang
auditorium pada hari Jumaat.
Akan ada kek.
Pelajar Harvard akan mempunyai kuliah terakhir di dalam Sanders pada hari Isnin.
Terdapat juga akan menjadi kek.
>> Juga, minggu ini pada hari Jumaat, bagi mereka anda yang akan datang ke New Haven,
kita ada Expo CS50.
Kami mempunyai lebih daripada 30 kumpulan yang berbeza berdaftar
untuk menunjukkan kepada anda semua dari perahu layar autonomi,
kepada sistem yang mengiktiraf potret digital, ke komputer
muzik dan muzik komputer-besaran.
Oleh itu, sila menyertai kami.
Saya fikir ia akan menjadi masa yang hebat.
>> Hari ini, walaupun, kita dapat terus bercakap mengenai AI,
tentang kecerdasan buatan.
Dan salah satu daripada perkara-perkara yang kita akan mendapatkan untuk hari ini
adalah idea bagaimana untuk menggunakan AI untuk menyelesaikan masalah.
Sekarang, seperti biasa, mari kita mulakan dengan sesuatu yang mudah.
Dan kita akan mula dengan idea yang mudah.
Dan itu menggunakan carian.
>> Jadi bayangkan untuk satu minit bahawa saya mempunyai tugas yang saya perlukan untuk melaksanakan.
Dan saya ingin mempunyai tugas yang automatik oleh beberapa ejen perisian.
Bayangkan bahawa saya cuba untuk membuat satu set penerbangan dari, katakan, Boston
ke San Francisco.
Saya boleh pergi melalui dan saya boleh menggunakan salah satu carian dalam talian yang indah
alat, yang akan melakukan pada dasarnya proses yang sama bahawa kita
akan berjalan sampai hari ini.
Tetapi jika anda tidak mempunyai bahawa alat, apa yang anda akan lakukan?
>> Nah, anda boleh melihat dan ketika dan berkata, saya dalam Boston.
Apa penerbangan disediakan untuk saya?
Sekarang, mungkin saya mempunyai tiga penerbangan yang mungkin keluar dari Boston
yang sesuai dengan masa yang apabila saya perlu pergi.
Saya boleh membuat penerbangan ke Chicago.
Atau saya boleh terbang ke Miami.
Atau saya boleh membuat penerbangan ke New York.
Saya kemudian boleh melihat antara satu sama salah satu kota destinasi
dan berfikir tentang apa lokasi Saya mungkin boleh mencecah
dari setiap satu kota individu.
>> Jadi mungkin dari Chicago, saya boleh mendapatkan penerbangan terus ke San Francisco.
Itulah yang sangat baik.
Atau saya boleh mendapatkan penerbangan ke Denver.
Sekarang, mungkin bahawa penerbangan ke San Francisco adalah penyelesaian yang sempurna bagi saya,
tetapi mungkin tidak.
Mungkin saya mencari sesuatu itulah sedikit lebih murah
atau sedikit lebih baik untuk jadual saya.
Oleh itu, saya boleh mencari apa yang lain kemungkinan mungkin di luar sana.
Jadi saya boleh melihat Denver.
Dan dari Denver, baik, mungkin Saya boleh mendapatkan penerbangan ke Austin.
Dan dari Austin, mungkin saya boleh mendapatkan penerbangan ke Phoenix Sky Harbor, dan dari Phoenix
ke San Francisco.
Sekarang, saya tidak dilakukan lagi.
Kerana mungkin ada penerbangan terus dari New York
ke San Francisco yang sesuai untuk saya.
Atau mungkin ada penerbangan dari Miami melalui Denver itu jauh lebih murah.
Jadi saya masih perlu pergi.
Dan saya masih perlu melihat semua orang-orang bandar-bandar yang saya telah tidak disiasat lagi.
Saya perlu mendalam menyemak semua kemungkinan yang saya mungkin mempunyai.
>> Jadi dari New York, mungkin saya boleh mendapatkan penerbangan ke Nashville, dan dari Nashville
ke Austin.
Dan kemudian saya tahu di mana saya berada.
Dan kemudian aku mengetahui dari Austin, saya boleh membuat penerbangan ke Phoenix, dan dari Phoenix
ke San Francisco.
Jika saya terbang pertama ke Miami, walaupun, mungkin saya boleh mendapatkan penerbangan dari Miami
ke Nashville, atau dari Miami ke Austin.
>> Dan sekarang saya telah mencuba semua daripada kemungkinan.
Saya telah membina graf ini yang menunjukkan saya semua laluan mungkin
supaya aku dapat mengambil.
Apabila kita mewakili ini pelbagai masalah,
kita tidak akan mewakili mereka dengan jelas sebagai graf ini,
kerana graf yang tidak mewakili sejarah di mana kami telah hilang.
Mengetahui bahawa saya terbang dari Phoenix Sky Harbor ke San Francisco
tidak beritahu saya sama ada saya datang melalui Nashville, atau melalui Denver, atau melalui Miami.
>> Jadi apa yang saya akan lakukan sebaliknya adalah Saya akan membawa masalah yang sama,
dan saya akan mewakilinya sebagai pokok.
Dan pada akar pokok, di atas, saya akan meletakkan tempat yang saya bermula,
Boston.
Dan dari Boston, saya akan melihat semua lokasi mungkin
bahawa saya boleh pergi ke.
Nah, dalam kes ini, saya mempunyai tiga, Chicago, New York, dan Miami.
Dan kemudian saya akan meneroka setiap kanak-kanak ini di pokok itu.
>> Dari Chicago, saya melihat bahawa saya mempunyai dua penerbangan.
Saya boleh terbang terus ke San Francisco atau ke Denver.
Sekarang San Francisco, itulah matlamat saya.
Itulah destinasi saya.
Itu akan menjadi daun pokok ini.
Iaitu, saya tidak akan pergi tempat selepas San Francisco.
Dari Denver, walaupun, Saya boleh terbang dari Denver
ke Austin, dari Austin ke Phoenix, dan dari Phoenix Sky Harbor ke San Francisco.
Dan kini sekali lagi, saya telah mencapai daun.
>> Saya kemudian dapat kembali ke depan bandar bahawa saya telah tidak diterokai sepenuhnya.
Itu akan menjadi New York, pergi kembali kepada bahagian atas pokok saya,
turun ke New York.
Dari New York, saya boleh terbang ke Nashville, dari Nashville ke Austin,
dari Austin ke Phoenix, dan dari Phoenix Sky Harbor ke San Francisco.
Dan akhirnya, satu bandar saya tidak melihat lagi, Miami.
>> Nah, dari Miami Saya berkata, saya mempunyai dua kemungkinan, Nashville atau Austin.
Jika saya membuat penerbangan ke Nashville, dan kemudian saya terbang dari Nashville, untuk Austin, ke Phoenix,
ke San Francisco.
Jika saya membuat penerbangan ke Austin, saya terbang Austin, ke Phoenix, ke San Francisco.
Dan kini saya mempunyai pokok.
Ia adalah pokok yang lengkap.
Itu semua kemungkinan dan semua laluan yang saya boleh ambil.
Iaitu, jika saya bermula pada akar pohon di bahagian atas
dan saya pergi ke salah satu daripada daun, ia memberitahu saya bukan sahaja
di mana saya akan berakhir, San Francisco,
tetapi ia memberitahu saya laluan yang Saya perlu ke sana.
>> Sekarang, yang satu ini adalah yang terbaik?
Nah, apa-apa tentang ini masalah lagi memberitahu saya
yang mana satu adalah penyelesaian terbaik.
Mungkin saya mengambil berat yang paling mengenai berapa banyak masa saya di udara,
atau jarak yang saya terbang.
Dalam kes itu, Chicago ke San Francisco mungkin jumlah yang singkat
batu di udara.
>> Mungkin saya mengambil berat tentang kos.
Dan kita semua tahu penerbangan terus biasanya lebih mahal.
Jadi mungkin jika saya mengambil ini jenis laluan ke belakang
melalui Miami, Nashville, Austin, Phoenix, mungkin kemudian
Saya mendapat harga yang lebih rendah.
Tetapi saya dapat mengoptimumkan di mana-mana kriteria yang saya hargai.
Siapa yang mendapat yang terbaik dalam penerbangan Wi-Fi, atau yang
lapangan terbang mempunyai makanan terbaik yang ada.
Dan setiap daripada mereka mungkin memberikan saya penyelesaian yang berbeza
yang saya lihat sebagai yang terbaik.
>> Ini jenis masalah, di mana kita akan
untuk membina pokok ini kemungkinan, dan kemudian
melihat setiap orang-orang laluan individu, dan memeriksa
yang mana satu memenuhi kriteria untuk kita,
kita akan memanggil masalah-masalah carian.
Dan kita mempunyai banyak algoritma, ada yang
kita lihat sudah, untuk pergi dan meneroka pokok-pokok.
Kita boleh melakukannya dengan cara yang saya hanya melakukan, carian kedalaman pertama,
akan turun sebagaimana yang kita boleh sehingga kita memukul daun, dan kemudian datang kembali ke atas,
dan akan segera kembali ke bawah.
Atau kita boleh melakukan apa yang dipanggil carian keluasan pertama.
Kita boleh mengembangkan segala-galanya di bahagian atas, dan kemudian
segala-galanya satu baris di bawahnya itu, dan kemudian
segala-galanya satu baris bawah itu.
Pokok-pokok carian adalah asas kepada AI.
Tetapi mereka tidak cukup mendapatkan betul sepanjang masa.
Malah, dalam banyak kes-kes bahawa kita benar-benar mengambil berat tentang,
kita mahu membina sebuah tiang, tetapi kita tidak benar-benar
mendapatkan untuk membuat semua keputusan.
>> Ini adalah keadaan yang dikenali sebagai carian pertentangan, juga dikenali
bagaimana untuk menulis permainan bermain sistem dan mendapat bayaran untuk itu.
Tetapi ini adalah jenis sistem di mana saya
mungkin boleh memilih apabila saya pergi dari Boston, yang bandar saya pergi ke depan.
Tetapi selepas itu, orang lain mungkin akan mendapat untuk membuat keputusan tentang di mana saya terbang.
Jadi untuk membina ini struktur jenis, kami
akan perlu mengambil sedikit pendekatan yang berbeza dengannya.
Kami tidak akan dapat hanya mencari melalui pokok itu
lagi, kerana kita tidak satu yang dalam kawalan
setiap mata tersebut keputusan.
>> Jadi mari kita bayangkan yang mudah permainan seperti tic-tac-toe.
Saya boleh bermula dengan lembaga-benar kosong.
Dan dalam tic-tac-toe, X mendapat untuk bermain pertama.
Oleh itu, saya boleh berfikir tentang semua bergerak mungkin bahawa X boleh membuat.
Dan jika saya bermain satu X, yang hebat.
Saya mempunyai sembilan mungkin bergerak yang saya boleh membuat.
Saya boleh meletakkan X dalam mana-mana satu dari orang-orang sembilan kedudukan.
>> Dan kemudian dari setiap mereka, saya dapat membayangkan apa yang berlaku seterusnya.
Nah, dalam kes ini, yang lain Pemain akan dapat mengambil giliran.
O akan dapat mengambil giliran.
Dan dari setiap orang, terdapat akan menjadi lapan tempat yang berbeza
O yang boleh letakkan penanda mereka.
>> Katakan saya membuat keputusan bahawa saya adalah akan meletakkan X yang di tengah.
Yang sentiasa seolah-olah seperti langkah pembukaan yang baik.
Saya boleh melihat di bawah itu, lapan bergerak mungkin bahawa O membuat.
Sekarang, jika saya bermain X, itu indah.
Saya boleh memilih yang mana satu saya pergi ke, yang di tengah-tengah.
Tetapi sekarang O mendapat untuk memilih.
Dan saya tidak mempunyai kawalan atas keputusan itu.
>> Tetapi dari setiap orang-orang jawatan lembaga boleh,
ada maka yang lain menetapkan kemungkinan.
Apabila ia datang untuk menjadi Yang saya sekali lagi, saya akan
mendapatkan untuk memilih dan berkata, dengan baik, jika O bergerak ke, baik,
tempat yang pertengahan di sebelah kiri, kemudian Saya mempunyai satu set kemungkinan
di mana saya boleh mengambil langkah seterusnya.
Dari orang-orang, saya boleh mempertimbangkan semua kemungkinan di bawahnya.
Dan kemudian O akan mendapat untuk memilih di kalangan mereka.
>> Dan saya boleh menjaga bangunan ini pokok keluar sehingga saya sampai ke titik
jika salah seseorang menang game-- itulah
tidak perlu lagi dipertimbangkan daun node-- atau lembaga adalah benar-benar penuh
dan tidak ada yang menang.
Dan itu juga akan menjadi nod daun.
Itu akan menjadi seri.
>> Tetapi perkara yang rumit dengan ini adalah jika ini hanya carian biasa
masalah, saya akan dapat berkata, dengan baik, X perlu pergi sini.
Hai perlu pergi ke sana.
Dan kemudian X perlu pergi di sini.
Dan kemudian O harus pergi ke sana.
Dan kemudian X boleh mendapatkan tiga berturut-turut, dan saya menang.
Dan permainan itu akan menjadi lebih dalam lima langkah, tiga bagi saya,
dua lawan saya.
Tetapi saya tidak sentiasa boleh memilih itu.
>> Jadi, apa yang kita akan perlu lakukan
adalah kita akan mempunyai mempunyai strategi baru.
Dan strategi yang algoritma permainan-bermain sering menggunakan
adalah apa yang dipanggil MINIMAX.
Idea utama MINIMAX ialah kami
akan memilih langkah yang memberikan lawan kami set yang paling teruk mungkin
langkah-langkah yang mereka boleh buat.
Ia tidak berbuat apa-apa yang baik saya untuk memilih satu langkah di mana
Saya mungkin boleh menang selepas itu, kerana lawan saya tidak
akan memberikan saya peluang itu.
Mereka akan memilih beberapa hasil dahsyat untuk saya.
Jadi, saya akan membuat bergerak yang memaksa lawan saya
untuk melakukan sesuatu yang lebih baik untuk saya.
Baiklah.
Mari kita lihat bagaimana yang memainkan keluar.
Jadi di sini adalah algoritma kami dalam kod pseudo.
Kita akan menjana pokok permainan keseluruhan.
Kami akan membina keseluruhan struktur.
Dan kemudian kita akan melalui.
Dan di bahagian paling bawah di setiap nod terminal, pada setiap daun,
kami akan menilai bagaimana berharga itu kepada saya?
Dan kita akan kepada perkara-perkara nilai yang adalah baik untuk saya sebagai positif.
Perkara-perkara yang tidak baik untuk saya akan kurang positif, atau sifar,
atau negatif.
>> Jadi dalam tic-tac-toe, mungkin kemenangan bagi saya adalah baik.
Itulah salah satu.
Dan tali leher adalah sifar.
Dan sesuatu yang merugikan saya, mungkin itu salah satu yang negatif.
Apa yang penting adalah bahawa lebih baik ia adalah untuk saya, semakin tinggi skor
ia menerima.
Dari orang-orang kemungkinan di bawah, maka kita akan menapis atas.
Dan apabila ia adalah peluang saya untuk memilih antara satu set alternatif,
Saya akan memilih satu yang mendapat skor tertinggi.
>> Dan setiap kali itu saya lawan berubah untuk memilih,
Saya akan menganggap bahawa mereka akan memilih salah satu yang mendapat markah yang paling rendah.
Dan jika saya melakukan ini sepanjang jalan naik ke puncak pokok itu,
Saya akan memilih jalan yang memberikan saya hasil yang terbaik yang saya boleh mendapatkan,
menganggap bahawa lawan saya membuat semua langkah yang tepat.
>> Baiklah, jadi mari kita lihat ini dalam tindakan pertama.
Dan kemudian kita akan benar-benar melihat kod untuk itu.
Jadi bayangkan Saya mempunyai pokok ini besar.
Dan sekarang saya tidak bermain tic-tac-toe.
Saya mahu memberi anda sesuatu yang sedikit lebih kaya.
Jadi saya telah mendapat beberapa permainan di mana ada banyak skor yang berbeza
bahawa saya boleh mempunyai pada akhir.
Oleh itu, saya membina pokok lengkap ini.
Dan saya dapat bergerak dahulu.
Saya pada akar pokok.
>> Dan saya boleh memilih bahawa- jadi saya dapat untuk memaksimumkan seluruh nod pertama.
Dan kemudian lawan saya mendapat untuk pergi.
Dan kemudian saya dapat pergi sekali lagi.
Jadi turun di bahagian bawah, saya mempunyai satu set kemungkinan yang saya boleh dipilih,
negeri terminal yang berbeza permainan.
Jika saya turun kerana paling kiri penjuru,
dan saya melihat bahawa saya telah mendapat pilihan antara lapan, tujuh dan dua,
juga, saya merupakan salah seorang yang mendapat untuk memilih.
Jadi, saya akan memilih yang terbaik daripada mereka.
Saya akan memilih lapan.
>> Jadi saya tahu bahawa jika saya turun ke titik itu,
Saya akan dapat untuk mendapatkan bahawa lapan mata.
Jika saya berakhir di titik seterusnya berakhir, nod seterusnya ke atas,
sembilan, satu, atau enam, baik, saya akan memilih yang terbaik daripada mereka.
Saya akan memilih sembilan.
Jika saya mempunyai pilihan antara dua, dan empat, dan satu,
Saya akan memilih empat, yang paling tinggi.
>> Sekarang, jika saya melihat tahap di atas itu, lawan saya
adalah yang mendapat untuk membuat pilihan itu.
Jadi lawan saya mendapat untuk pilih, saya mahu memberi
perkara yang akan untuk mendapatkan dia lapan mata,
atau saya memberinya perkara itu akan memberinya sembilan mata,
atau benda yang akan untuk memberinya empat mata?
Dan lawan saya, yang rasional, akan
untuk memilih sekurang-kurangnya orang-orang, akan memilih empat.
>> Dan saya boleh melakukan ini melalui keseluruhan pokok itu.
Saya boleh pergi ke bawah untuk yang set pertengahan tiga.
Dan saya boleh memilih antara satu, tiga dan lima.
Dan saya mendapat untuk memilih.
Jadi saya memilih lima.
Saya boleh memilih tiga, sembilan, atau dua.
Saya boleh memilih, jadi saya memilih sembilan.
Enam, lima, atau dua, saya pilih.
Saya boleh memilih enam.
Tahap di atas itu, yang mendapat untuk memilih?
Siapa yang mendapat untuk memilih?
Lelaki yang lain, lawan saya.
Jadi mereka memilih lima, sembilan, atau enam, yang mana satu?
>> PENONTON: Lima.
>> SPEAKER: Mereka memilih lima.
Mereka boleh memilih minimum.
Kemudian yang terakhir, memilih satu, dua, atau tiga.
Saya boleh memilih, jadi saya memilih tiga.
Sembilan, tujuh, atau dua, saya memilih sembilan.
Dan 11, enam atau empat, saya memilih 11.
Lawan saya kemudian memilih tiga, sembilan, atau 11, memilih minimum.
Beliau memberikan saya tiga.
Dan kemudian akhirnya di bahagian atas pokok itu, saya dapat memilih lagi.
Dan saya dapat memilih antara empat, lima, atau tiga.
Jadi saya mengambil lima.
>> Jika saya mendapat untuk mengawal segala-galanya, saya akan mengambil jalan yang membawa kepada 11.
Tetapi saya tidak dapat membuat pilihan itu.
Jika saya pergi ke jalan itu.
Lawan saya akan memaksa saya ke pilihan yang membawa kepada tiga.
Jadi yang terbaik yang boleh saya lakukan adalah untuk mengambil cawangan pertengahan,
membuat bahawa pilihan itu akhirnya akan membawa saya ke lima mata.
Itulah yang MINIMAX tidak.
>> Baiklah.
Mari kita lihat pada itu.
Jadi di sini di CS50 IDE merupakan program yang
melaksanakan MINIMAX untuk bermain tic-tac-toe.
Kami akan membina sehingga representasi.
Kita akan mempunyai dua opponent-- atau dua pemain, komputer kita
Pemain dan pemain manusia.
Jumlah pemain akan bermain O. Yang akan menjadi pemain mesin.
Mereka boleh bergerak kedua.
Dan pemain yang lain, kami pemain manusia, akan X.
>> Dan untuk membuat hidup saya yang sedikit mudah, saya akan
label yang negatif satu pemain.
Jadi saya hanya boleh membiak oleh salah negatif untuk menukar
antara seorang pemain dan yang lain.
Baiklah, jadi mari kita lihat pada apa yang kita benar-benar akan lakukan.
Kami akan menentukan lembaga kami.
Ia akan menjadi, baik, kita akan untuk membolehkan ia menjadi tiga dengan tiga,
atau kita juga boleh bermain lima lima atau tujuh
oleh tujuh tic-tac-toe jika anda lebih seperti, berdasarkan beberapa dimensi D.
>> Dan kita akan mempunyai pasangan fungsi penolong
yang akan melakukan perkara seperti memulakan yang screen-- atau maaf,
memulakan pembolehubah kami, kosongkan skrin, menarik papan pada skrin,
salah satu yang memeriksa papan untuk melihat sama ada atau tidak
ada satu pemenang, satu yang mem-parsing melalui baris arahan,
hanya untuk membantu antara satu yang berbunyi dalam input, dan satu fungsi dipanggil MINIMAX.
Dan itulah yang kami akan peduli tentang.
Tetapi mari kita lihat pertama di utama.
>> Apa yang kita lakukan?
Nah, kita akan menghuraikan baris arahan kami,
hanya membaca dan melihat apa yang papan dimensi kami ingin mempunyai.
Kami akan memulakan lembaga kami.
Dan kemudian kita akan masukkan satu gelung liar yang besar, berkali-kali
terima pertukaran sehingga permainan menang, atau tidak ada bergerak meninggalkan.
Setiap kali kita pergi melalui itu gelung, kami akan mengosongkan skrin.
Kami akan menarik papan pada skrin.
Dan kami sengaja semacam pengabstrakan ini jauh sebagai subrutin,
supaya kita tidak perlu bimbang terlalu banyak mengenai butir-butir bagaimana ia berlaku.
>> Anda akan perlu kod di lewat hari ini.
Dan jika anda mahu untuk melihat melalui dan mengetahui, anda boleh melihat mereka semua.
Tetapi kita akan menarik papan pada skrin.
Dan kemudian kami akan menyemak dan lihat, kita mempunyai pemenang?
Adakah seseorang memenangi permainan ini?
Jika mereka ada, kita akan mencetak keluar mesej kemenangan.
Dan kita akan menamatkan permainan.
>> Kami juga akan menyemak dan melihat jika ada seri.
Ia akan menjadi mudah untuk melihat jika ada seri.
Ini bermakna bahawa semua ruang penuh, tetapi tidak ada seorang pemenang lagi.
Kita boleh mengisytiharkan seri dan dilakukan.
Kemudian meat-- sebenar jika ia seorang pemain mesin,
kami akan membenarkan bahawa Pemain mesin untuk mencari
melalui menggunakan algoritma MINIMAX ini, untuk mencari langkah terbaik yang ia boleh.
Dan kemudian kita akan meletakkan bahawa langkah ke atas.
>> Jika tidak, jika ia adalah satu pemain manusia, kami akan membaca beberapa input daripada manusia.
Dan kemudian sama ada manusia pemain atau pemain mesin,
kami akan melakukan beberapa sedikit bit semakan ralat,
memastikan ia kekal dalam sempadan dimensi sebenar lembaga
yang kita ada, pastikan bahawa ruang yang kosong,
bahawa tidak ada orang yang meletakkan yang bahagian di sana sudah.
Dan kemudian kita hanya akan meletakkan sekeping di atas kapal,
menukar pemain untuk lapisan seterusnya, dan kenaikan berapa banyak bergerak berlaku.
>> Itulah gelung utama permainan tic-tac-toe kami.
Minimax, maka, adalah betul-betul algoritma yang kita sebelum ini.
Satu-satunya pelarasan yang kami telah membuat supaya kita
boleh bermain lebih tinggi papan dimensi adalah kami telah
disimpan parameter tambahan ini dipanggil mendalam.
Dan kedalaman hanya berkata, jika saya mencari ke bawah melalui pokok yang
dan saya mendapat begitu jauh ke bawah selepas beberapa kedalaman tahap
bahawa saya hanya tidak mahu pergi mana-mana lagi,
Saya akan berhenti dan hanya menilai lembaga pada ketika itu.
Saya akan menyemak dan melihat jika ada seorang pemenang.
Jika ada seorang pemenang, saya kembali mereka.
Jika tidak, saya akan pergi melalui gelung.
Dan saya akan berkata, untuk semua lokasi yang mungkin
bahawa saya mungkin boleh mengambil sebagai langkah saya, saya akan
membina papan hipotesis termasuk langkah saya di atas kapal itu,
dan kemudian secara rekursif panggilan MINIMAX.
>> Jika ia langkah saya, saya dapat mencari salah satu yang mendapat markah yang terbesar.
Jika ia langkah lawan saya, kita dapati salah satu yang mendapat markah yang minimum.
Dan semua yang lain adalah penyimpanan hanya rekod.
Baiklah, jadi mari kita lihat jangka masa ini.
Sebenarnya, mungkin kita boleh mendapatkan beberapa sukarelawan
untuk datang dan bermain tic-tac-toe.
[Didengar] satu, dan satu lagi, dua, di sana.
Naiklah.
>> Jadi mari kita pergi ke depan dan memulakan semula ini sepenuhnya.
Jadi, hi.
>> PENONTON: Hi.
>> SPEAKER: Apa nama anda?
>> PENONTON: Gorav.
SPEAKER: Gorav.
>> PENONTON: Saya Layla.
>> SPEAKER: Dan Layla dan Layla, maaf.
Naiklah.
Gorav, kita akan mempunyai anda pergi pertama.
Dan saya akan bertanya kepada anda untuk menjadi tidak sangat baik Pemain tic-tac-toe.
OK, jadi semua tekanan dimatikan pada anda.
Mari kita lihat, walaupun, bahawa mesin kami Pemain sebenarnya boleh melakukan sesuatu yang bijak.
Jadi teruskan.
Anda akan menaip di mana koordinat anda ingin meletakkan X anda di dalam.
A0, OK, dan mesin yang telah pergi segera dan meletakkan nama di A1.
>> Letakkan O di papan.
Baiklah, sekarang pergi ke hadapan.
Anda ingin pergi?
C2.
Pemain Mesin kami telah mengambil persegi tengah, menyekat anda.
Sehingga adalah yang baik, perkara yang bijak untuk ia lakukan.
Anda menyekatnya.
Itulah yang sangat baik.
Ia mengambil sudut sana.
>> Dan ia akan memaksa anda untuk mengambil satu ruang lepas, B0.
Dan permainan berakhir di seri.
Tetapi ia memainkan munasabah permainan terhadap anda, bukan?
Baiklah, terima kasih sangat banyak, Gorav.
>> [Tepuk tangan]
>> Baiklah, Layla, kita akan sehingga permainan pada anda di sini.
>> PENONTON: Oh, hebat.
>> SPEAKER: Kami akan memberi anda empat oleh empat tic-tac-toe.
Sekarang, dalam empat oleh empat, anda perlu untuk memenangi empat berturut-turut, bukan tiga berturut-turut.
Dan itu semua anda.
Jadi Layla mengambil D1.
Kami sedang akan mengikuti pemain komputer kami di sini.
Tiga oleh tiga tic-tac-toe adalah jenis perkara itu adalah mudah bagi kita semua.
Tetapi ia masih baik untuk melihat pemain komputer membuat langkah bijak.
Empat oleh empat sampai ke menjadi lebih sukar sedikit.
>> Baik dilakukan.
Baiklah, jadi ini Layla menyelesaikan serangan.
Oh, dan kita sepatutnya berakhir di sana.
Tetapi mari kita buat satu lagi di sini.
Jadi Layla, terima kasih.
Baik dilakukan.
>> [Tepuk tangan]
>> Jadi Pemain tic-tac-toe kita pergi melalui dan mendapati lokasi,
menyelesaikan mereka menggunakan MINIMAX ini.
Dan saya mempunyai tetapan mendalam pada itu supaya ia
tidak akan berjalan terlalu cepat, yang mungkin mengapa
Layla dapat pergi dengan baik di hadapan seperti dia, dan melakukan dengan baik.
Tetapi sistem ini yang hanya pergi melalui dan kekerasan
pergi lebih dalam, dan lebih dalam, dan lebih mendalam, dan mencari penyelesaian
yang mereka perlukan, orang-orang jenis sistem agak berjaya ini, baik,
permainan papan standard.
>> Dan sebenarnya, jika kita melihat seorang tiga oleh tiga permainan tic-tac-toe,
ini adalah pada dasarnya masalah diselesaikan.
Dan ini ialah gambar rajah yang indah dari Randall Munroe di XKCD,
menunjukkan yang bergerak anda perlu mengambil, diberikan bergerak lawan.
Ini adalah sesuatu yang kita boleh mudah menentukan terlebih dahulu.
Tetapi apa yang berlaku seperti yang kita mendapatkan lebih permainan kompleks, permainan yang lebih rumit,
di mana terdapat papan lebih besar, lebih kemungkinan, strategi yang lebih mendalam?
>> Ternyata ini kekerasan masih mencari
melakukan agak baik, kecuali apabila anda sampai ke titik
di mana pokok yang begitu besar bahawa anda tidak boleh mewakili semua.
Apabila anda tidak boleh mengira keseluruhan pokok itu, apabila anda tidak boleh pergi ke hadapan dan tolak
diri anda ke titik di mana anda telah mendapat keseluruhan pokok itu dalam ingatan,
atau sama ada anda boleh mendapatkannya dalam ingatan dan ia akan hanya
membawa anda terlalu lama untuk mencari melalui itu, anda perlu melakukan sesuatu yang lebih pintar.
>> Dalam usaha untuk melakukan itu, anda perlu melakukan dua perkara.
Pertama, anda perlu mencari beberapa cara mengehadkan kedalaman anda.
Nah, itu OK.
Kita boleh mencari beberapa bagus, tahap minimum dan berkata, anda hanya boleh pergi begitu dalam.
Tetapi apabila anda berbuat demikian, ini bermakna anda mempunyai ini papan sebahagiannya tidak lengkap.
Dan anda perlu untuk memilih, saya suka ini papan sebahagiannya tidak lengkap,
atau lembaga sebahagiannya tidak lengkap ini?
>> Dan kami empat oleh empat permainan tic-tac-toe,
pemain komputer kami pun turun ke bawah dan ia berkata,
Saya telah mendapat dua papan yang berbeza.
Salah satu tidak adalah kemenangan.
Salah satu tidak adalah kerugian.
Salah satu tidak adalah seri.
Bagaimana untuk memilih antara mereka?
Dan ia tidak mempunyai cara yang bijak untuk melakukannya.
>> Kami melihat ini jenis penilaian berlaku sepanjang masa
seperti yang kita masuk ke dalam permainan yang lebih kompleks.
Chess adalah contoh yang baik.
Dalam catur, kita ada, pertama sekali, lembaga yang lebih besar.
Kami mempunyai lebih keping.
Dan kedudukan serpihan ini dan cara yang serpihan ini bergerak
adalah amat penting.
Jadi, jika saya mahu menggunakan MINIMAX, Saya perlu dapat menentukan
dan berkata, lembaga ini, di mana tiada siapa yang menang atau kalah lagi,
entah bagaimana lebih baik daripada ini lain lembaga, di mana tiada siapa yang menang atau kalah.
>> Untuk berbuat demikian, saya mungkin melakukan perkara seperti saya mungkin hanya
mengira berapa keping yang saya ada dan berapa keping yang anda ada?
Atau saya mungkin memberikan yang berbeza buah mata yang berbeza.
Ratu saya adalah bernilai 20 mata.
Pajak gadai anda bernilai satu mata.
Siapakah yang mempunyai lebih banyak mata jumlah?
Atau saya boleh mempertimbangkan perkara yang suka, yang punya jawatan lembaga yang lebih baik?
Yang seterusnya ialah ia akan datang, apa-apa yang saya boleh
jangan menilai dengan lebih tepat yang kemungkinan ini
adalah lebih baik tanpa mendalam mengingati
setiap langkah yang boleh datang selepas itu.
>> Sekarang untuk membuat kerja-kerja itu, salah satu perkara itu
akan menjadi benar-benar penting untuk kita tidak hanya bergerak lurus
turun ke kedalaman tertentu had, tetapi dapat berkata,
salah satu daripada idea-idea yang saya mempunyai begitu buruk bahawa itu
tidak bernilai mengingati semua cara yang mungkin
barang-barang boleh pergi dari buruk.
Untuk berbuat demikian, kami akan menambah ke dalam MINIMAX prinsip yang dipanggil Alph-beta.
Dan alpha-beta berkata, jika anda mempunyai idea yang buruk,
jangan buang masa anda cuba untuk mengetahui dengan tepat bagaimana buruk ia adalah.
>> Jadi di sini adalah apa yang kita akan lakukan.
Kami akan mengambil yang sama prinsip-prinsip yang kita ada sebelum,
Jenis MINIMAX yang sama penggeledahan, hanya kami
akan mengesan, bukan sahaja daripada nilai sebenar yang kita ada, tetapi kita akan
mengesan terbaik mungkin nilai yang saya dapat,
dan yang paling teruk mungkin keputusan saya boleh mempunyai.
Dan bila-bila masa yang paling teruk mungkin Perkara yang sedang besar,
Saya akan meninggalkan bahagian pokok itu.
Dan aku tidak akan peduli melihat lagi.
>> Baiklah, jadi bayangkan bahawa kita bermula dengan ini pokok permainan sama.
Dan sekarang kita akan pergi turun lagi, semua jalan ke bawah
ke sudut kiri bawah.
Dan di bawah yang telah meninggalkan sudut, kita melihat dan kami menilai papan ini.
Mungkin ia adalah empat oleh empat tic-tac-toe kapal, atau mungkin ia adalah papan catur.
Tetapi kita melihat ia, dan kami menilai , dan kita akan mendapat nilai lapan.
>> Pada ketika itu, kita tahu bahawa kita akan mendapat sekurang-kurangnya
lapan mata daripada keputusan bahagian bawah ini.
Tidak kira apa yang lain dua adalah, yang tujuh dan dua.
Mereka boleh menjadi apa-apa nilai-nilai mereka mahu menjadi.
Kita akan mendapat sekurang- kurangnya lapan mata.
Baiklah, tetapi kita boleh teruskan dan menyemak.
Mungkin salah seorang daripada mereka adalah lebih baik daripada lapan.
>> Kami melihat tujuh.
Adakah itu lebih baik daripada lapan?
Tidak, itu tidak berubah pendapat kami sama sekali.
Kita melihat kedua-dua.
Adakah itu lebih baik daripada lapan?
Tidak, itu tidak berubah pendapat kami sama sekali.
Jadi sekarang kita tahu kita telah habis semua kemungkinan di sana.
Kita tidak akan mendapat apa-apa yang lebih baik daripada lapan.
Kita akan mendapatkan tepat lapan.
>> Dan supaya kita menukar nod itu dan katakan, yang kini kepastian.
Kita naik satu tahap di atas itu.
Dan sekarang kita tahu sesuatu tentang tahap pengurangan.
Kita tahu bahawa kita tidak akan mendapat lebih daripada lapan mata jika kita turun
arah itu.
Kerana walaupun mereka Dua cawangan berubah
menjadi hebat dan bernilai beribu-ribu mata setiap satu,
lawan kami akan memberi kita minimum, dan memberi kita lapan.
Baiklah, baik, mari kita lihat.
Kami akan terus pergi ke jalan itu.
Kami turun ke tengah-tengah yang di sebelah kiri.
Kami melihat ke bawah dan kami melihat ada sembilan.
Kita tahu bahawa kita akan mendapat sekurang-kurangnya sembilan mata dengan pergi ke bawah
bahawa jalan tengah.
Dan pada ketika ini, kita hanya boleh berhenti seketika.
Dan kita boleh berkata, melihat, saya kenal tahap di atas,
Saya akan mendapat tidak lebih daripada lapan menunjukkan dengan pergi ke arah ini.
Tetapi jika saya pergi ke tengah-tengah jalan dan bukan jalan yang kiri,
Saya akan mendapat sekurang-kurangnya sembilan mata.
>> Lawan saya tidak pernah akan biarlah saya pergi ke jalan yang pertengahan.
Mereka boleh memilih.
Dan mereka akan memilih jalan ke kiri ke arah lapan,
dan bukan ke tengah-tengah ke arah apa yang sekurang-kurangnya sembilan mata.
Jadi pada ketika itu, saya akan berhenti.
Dan saya akan berkata, anda tahu apa?
Saya tidak perlu melihat apa-apa lebih ke bawah ke arah itu.
Oleh kerana saya tidak akan ke sana.
>> Saya boleh melangkau lebih satu itu, dan saya boleh melangkau lebih enam,
kerana itu tidak pernah akan berlaku.
Jadi saya akan pergi ke bawah dan saya akan mempertimbangkan kemungkinan yang akan datang.
Saya pergi ke sana dan saya katakan, saya melihat dua.
Saya tahu jika saya mendapat ke sini, saya akan mendapatkan sekurang-kurangnya dua.
OKAY.
Saya terus pergi.
Saya melihat empat.
Saya tahu saya akan mendapat sekurang-kurangnya empat.
Masih banyak di antara empat dan lapan, walaupun.
Jadi saya teruskan.
Saya melihat ke bawah dan saya melihat ada satu.
Baiklah, saya tahu jika Saya pergi ke jalan ini,
Saya akan dapat untuk memilih empat.
Apa yang lawan saya akan lakukan?
Antara sesuatu yang memberikan saya lapan, sesuatu yang memberikan saya empat,
dan sesuatu yang memberikan saya sekurang-kurangnya sembilan,
dengan baik, dia akan memberi saya empat.
Dan saya tahu kini berada di paling atas, saya akan
dapat mendapatkan sekurang-kurangnya empat mata daripada permainan ini.
>> Idea alfa-beta adalah untuk memotong bahagian-bahagian pokok itu supaya
bahawa saya tidak melihat mereka lagi.
Tetapi ia masih kelihatan seperti saya telah melihat banyak pokok.
Mari kita terus pergi ke bawah.
Kami akan pergi ke satu depan sekarang.
Turun di bahagian bawah, saya mendapati satu.
Saya tahu saya akan mendapatkan sekurang-kurangnya satu.
Saya terus mencari.
>> Saya mencari seorang tiga.
Saya tahu saya akan mendapat sekurang-kurangnya tiga.
Saya terus pergi.
Saya mencari seorang lima.
Saya tahu saya akan mendapat lima jika saya mendapat ke bawah di jalan itu.
Dan saya juga tahu kemudian yang lawan saya, jika saya
pilih pertengahan tiga pilihan besar,
dia akan memberikan saya sesuatu yang lima atau kurang.
>> OKAY.
Saya boleh terus pergi sana.
Saya boleh melihat ke bawah dan saya boleh berkata, apa yang saya akan
untuk mendapatkan jika saya pergi ke jalan menengah?
Saya akan mendapatkan, baik, tiga di sana.
Saya akan mendapat sesuatu yang sekurang-kurangnya tiga.
Masih ada perkara antara tiga dan lima, jadi saya terus mencari.
Oh, sembilan, saya akan pasti mengambil yang lebih tiga.
Saya akan mendapat sekurang-kurangnya sembilan jika saya pergi ke jalan yang pertengahan.
>> Sekarang lawan saya berhenti dan berkata, melihat, tidak ada gunanya lagi.
Saya tahu bahawa saya lawan pengurangan, dia
akan memberikan saya perkara itu kurang daripada atau sama dengan lima,
bukannya perkara itu lebih besar daripada atau sama dengan sembilan.
Saya berhenti.
Saya tidak melihat apa-apa lagi pada itu.
Saya terus pergi.
>> Saya melihat ke bawah pada satu ini.
Turun ke bawah, saya mendapati enam.
Saya tahu saya akan mendapat sekurang-kurangnya enam.
Dan apa yang boleh saya lakukan?
Saya boleh berhenti.
Kerana ada pilihan di antara sesuatu yang sekurang-kurangnya enam
dan sesuatu yang kurang daripada lima, dia
akan memberikan saya perkara yang yang kurang daripada lima.
Dan sekarang saya tahu saya akan untuk mendapatkan tepat pilihan itu.
Saya akan mendapatkan lima pilihan.
>> Saya naik semula ke atas.
Yang saya akan memilih antara sesuatu
yang lebih besar daripada atau sama dengan empat, atau sesuatu yang sama dengan lima?
Saya akan mengambil sesuatu yang sekurang-kurangnya lima.
Saya pergi ke jalan terakhir, semua jalan turun ke bawah.
Ada satu a.
OK, sekurang-kurangnya saya akan mendapat satu mata.
Saya terus pergi.
Dua, oh, itu lebih baik daripada satu.
Saya akan mendapatkan sekurang-kurangnya dua.
Saya mencari seorang tiga.
Saya tahu saya akan mendapat tiga.
>> Dan titik di atas itu, lawan saya akan
untuk memberi saya sesuatu yang kurang daripada atau sama dengan tiga.
Dan sekarang saya boleh berhenti.
Kerana dalam pilihan antara saya yang mampu untuk mendapatkan lima dan lawan saya
memberi saya sesuatu yang kurang daripada tiga, Saya sentiasa akan mengambil yang lima.
Jadi, saya tidak menilai yang Bahagian bawah pokok itu sama sekali.
>> Sekarang, ini mungkin kelihatan kecil.
Tetapi apabila bit sedikit aritmetik, lebih besar daripada dan kurang daripada,
boleh dipotong dari bahagian keseluruhan pokok ini pesat berkembang,
yang membawa kepada yang besar jumlah simpanan, simpanan
yang cukup besar saya yang boleh mula bermain kompetitif
di lebih banyak permainan yang kompleks.
>> Baiklah, jika kita melihat saiz dan kerumitan permainan yang berbeza,
tic-tac-toe adalah contoh mudah kami.
Kami mempunyai papan kecil, tiga oleh tiga.
Kita dapat, paling banyak, purata kira-kira empat pilihan yang berbeza
seperti yang kita pergi melalui permainan.
Kami mempunyai tempat di sekitar 10 kepada kelima daun yang berbeza mungkin.
Dan membina tic-tac-toe Pemain, baik, kita lakukan itu.
Ia mudah.
>> Jika kita pergi ke sesuatu yang lebih kompleks, seperti menyambung empat.
Adakah anda masih ingat permainan ini di mana anda jatuh token sedikit?
Ia adalah satu enam tujuh kapal, tidak yang lebih besar, masih
mempunyai kira-kira cawangan yang sama faktor seperti tic-tac-toe.
Saya mempunyai kira-kira empat pilihan di mana saya boleh meletakkan perkara dalam.
Tetapi kini, saya telah mendapat banyak lagi membawa, 10 kuasa 21.
Itu sesuatu yang mudah cukup bahawa kita menyelesaikan segera.
>> Dam, lebih complex-- anda mendapat lapan lapan kapal.
Anda hanya separuh daripada mereka pada bila-bila masa, walaupun.
Anda telah mendapat cawangan yang faktor itu kira-kira 2.8.
Nah, kita telah mendapat pasangan bergerak anda boleh mengambil.
Anda telah mendapat kira-kira 10 hingga 31 daun, lebih besar, dan lebih besar, dan lebih besar ruang.
Kerana saya perlu mencari melalui mereka ruang yang lebih besar dan lebih besar,
itulah apabila perkara seperti alpha-beta dan dapat untuk memotong keseluruhan cawangan
menjadi penting.
>> Sekarang, dam adalah cukup mudah pada 1992.
Satu program komputer yang dipanggil Chinook mengalahkan dam dunia
juara, Marion Tinsley.
Dan sejak itu, tiada Pemain tuan manusia mempunyai
dapat mengalahkan yang terbaik sistem pengiraan.
Jika kita melihat sesuatu seperti catur, kini lagi, kita mempunyai lapan lapan kapal.
Tetapi kita mempunyai lebih kompleks keping, banyak pergerakan yang lebih kompleks.
Kami mempunyai faktor bercabang kira-kira 35, 35 bergerak mungkin secara purata
bahawa saya boleh mengambil, dan keadaan ruang, beberapa daun
yang yang berkembang kepada 10 kuasa 123, nombor besar kemungkinan.
>> Walaupun masih, pemproses moden dapat melakukan ini dengan jayanya.
Pada tahun 1995 dan kemudian pada tahun 1997, komputer program dipanggil Deep Blue dibina oleh IBM
yang berlari pada komputer super gergasi mengalahkan juara dunia semasa,
Garry Kasparov.
Ini adalah satu titik perubahan.
Hari ini, walaupun, bahawa pemprosesan sama kuasa menganggotai MacBook saya.
>> Kelajuan pemprosesan terus mendapat lebih cepat dan lebih cepat.
Kita boleh menilai lebih banyak papan lebih cepat dan lebih cepat.
Tetapi yang lebih penting, kami mempunyai lebih baik fungsi penilaian dan mencantas lebih baik
kaedah.
Oleh itu, kita boleh mencari lebih banyak ruang complexly.
Yang terbesar lembaga permainan yang kita boleh berfikir,
sesuatu seperti Go itulah mendapat 19 sebanyak 19 kapal,
kini tiba-tiba, kami melepasi titik ini di mana sistem pengiraan boleh menang.
Tidak ada pengiraan sistem di luar sana
yang boleh mengalahkan seorang profesional Go pemain.
Sistem terbaik hari ini pangkat ia kira-kira jenis tahap amatur yang baik.
Jadi ada masih agak sedikit keluar sana yang anda tidak boleh mendapatkan lagi.
>> Baiklah, ini permainan papan tradisional,
jenis-jenis sistem di mana kita membina MINIMAX ini, sama ada ia mendapat
alpha-beta atau tidak, algoritma ini bekerja kerana terdapat kekangan tertentu.
Kami mempunyai maklumat yang sempurna tentang dunia.
Kita tahu di mana semua serpihan berada.
Dunia ini statik.
Tiada siapa yang mendapat untuk menggerakkan keping sekitar semasa saya
duduk di sana berfikir, mengambil giliran saya.
Ada satu ruang tindakan itu diskret.
Saya boleh meletakkan pajak gadai saya di sini, atau saya boleh meletakkan pajak gadai saya di sini.
Saya tidak dibenarkan untuk meletakkan pajak gadai saya pada garis di antara kedua-dua kuasa dua.
>> Dan akhirnya, tindakan adalah berketentuan.
Saya tahu bahawa jika saya katakan, tir kuda tiga,
rook saya akan berakhir di kuda tiga, selagi ia adalah langkah yang sah.
Tidak ada ketidakpastian tentang itu.
Sekarang, seperti yang saya pergi ke lebih pelbagai jenis permainan,
kita perlu memecahkan andaian.
>> Bagaimana jika saya pergi ke sesuatu seperti permainan video klasik?
Berikut adalah pilihan video permainan dari Atari 2600.
Apa yang perlu saya di sana?
Saya telah mendapat Frogger, Angkasa Invaders, Kesilapan dan Pac-Man.
Apakah jenis persekitaran saya ada di sini sekarang?
Yang manakah andaian ini adakah saya perlu untuk memecahkan?
>> Nah, ia bergantung kepada permainan.
Saya boleh bermain catur pada 2600, dan ia akan menjadi seperti yang sebelum ini.
Bagi kebanyakan sistem-sistem ini, ada pengetahuan yang lengkap tentang dunia.
Ada benar-benar tindakan berketentuan.
Tetapi biasanya, dunia ini tidak lagi statik.
Iaitu, semasa saya duduk di sana menunggu, ada sesuatu yang bergerak.
Hantu yang datang untuk mendapatkan saya.
Kala jengking mengikuti saya di bawahnya.
Penceroboh angkasa datang lebih dekat dan lebih dekat.
Sejauh yang boleh kita lakukan terhadap mereka ini?
>> Beberapa tahun yang lalu, Google telah projek yang dikenali sebagai
DeepMind, di mana mereka dilatih komputer program untuk bermain Atari 2600 permainan.
Dan jika anda rasa ini tidak serius perniagaan, hasil kajian mereka
telah diterbitkan dalam Nature, jadi hanya kira-kira sebagai baik penerbitan
kerana anda mungkin boleh mendapatkan.
Dan di sini adalah bagaimana mereka dilakukan.
>> Mereka mempunyai algoritma yang duduk dan melihat hanya input skrin.
Ia mendapat sebarang arahan apa jua pun mengenai peraturan permainan.
Dan ia sepatutnya memikirkan, berdasarkan skor, yang bagaimana ia lakukan.
Ini adalah satu sistem yang digunakan sesuatu dipanggil pengukuhan pembelajaran.
Iaitu, ia melihat skor.
Dan jika ia mendapat skor yang baik, ia berkata, Saya harus ingat perkara-perkara.
Dan saya perlu melakukan perkara-lagi.
Dan jika ia mendapat nilai buruk, ia berkata, Saya tidak boleh berbuat apa lagi.
>> Ini adalah prestasi daripada sistem-sistem yang terlatih
dibenarkan bermain untuk beberapa jam pada setiap permainan,
dibandingkan dengan pemain profesional.
Jadi bagi semua permainan yang ke sebelah kiri baris ini,
ini program komputer sendiri terlatih mengatasi pemain profesional.
Dan bagi segala-galanya kepada betul, pemain profesional
masih terbaik.
Untuk sesuatu yang tahu apa-apa tentang kaedah-kaedah, yang
tahu apa-apa struktur permainan, ini adalah prestasi yang mengagumkan.
Dan ini adalah apa yang kita mampu lakukan hari ini.
>> OK, anda katakan, tetapi jika kita berfikir tentang AI dalam permainan,
biasanya kita berfikir tentang perkara yang kita boleh sebenarnya
duduk dan bermain menentang.
Jika saya duduk dan saya bermain StarCraft, atau saya bermain Percuma Ayak,
lawan komputer adalah orang yang mengawal Zerg,
atau mengawal tamadun yang lain.
Bagaimana mereka pemain benar-benar mencari bergerak mereka?
>> Nah, permainan ini distrukturkan banyak cara yang sama seperti permainan papan kami,
permainan ini yang kita akan secara kolektif memanggil empat X permainan,
meneroka, expand-- lupa yang.
Apakah mereka?
Meneroka, berkembang, dan padamkan api, Saya fikir adalah yang terakhir.
Tetapi mereka pada dasarnya penerokaan dan menakluk permainan.
Biasanya, lawan komputer ada mempunyai maklumat yang terhad.
Mereka tidak tahu apa yang berlaku di sebalik kabus perang.
Mereka tidak dapat melihat apa yang anda ada dalam inventori anda.
>> Ada satu persekitaran yang dinamik.
Semuanya berubah sepanjang masa.
Anda tidak mendapat untuk duduk dan menunggu untuk mengambil langkah anda.
Tetapi kebanyakan perkara-perkara yang masih diskret.
Saya perlu meletakkan bandar saya di sini.
Atau saya perlu meletakkan bandar saya di sini.
Dan segala-galanya adalah berketentuan.
Apabila saya katakan, menggerakkan unit saya di sini, unit saya bergerak di sini, melainkan jika halangan tiba-tiba
mula bermain.
Sekarang, itu bukan semua komputer permainan yang di luar sana hari ini.
>> Jika saya pergi dan saya bermain jenis orang pertama permainan, sesuatu seperti pencuri atau Fallout
atau Skyrim, atau Halo, kini Saya mempunyai lawan komputer
yang di luar sana yang mempunyai keadaan yang sangat berbeza.
Mereka mempunyai, sekali lagi, maklumat yang terhad.
Mereka hanya boleh melihat bidang tertentu pandangan.
Keadaan masih dinamik.
Keadaan berubah sepanjang masa.
>> Tetapi sekarang saya mempunyai lebih ruang tindakan yang berterusan.
Saya boleh hanya mengintip yang sedikit sedikit keluar dari pintu.
Dan beberapa permainan, saya tindakan-tindakan yang stokastik.
Saya dapat cuba untuk melompat ke atas dinding itu, tetapi saya telah mendapat peluang untuk gagal.
Jenis-jenis permainan semakin hampir dan lebih dekat kepada jenis pengawal
yang kita membina dalam robotik.
>> Dalam robotik, kita perlu menganggap yang kita ada maklumat yang terhad.
Kami mempunyai sensor yang memberitahu kita tentang dunia.
Kami mempunyai yang sentiasa berubah-ubah, persekitaran yang dinamik.
Kami mempunyai sebuah dunia di mana ruang adalah berterusan, dan bukan diskret.
Dan tindakan kita, apabila kita cuba mereka mempunyai peluang untuk gagal.
Dan sebenarnya, permainan moden pengawal lawan Halo anda,
atau bagi mereka NPC dalam Skyrim, pada dasarnya menjalankan seni bina robotik kecil.
>> Mereka merasakan dunia.
Mereka membina model di dunia.
Mereka mengira berdasarkan satu set matlamat yang mereka ingin capai.
Mereka merancang tindakan berdasarkan kepada apa yang mereka tahu.
Dan orang-orang yang betul-betul jenis yang sama Sistem yang kami membina dalam robotik.
Jadi seni bina ini, untuk membawa balik ini bersama-sama,
selalunya betul sama.
>> Jadi mari kita lihat jika kita boleh melihat bahawa.
Mari kita kembali kepada kami contoh tic-tac-toe.
Dan saya akan bertanya beberapa saya pasca-dokumen untuk datang dan membantu saya.
Jadi Chen Ming, dan Alessandro, dan Olivier, jika anda semua akan datang.
Dan saya akan memerlukan beberapa sukarelawan
>> OK, saya melihat tangan kanan ke atas terdapat di bahagian tengah.
Izinkan saya mengambil satu lagi, seseorang lagi di belakang yang berkenaan.
Baiklah, di sana.
Naiklah.
Baiklah.
Jadi mari kita mengambil perlindungan yang turun.
Dan jika anda semua akan datang tepat kembali sekitar sini bagi saya, yang hebat.
>> Jadi ini adalah robot yang dipanggil Baxter.
Dan Baxter adalah sebuah robot itu adalah satu platform perdagangan, yang direka
oleh sebuah syarikat bernama Rethink.
Dan robot ini direka untuk pembuatan berskala kecil.
Tetapi hari ini kita akan menggunakannya untuk bermain tic-tac-toe.
Sekarang, robot ini juga sesuatu itulah yang agak unik.
Kerana jika saya berdiri di mana-mana berhampiran automasi kilang standard
sistem, saya akan berada di dalam sangat kubur bahaya yang cedera.
>> Baxter, bagaimanapun, direka untuk menjadi agak selamat untuk berinteraksi dengan.
Oleh itu, saya boleh menolak robot ini.
Dan anda boleh lihat ia sedikit agak fleksibel kerana ia bergerak di sekitar.
Dan saya boleh mengubah semula ia di mana saya mahu ia pergi.
Sekarang dalam sistem robot biasa, kita akan mempunyai satu set sendi sini
yang akan terus bertindak balas kepada arahan kedudukan.
Dan mereka tidak akan semestinya mengambil berat jika mereka bergerak di udara terbuka,
atau jika mereka bergerak melalui tulang rusuk saya.
>> OKAY.
Dan biasanya, jika anda di sini dengan sistem industri,
anda akan pergi ke mana-mana berhampiran.
Akan terdapat kuning pita keselamatan sekelilingnya.
Sistem ini mempunyai reka bentuk sedikit berbeza
untuk menjadi lebih mesra dan lebih mudah untuk orang ramai untuk berinteraksi dengan,
kerana di setiap sendi, ada mata air.
Dan bukannya mengawal kedudukan yang tepat,
kita mengawal jumlah tertentu tork, sejumlah berkuat kuasa,
yang kita ingin menjadi pada musim bunga itu.
Baiklah, jadi biarlah saya mengambil sukarelawan kami di sini.
Hi, apa nama anda?
>> PENONTON: Louis.
>> SPEAKER: Louis.
Gembira jumpa dengan awak.
Dan?
>> PENONTON: Daud.
>> SPEAKER: David.
Gembira Mengenali Anda.
Jika anda semua akan menunggu di sini untuk kali kedua,
Saya akan memberikan anda peluang untuk melakukan ini.
Jadi robot ini, jika anda datang dan jika anda menolak perlahan-lahan di atasnya,
anda akan melihat bahawa ia bergerak sedikit.
Dan jika anda merebut dengan betul di sini di pergelangan tangan sahaja
di atas di mana butang-butang yang, ia kelihatan seperti anda perlu merebut butang,
tetapi merebut tepat di atas ia sebaliknya, anda akan dapat perlahan-lahan memanipulasi ia
melalui ruang.
Louis, anda ingin mencubanya?
Jadi memberikan hanya sedikit tekan untuk memulakan dengan.
Dan kemudian jika anda meletakkan jari anda di sana dan memegang kepadanya,
kerana ia akan bergerak untuk anda kemudian.
Baiklah, anda ingin mencubanya?
Naiklah.
Maka berikanlah ia hanya yang lembut menolak ada untuk bermula.
Anda boleh merasakan bagaimana rasanya.
Dan kemudian jika anda mengambil ia di sana, anda akan dapat untuk bergerak di sekitar.
>> OKAY.
Jadi biasanya, ini jenis robot akan digunakan untuk pengeluaran berskala kecil.
Dan saya akan menggerakkan lengan ini hanya turun dari cara yang sedikit di sini.
Tetapi hari ini, kita akan menggunakan sama tic-tac-toe sistem bermain
berdasarkan MINIMAX yang kita bina sebelum ini.
OKAY?
Jadi, anda semua masing-masing akan bermain satu permainan.
Louis, anda akan menjadi yang terdahulu.
Biar saya pegang di sini untuk kali kedua.
Saya akan mempunyai anda berdiri betul di sini, supaya semua orang boleh melihat anda.
Adakah anda semua ditubuhkan di sini?
>> ROBOT: Selamat datang.
Mari kita bermain tic-tac-toe.
Tidak memahami tanda anda sebelum Saya mengatakan bahawa ia adalah giliran anda.
Saya memulakan permainan.
Ia adalah giliran saya.
SPEAKER: Sekarang, jika anda boleh mengambil salah satu kepingan anda dan pergi ke depan dan meletakkannya.
ROBOT: Ia adalah giliran anda.
[Ketawa]
Ia adalah giliran saya.
[Ketawa]
Ia adalah giliran anda.
SPEAKER: Umat manusia adalah mengharapkan anda di sini, Louis.
>> ROBOT: Ia adalah giliran saya.
>> SPEAKER: Jadi Baxter berjaya disekat di sini.
>> ROBOT: Ia adalah giliran anda.
Ia adalah giliran saya.
Ia adalah giliran anda.
Ia adalah giliran saya.
SPEAKER: Dan kami akan memberitahu Baxter selesai daripada langkah terakhir di sini.
>> [Ketawa]
>> ROBOT: Itu seri.
Saya akan menang lain kali.
>> [Ketawa]
>> SPEAKER: Baiklah, terima kasih sangat banyak, Louis.
Terima kasih.
Anda boleh pergi dengan cara ini.
>> ROBOT: Saya memulakan permainan.
SPEAKER: Jadi biarlah saya menerangkan kepada anda satu lagi sedikit
sedikit sebelum kita rematch kami di sini.
Apa sebenarnya yang sedang berlaku?
Jadi robot mempunyai atas kamera di sini.
Dan ia melihat ke bawah di papan.
Dan ia melihat sama ada ia mendapat O merah atau biru
dan X. putih Sebagai orang-orang mendapatkan diletakkan pada kapal, yang pada dasarnya input yang sama
bahawa kita akan membaca dari struktur data kami dari skrin kami.
Ia berjalan yang sama algoritma MINIMAX menjadi
dapat untuk mencari di mana untuk meletakkan tanda yang baik.
>> Dan kemudian kami memberikan arahan tentang di mana kami ingin tanda untuk diletakkan.
Lengan bergerak keluar.
Ia menggunakan penggenggam vakum untuk memohon beberapa sedutan untuk sekeping kayu,
mengambilnya, bergerak ke kanan tempat, dan kemudian lepaskan sedutan
dan lepaskan.
Baiklah, kita akan untuk memberikan satu pukulan lebih
dengan pemain yang lebih bijak sedikit di sini.
Anda bersedia?
Baiklah, jika anda sedang berdiri sehingga di sini dan memberi a-- berubah cara ini
supaya anda boleh melihat semua orang.
Dan kemudian [didengar].
>> ROBOT: Ia adalah giliran saya.
>> SPEAKER: Baxter akan bermula.
Ia adalah giliran anda.
Ia adalah giliran saya.
Ia adalah giliran anda.
Ia adalah giliran saya.
>> [Ketawa]
>> SPEAKER: [WHISPERING] Hanya Ia boleh pergi ke hadapan dan menang.
ROBOT: Ia adalah giliran anda.
SPEAKER: Itu OK.
>> ROBOT: Ia adalah giliran saya.
>> [Ketawa]
>> Saya menang.
>> [Ketawa]
>> Saya memulakan permainan.
>> SPEAKER: Baiklah, terima kasih banyak.
Baiklah, saya fikir kami mempunyai masa untuk satu lagi yang sangat baik Pemain tic-tac-toe,
seseorang yang boleh meletakkan perkara ini kepada sepadan, yang tahu apa yang mereka lakukan.
>> [Ketawa]
>> Siapa yang akan menjadi juara kami di sini?
Baiklah, rakan-rakan anda menawarkan diri anda.
Itu sudah cukup baik untuk saya.
Beritahu saya nama anda lagi.
PENONTON: Tamir.
SPEAKER: Tamir, baik untuk melihat anda.
Baiklah, sekali lagi, kita akan meletakkan anda sehingga di sini supaya semua orang boleh melihat anda.
Anda di wakil kami dalam perlawanan ini sekarang.
Baxter adalah satu dan oh dan oh.
Atau maaf, salah oh dan satu.
Dan ia terpulang kepada anda di sini.
Baxter akan dapat bergerak dahulu, walaupun.
So.
ROBOT: Ia adalah giliran saya.
>> [Ketawa]
>> Ia adalah giliran anda.
Ia adalah giliran saya.
Ia adalah giliran anda.
Ia adalah giliran saya.
Ia adalah giliran anda.
>> [Ketawa]
ROBOT: Ia adalah giliran saya.
SPEAKER: Ia lebih sukar apabila anda berdiri di sini, orang.
[Ketawa]
ROBOT: Anda manusia begitu mudah untuk ditewaskan.
[Ketawa dan tepukan]
SPEAKER: Terima kasih sangat banyak.
ROBOT: Saya menang.
Saya memulakan permainan.
>> SPEAKER: Baiklah, jadi terima kasih sangat banyak untuk Olivier, dan Alessandro,
dan Chen Ming.
>> [Tepuk tangan]
>> Saya mahu membuat satu ketika lalu.
Jadi Baxter sekurang- berakhir di situ, ditipu.
Dan itu adalah di luar jangkaan.
Salah satu yang hebat perkara tentang AI adalah kita yang
bekerja dalam AI supaya kita boleh membina benar-benar menarik dan bijak
peranti.
Tetapi kita juga melakukan kerja-kerja dalam AI kerana ia memberitahu kita sesuatu
tentang bagaimana manusia adalah bijak.
>> Salah satu kegemaran kajian dari makmal saya ialah
melihat apa yang berlaku apabila Mesin tidak disangka-sangka menipu.
Kami melakukan ini asalnya tidak dengan Baxter bermain tic-tac-toe,
tetapi dengan robot yang lebih kecil yang dinamakan Nao, yang bermain batu-kertas-gunting.
Dan kadang-kadang selepas bermain banyak dan banyak
batu-kertas-gunting permainan membosankan, robot akan membuang isyarat,
kehilangan, dan kemudian tiba-tiba menukar isyarat dan berkata, saya menang.
>> [Ketawa]
>> Sekarang, kadang-kadang kita juga akan mempunyai robot, hanya sebagai kawalan, membuang isyarat,
menang, dan menukarkan isyarat yang kehilangan, membuang perlawanan,
menipu untuk kalah.
Dan itu adalah tidak hampir yang menarik.
Robot yang menipu untuk memenangi orang
bertindak balas terhadap seolah-olah ia adalah keluar untuk mendapatkan mereka, seperti ia
secara aktif mencari kebinasaan mereka.
>> [Ketawa]
>> Ia menjadi ejen.
Ia seperti seseorang.
Ia mempunyai kepercayaan dan niat.
Dan ia bukan niat yang baik.
Dan robot yang melemparkan permainan hanya berfungsi.
Ia hanya satu peranti patah.
Biar saya tunjukkan kepada anda beberapa contoh itu daripada beberapa peserta kami.
Jadi di sini adalah penipuan untuk kehilangan.
>> [VIDEO MAIN SEMULA]
- [Didengar] menang.
Jom main.
>> -Tunggu apa?
>> - [Didengar] menang.
Jom main.
>> [Didengar] menang.
Jom main.
>> SPEAKER: Dan di sini adalah menipu untuk menang.
>> -Ya, Saya menang.
Jom main.
>> -Anda Tidak boleh berbuat demikian.
>> [Ketawa]
>> -Ya, Saya menang.
-Anda Ditipu.
Anda ditipu sekarang.
>> -Ya, Saya menang.
>> Hey, anda penipu.
Anda menipu, menipu super.
>> [AKHIR MAIN SEMULA]
>> SPEAKER: Ini berbeza reaksi cepat
mengubah persepsi kita tentang peranti.
Adakah ini bermakna bahawa kita sengaja membina
mesin yang menipu kerana itulah kejuruteraan yang terbaik yang boleh kita lakukan?
Tidak, tetapi ia memberitahu kita sesuatu benar-benar menarik tentang orang.
Itu perkara yang menipu anda dan mencuri kemenangan anda, itu
sesuatu yang masih hidup, itu bernyawa, yang keluar untuk mendapatkan anda.
Ia mempunyai keadaan mental.
Ia mempunyai kepercayaan.
Ia mempunyai niat.
>> Itu perkara yang tangan yang permainan untuk anda, yang tidak.
Itu hanya tidak berfungsi.
Ini adalah dalam pelbagai cara mengapa ia mudah untuk membuang permainan dengan anak-anak.
Tetapi jika anda cuba untuk menipu mereka dan jenis menuntut kemenangan
apabila, anda tahu, hanya untuk memendekkan permainan, mereka akan menangkap anda segera.
Ini jenis kesan yang kita lihat yang keluar dari AI,
mereka mengajar kita banyak perkara mengenai diri kita sendiri.
>> Baiklah, itu sahaja untuk hari ini.
Terima kasih banyak kepada Daud, pasukan pengeluaran Harvard
untuk turun.
>> [Tepuk tangan]
>> Kami akan melihat anda untuk kuiz satu, dan kemudian untuk satu kuliah lepas.
Mempunyai hari yang hebat.
>> [Tepuk tangan]
>> [Bermain muzik]
DAVID MALAN J: Sebenarnya, kita mungkin perlu untuk memperkenalkan beberapa jenis penyulitan,
bukan?
Kerana itu pengepala ini permintaan HTTP akan
hancur supaya sesiapa sahaja cuba untuk menghidu trafik anda
tidak akan benar-benar dapat melihat mereka.
Jadi apa penyelesaian untuk masalah ini?
Nah, kita perlu benar-benar memperkenalkan penyulitan ke dalam formula,
sehingga ketika orang itu ialah penghantaran data dari A ke B,
kita boleh selamat send--
>> [Ketawa]
>> Maklumat dalam cara bahawa musuh tidak boleh, sebenarnya, melihatnya.