>> [MUSIC PLAYING]
>> SPEAKER: Selamat datang kembali, semua orang.
Ini adalah CS50.
Dan hari ini, kami memiliki banyak hal yang menarik untuk dibicarakan.
Pertama, meskipun, saya harus mengingatkan Anda dari hal-hal administratif beberapa.
Minggu ini adalah kuis satu, Rabu atau untuk bagian Yale
pada hari Selasa dan Kamis, Kamis.
Tersedia ulasan kuis malam ini di Yale, 5:30-07:00.
Di Harvard, mereka merekam satu kemarin.
Dan semua orang bisa menonton online itu.
>> Juga, minggu ini atau awal minggu depan, kita harus kuliah CS50 terakhir kami.
[Erangan] saya tahu.
Itu datang begitu cepat.
Siswa Yale akan memiliki hidup kuliah di sini di sekolah hukum
auditorium Jumat.
Akan ada kue.
Siswa Harvard akan memiliki kuliah terakhir di Sanders, Senin.
Juga akan ada kue.
>> Juga, pekan ini Jumat, bagi mereka Anda yang datang ke New Haven,
kita memiliki Expo CS50.
Kami memiliki lebih dari 30 kelompok yang berbeda terdaftar
menunjukkan segalanya dari perahu layar otonom,
untuk sistem yang mengakui potret digital, ke komputer
musik dan musik-diproduksi komputer.
Jadi silahkan bergabung dengan kami.
Saya pikir itu akan menjadi waktu yang tepat.
>> Hari ini, meskipun, kita bisa terus berbicara tentang AI,
tentang kecerdasan buatan.
Dan salah satu hal yang kita akan sampai ke hari ini
adalah ide tentang bagaimana untuk menggunakan AI untuk memecahkan masalah.
Sekarang, seperti biasa, mari kita mulai dengan sesuatu yang sederhana.
Dan kita akan mulai dengan ide sederhana.
Dan itu menggunakan pencarian.
>> Jadi bayangkan sebentar bahwa saya memiliki tugas yang saya butuhkan untuk melakukan.
Dan saya ingin memiliki tugas yang otomatis oleh beberapa agen software.
Bayangkan bahwa saya sedang mencoba untuk memesan satu set dari penerbangan dari, katakanlah, Boston
ke San Francisco.
Aku bisa pergi melalui dan saya bisa menggunakan salah satu pencarian online indah
alat, yang akan melakukan pada dasarnya proses yang sama bahwa kita
akan berjalan melalui hari ini.
Tapi jika Anda tidak memiliki itu alat, apa yang akan Anda lakukan?
>> Nah, Anda bisa melihat dan melihat dan berkata, aku di Boston.
Penerbangan apa yang tersedia untuk saya?
Sekarang, mungkin aku memiliki tiga mungkin penerbangan dari Boston
yang sesuai waktu ketika saya harus meninggalkan.
Aku bisa terbang ke Chicago.
Atau aku bisa terbang ke Miami.
Atau aku bisa terbang ke New York.
Saya kemudian bisa melihat dari masing-masing salah satu kota tujuan
dan berpikir tentang apa lokasi Saya mungkin bisa mencapai
dari masing-masing kota individual.
>> Jadi mungkin dari Chicago, saya bisa mendapatkan penerbangan langsung ke San Francisco.
Itu sangat baik.
Atau aku bisa mendapatkan penerbangan ke Denver.
Sekarang, mungkin bahwa penerbangan ke San Francisco adalah solusi sempurna bagi saya,
tapi mungkin tidak.
Mungkin aku sedang mencari sesuatu itu sedikit lebih murah
atau sedikit lebih baik untuk jadwal saya.
Dan jadi saya bisa melihat apa yang lainnya kemungkinan mungkin di luar sana.
Jadi saya bisa melihat Denver.
Dan dari Denver, well, mungkin Saya bisa mendapatkan penerbangan ke Austin.
Dan dari Austin, mungkin aku bisa mendapatkan penerbangan ke Phoenix, dan dari Phoenix
ke San Francisco.
Sekarang, aku belum selesai.
Karena mungkin ada penerbangan langsung dari New York
ke San Francisco yang sempurna bagi saya.
Atau mungkin ada penerbangan dari Miami melalui Denver yang jauh lebih murah.
Jadi saya masih harus pergi.
Dan saya masih harus melihat semua orang kota-kota yang saya belum diselidiki belum.
Saya harus mendalam memeriksa semua kemungkinan bahwa saya mungkin memiliki.
>> Jadi dari New York, mungkin saya bisa mendapatkan penerbangan ke Nashville, dan dari Nashville
ke Austin.
Dan kemudian saya tahu keberadaan saya.
Dan kemudian saya tahu dari Austin, aku bisa terbang ke Phoenix, dan dari Phoenix
ke San Francisco.
Jika aku terbang pertama ke Miami, meskipun, mungkin aku bisa mendapatkan penerbangan dari Miami
ke Nashville, atau dari Miami ke Austin.
>> Dan sekarang saya sudah mencoba semua dari kemungkinan.
Saya telah membangun grafik ini yang menunjukkan saya semua kemungkinan rute
bahwa saya mungkin bisa mengambil.
Ketika kami mewakili ini macam masalah,
kami tidak akan mewakili mereka secara eksplisit sebagai grafik ini,
karena grafik yang tidak mewakili sejarah di mana kita sudah.
Mengetahui bahwa saya terbang dari Phoenix ke San Francisco
tidak memberitahu saya apakah saya datang melalui Nashville, atau melalui Denver, atau melalui Miami.
>> Jadi apa yang akan saya lakukan sebagai gantinya adalah Aku akan mengambil masalah yang sama,
dan aku akan mewakili sebagai pohon.
Dan pada akar pohon, di atas, saya akan menempatkan tempat yang saya mulai,
Boston.
Dan dari Boston, saya akan melihat semua lokasi yang mungkin
bahwa saya dapat melakukan perjalanan ke.
Nah, dalam hal ini, aku punya tiga, Chicago, New York, dan Miami.
Dan kemudian aku akan mengeksplorasi masing-masing anak-anak ini di pohon.
>> Dari Chicago, saya melihat bahwa aku punya dua penerbangan.
Aku bisa terbang langsung ke San Francisco atau ke Denver.
Sekarang San Francisco, itulah tujuan saya.
Itu tujuan saya.
Itu akan menjadi daun pohon ini.
Artinya, aku tidak akan pergi suatu tempat setelah San Francisco.
Dari Denver, meskipun, Aku bisa terbang dari Denver
ke Austin, dari Austin ke Phoenix, dan dari Phoenix ke San Francisco.
Dan sekarang lagi, saya telah mencapai daun.
>> Saya kemudian bisa kembali ke yang berikutnya kota yang aku belum sepenuhnya dieksplorasi.
Itu akan menjadi New York, pergi kembali ke atas pohon saya,
datang ke New York.
Dari New York, saya bisa terbang ke Nashville, dari Nashville ke Austin,
dari Austin ke Phoenix, dan dari Phoenix ke San Francisco.
Dan akhirnya, salah satu kota saya belum melihat belum, Miami.
>> Nah, dari Miami aku bilang aku punya dua kemungkinan, Nashville atau Austin.
Jika saya terbang ke Nashville, baik maka aku terbang dari Nashville, ke Austin, ke Phoenix,
ke San Francisco.
Jika saya terbang ke Austin, aku terbang Austin, untuk Phoenix, ke San Francisco.
Dan sekarang saya memiliki pohon.
Ini adalah pohon lengkap.
Ini semua kemungkinan dan semua jalan yang aku bisa mengambil.
Artinya, jika saya mulai di akar pohon di atas
dan saya pergi ke salah satu daun, ia memberitahu saya tidak hanya
di mana aku akan berakhir, San Francisco,
tapi ia memberitahu saya bahwa rute Saya perlu mengambil untuk sampai ke sana.
>> Sekarang, yang satu ini adalah yang terbaik?
Nah, apa-apa tentang ini Masalah belum memberitahu saya
mana yang merupakan solusi terbaik.
Mungkin aku peduli paling tentang berapa banyak waktu saya di udara,
atau jarak yang aku terbang.
Dalam hal ini, Chicago ke San Francisco mungkin jumlah terpendek
mil di udara.
>> Mungkin aku peduli tentang biaya.
Dan kita semua tahu penerbangan langsung biasanya lebih mahal.
Jadi mungkin jika saya mengambil ini jenis rute mundur
melalui Miami, Nashville, Austin, Phoenix, mungkin kemudian
Saya mendapatkan harga yang lebih rendah.
Tapi aku bisa mengoptimalkan pada setiap kriteria yang saya peduli.
Siapa yang punya yang terbaik di penerbangan Wi-Fi, atau yang
bandara memiliki makanan terbaik yang tersedia.
Dan masing-masing mungkin memberikan solusi yang berbeda
yang saya lihat sebagai yang terbaik.
>> Jenis-jenis masalah, di mana kita akan
untuk membangun pohon ini kemungkinan, dan kemudian
melihat masing-masing jalur individu, dan memeriksa
mana yang memenuhi kriteria bagi kita,
kita akan memanggil masalah-masalah pencarian.
Dan kami memiliki banyak algoritma, beberapa di antaranya
kita lihat sudah, pergi dan mengeksplorasi pohon-pohon.
Kita bisa melakukannya dengan cara yang saya hanya melakukan, pencarian depth-first,
turun sejauh yang kami bisa sampai kita memukul daun, dan kemudian datang kembali,
dan akan segera kembali ke bawah.
Atau kita bisa melakukan apa disebut pencarian breadth-first.
Kita bisa memperluas segalanya di bagian atas, dan kemudian
semuanya satu baris di bawah itu, dan kemudian
semuanya satu baris di bawahnya itu.
Pohon-pohon pencarian merupakan dasar untuk AI.
Tapi mereka tidak cukup mendapatkan benar sepanjang waktu.
Bahkan, dalam banyak kasus bahwa kita benar-benar peduli,
kami ingin membangun sebuah pohon, tapi kami tidak benar-benar
bisa membuat semua keputusan.
>> Ini adalah situasi yang disebut pencarian permusuhan, juga dikenal
bagaimana menulis playing game sistem dan dibayar untuk itu.
Tetapi ini adalah jenis sistem di mana saya
mungkin bisa memilih ketika saya pergi dari Boston, yang kota saya pergi ke depan.
Tapi setelah itu, orang lain mungkin mendapatkan untuk membuat keputusan tentang di mana aku terbang.
Jadi untuk membangun ini jenis struktur, kami
akan harus mengambil sedikit pendekatan yang berbeda untuk itu.
Kami tidak akan dapat hanya mencari melalui pohon
lagi, karena kita tidak salah satu yang memegang kendali
dari masing-masing poin keputusan.
>> Jadi mari kita bayangkan sederhana permainan seperti tic-tac-toe.
Aku bisa mulai dengan papan benar-benar kosong.
Dan di tic-tac-toe, X akan bermain pertama.
Dan jadi saya bisa berpikir tentang semua mungkin langkah yang X bisa membuat.
Dan jika aku yang bermain X, itu hebat.
Saya memiliki sembilan mungkin bergerak bahwa saya dapat membuat.
Aku bisa menempatkan X di salah satu dari sembilan posisi.
>> Dan kemudian dari masing-masing, saya bisa membayangkan apa yang terjadi selanjutnya.
Nah, dalam hal ini, yang lain pemain akan bisa mengambil giliran.
O akan bisa mengambil giliran.
Dan dari masing-masing, ada akan delapan tempat yang berbeda
O yang bisa menempatkan penanda mereka.
>> Katakanlah saya memutuskan bahwa saya akan menempatkan X di tengah.
Yang selalu tampak seperti langkah pembukaan yang baik.
Aku bisa melihat di bawah itu, delapan kemungkinan bergerak yang O membuat.
Sekarang, jika saya bermain X, itu indah.
Saya bisa memilih mana yang saya pergi ke, satu di tengah.
Tapi sekarang O mendapat untuk memilih.
Dan saya tidak memiliki kontrol atas keputusan itu.
>> Tapi dari masing-masing posisi papan mungkin,
ada maka lain set kemungkinan.
Ketika datang untuk menjadi giliran saya lagi, saya akan
bisa memilih dan mengatakan, baik, jika O bergerak ke, baik,
tempat tengah di sebelah kiri, kemudian Saya memiliki satu set kemungkinan
di mana saya bisa mengambil langkah berikutnya.
Dari mereka, saya bisa mempertimbangkan semua kemungkinan di bawah mereka.
Dan kemudian O akan mendapatkan untuk memilih di antara mereka.
>> Dan aku bisa terus membangun ini pohon keluar sampai aku sampai ke titik
di mana baik seseorang memenangkan game-- itu
mendapat dipertimbangkan daun node-- atau papan benar-benar penuh
dan tidak ada yang menang.
Dan itu juga akan menjadi simpul daun.
Itu akan menjadi dasi.
>> Tetapi hal rumit dengan ini jika ini hanya pencarian biasa
masalah, saya akan bisa katakanlah, baik, X harus pergi di sini.
Dan O harus pergi cara di atas sana.
Dan kemudian X harus pergi di sini.
Dan kemudian O harus pergi cara di atas sana.
Dan kemudian X bisa mendapatkan tiga berturut-turut, dan saya menang.
Dan permainan akan berakhir dalam lima langkah, tiga bagi saya,
dua untuk lawan saya.
Tapi aku tidak selalu bisa memilih itu.
>> Jadi sebaliknya, apa yang kita akan harus melakukan
adalah kita akan memiliki memiliki strategi baru.
Dan strategi yang algoritma game-playing sering menggunakan
adalah apa yang disebut minimax.
Ide sentral dari minimax adalah bahwa kita
akan mengambil langkah yang memberikan lawan kami mungkin set terburuk
dari bergerak bahwa mereka dapat membuat.
Itu tidak ada gunanya bagiku untuk memilih langkah mana
Aku mungkin bisa menang setelah itu, karena lawan saya tidak
akan memberi saya kesempatan itu.
Mereka akan memilih beberapa hasil yang mengerikan bagi saya.
Jadi aku akan membuat bergerak yang memaksa lawan saya
untuk melakukan sesuatu yang lebih baik bagi saya.
Baiklah.
Mari kita lihat bagaimana yang bermain keluar.
Jadi, inilah algoritma dalam pseudocode.
Kita akan menghasilkan seluruh pohon permainan.
Kami akan membangun seluruh struktur.
Dan kemudian kita akan pergi melalui.
Dan di bagian paling bawah di masing-masing node terminal, pada setiap daun,
kami akan mengevaluasi bagaimana berharga adalah bahwa saya?
Dan kita akan nilai-hal yang yang baik bagi saya sebagai positif.
Hal-hal yang tidak baik bagi saya akan kurang positif, atau nol,
atau bahkan negatif.
>> Jadi dalam tic-tac-toe, mungkin kemenangan bagi saya adalah baik.
Itu salah satu a.
Dan dasi adalah nol.
Dan sesuatu yang kerugian bagi saya, mungkin itu yang negatif.
Yang penting adalah bahwa lebih baik itu untuk saya, semakin tinggi skor
yang diterimanya.
Dari mereka yang kemungkinan di bawah, maka kita akan menyaring ke atas.
Dan ketika itu kesempatan saya untuk memilih antara satu set alternatif,
Saya akan memilih salah satu yang mendapat skor tertinggi.
>> Dan setiap kali itu saya lawan berubah untuk memilih,
Saya akan berasumsi bahwa mereka akan memilih salah satu dengan nilai terendah.
Dan jika saya melakukan ini semua jalan sampai ke puncak pohon,
Saya akan memilih jalan yang memberikan saya hasil terbaik yang bisa saya dapatkan,
dengan asumsi bahwa lawan saya membuat semua gerakan yang benar.
>> Baiklah, jadi mari kita lihat ini dalam tindakan pertama.
Dan kemudian kita akan benar-benar melihat kode untuk itu.
Jadi bayangkan saya harus pohon besar ini.
Dan sekarang aku tidak bermain tic-tac-toe.
Saya ingin memberikan Anda sesuatu yang sedikit lebih kaya.
Jadi saya punya beberapa permainan di mana ada banyak nilai yang berbeda
bahwa aku bisa memiliki di akhir.
Dan jadi saya membangun pohon lengkap ini.
Dan aku bisa bergerak pertama.
Aku di akar pohon.
>> Dan aku bisa memilih itu-- jadi saya mendapatkan untuk memaksimalkan seluruh simpul pertama.
Dan kemudian lawan saya mendapat untuk pergi.
Dan kemudian saya bisa pergi lagi.
Begitu turun di bagian bawah, saya memiliki satu set kemungkinan bahwa saya dapat memilih dari,
negara terminal yang berbeda dari permainan.
Jika aku turun di bahwa paling kiri pojok,
dan saya melihat bahwa saya punya pilihan antara delapan, tujuh, dan dua,
baik, saya salah satu yang mendapat untuk memilih.
Jadi aku akan memilih yang terbaik dari mereka.
Aku akan memilih delapan.
>> Jadi saya tahu bahwa jika saya pernah turun ke titik itu,
Aku akan bisa mendapatkan delapan poin.
Jika saya berakhir di titik berikutnya lebih, node berikutnya lebih,
sembilan, satu, atau enam, well, aku akan memilih yang terbaik dari mereka.
Saya akan memilih sembilan.
Jika saya memiliki pilihan antara dua, dan empat, dan satu,
Saya akan memilih empat, yang tertinggi.
>> Sekarang, jika saya melihat tingkat di atas itu, lawan saya
adalah salah satu mendapat untuk membuat pilihan itu.
Jadi lawan saya sampai ke memilih, apakah saya ingin memberinya
hal itu akan untuk mendapatkan dia delapan poin,
atau apakah saya memberinya hal itu akan memberinya sembilan poin,
atau hal yang terjadi memberinya empat poin?
Dan lawan saya, menjadi rasional, akan
untuk memilih minimum dari mereka, akan memilih empat.
>> Dan saya bisa melakukan ini melalui seluruh pohon.
Aku bisa pergi ke yang set tengah dari tiga.
Dan aku bisa memilih antara satu, tiga, dan lima.
Dan aku bisa memilih.
Jadi saya memilih lima.
Aku bisa memilih tiga, sembilan, atau dua.
Saya bisa memilih, jadi saya memilih sembilan.
Enam, lima, atau dua, saya memilih.
Saya bisa memilih enam.
Tingkat di atas itu, siapa yang akan dipilih?
Siapa yang mendapat untuk memilih?
Orang lain, lawan saya.
Jadi mereka memilih lima, sembilan, atau enam, yang mana?
>> AUDIENCE: Lima.
>> SPEAKER: Mereka memilih lima.
Mereka bisa memilih minimum.
Dan kemudian yang terakhir, memilih salah satu, dua, atau tiga.
Saya bisa 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.
Dia memberi saya tiga.
Dan akhirnya di puncak pohon, aku bisa memilih lagi.
Dan aku bisa memilih antara empat, lima, atau tiga.
Jadi saya mengambil lima.
>> Jika saya harus mengendalikan segala sesuatu, saya akan mengambil jalan yang mengarah ke 11.
Tapi aku tidak bisa membuat pilihan itu.
Jika saya pergi ke jalan itu.
Lawan saya akan memaksa saya ke pilihan yang mengarah ke tiga.
Jadi yang terbaik yang dapat saya lakukan adalah untuk mengambil cabang tengah,
membuat pilihan itu akhirnya akan membawa saya ke lima poin.
Itulah yang minimax tidak.
>> Baiklah.
Mari kita lihat itu.
Jadi di sini di CS50 IDE adalah sebuah program yang
mengimplementasikan minimax untuk bermain tic-tac-toe.
Kami akan membangun up representasi.
Kita akan memiliki dua opponent-- atau dua pemain, komputer kita
player dan pemain manusia.
Pemain nomor satu akan bermain O. Itu akan menjadi pemain mesin.
Mereka bisa bergerak kedua.
Dan pemain lain, kami pemain manusia, akan X.
>> Dan untuk membuat hidup saya menjadi kecil sederhana, aku akan
label yang negatif player.
Jadi aku hanya dapat berkembang biak oleh satu negatif untuk swap
antara satu pemain dan lainnya.
Baiklah, jadi mari kita lihat apa yang kita benar-benar akan dilakukan.
Kita akan mendefinisikan papan kami.
Ini akan menjadi, baik, kita akan untuk memungkinkan untuk menjadi tiga oleh tiga,
atau kita bahkan dapat bermain lima dengan lima atau tujuh
tujuh tic-tac-toe jika Anda akan seperti, berdasarkan beberapa dimensi D.
>> Dan kita akan memiliki beberapa fungsi helper
yang akan melakukan hal-hal seperti menginisialisasi screen-- atau menyesal,
menginisialisasi variabel kita, menghapus layar, menggambar papan di layar,
salah satu yang memeriksa papan untuk melihat apakah atau tidak
ada pemenang, yang mem-parsing melalui baris perintah,
hanya untuk membantu, yang berbunyi masukan, dan satu fungsi yang disebut minimax.
Dan itulah salah satu kita akan peduli tentang.
Tapi mari kita lihat pertama di utama.
>> Apa yang kita lakukan?
Nah, kita akan mengurai baris perintah kami,
hanya membaca dan melihat apa papan dimensi kita ingin memiliki.
Kami akan menginisialisasi papan kami.
Dan kemudian kita akan memasukkan salah satu lingkaran liar besar, berulang kali
menerima bergerak sampai permainan ini adalah menang, atau tidak ada gerakan kiri.
Setiap kali kita pergi melalui itu lingkaran, kita akan membersihkan layar.
Kami akan menarik papan di layar.
Dan kami sengaja semacam abstrak ini pergi sebagai subrutin,
sehingga kita tidak perlu khawatir terlalu banyak tentang rincian bagaimana mereka terjadi.
>> Anda akan memiliki kode hari ini.
Dan jika Anda ingin melihat melalui dan mencari tahu, Anda dapat melihat mereka semua.
Tapi kita akan menarik papan di layar.
Dan kemudian kami akan memeriksa dan lihat, kita memiliki pemenang?
Apakah seseorang memenangkan pertandingan ini?
Jika mereka memiliki, kami akan mencetak keluar pesan kemenangan.
Dan kami akan mengakhiri permainan.
>> Kami juga akan memeriksa dan melihat apakah ada dasi.
Ini akan mudah untuk melihat apakah ada dasi.
Ini berarti bahwa semua ruang penuh, tapi belum ada pemenang belum.
Kita dapat mendeklarasikan dasi dan dilakukan.
Kemudian meat-- nyata jika itu pemain mesin,
kami akan memungkinkan bahwa mesin pemutar untuk mencari
melalui menggunakan algoritma minimax ini, untuk menemukan langkah terbaik yang dapat dilakukannya.
Dan kemudian kami akan menempatkan bahwa langkah up.
>> Jika tidak, jika itu pemain manusia, kita akan membaca beberapa masukan dari manusia.
Dan kemudian apakah itu manusia pemain atau pemain mesin,
kami akan melakukan beberapa sedikit bit pengecekan error,
pastikan tetap dalam batas-batas dari dimensi sebenarnya dari papan
yang kita miliki, pastikan bahwa ruang yang kosong,
bahwa tidak ada seseorang put sepotong di sana sudah.
Dan kemudian kami hanya akan menempatkan sepotong di papan,
mengubah pemain ke lapisan berikutnya, dan kenaikan berapa banyak bergerak terjadi.
>> Itu loop utama untuk permainan tic-tac-toe kami.
Minimax, kemudian, tepatnya algoritma yang kita sebelumnya.
Satu-satunya penyesuaian yang kami telah membuat sehingga kita
bisa bermain lebih tinggi papan dimensi adalah kita sudah
terus parameter tambahan ini disebut mendalam.
Dan kedalaman hanya mengatakan, jika saya mencari ke bawah melalui pohon yang
dan saya mendapatkan begitu jauh ke bawah melampaui beberapa kedalaman tingkat
bahwa saya hanya tidak ingin untuk pergi lebih jauh,
Aku akan berhenti dan hanya mengevaluasi dewan pada saat itu.
Aku akan memeriksa dan melihat apakah ada pemenang.
Jika ada pemenang, saya kembali mereka.
Jika tidak, saya akan pergi melalui loop.
Dan aku akan mengatakan, untuk semua kemungkinan lokasi
bahwa saya mungkin bisa mengambil sebagai langkah saya, saya akan
membangun sebuah papan hipotetis yang termasuk saya pindah di papan itu,
dan kemudian secara rekursif memanggil minimax.
>> Jika itu saya pindah, saya bisa menemukan salah satu yang mendapat skor terbesar.
Jika itu bergerak lawan saya, kita menemukan salah satu yang punya nilai minimum.
Dan segala sesuatu yang lain hanya pencatatan.
Baiklah, jadi mari kita lihat run ini.
Sebenarnya, mungkin kita bisa mendapatkan beberapa relawan
untuk datang dan bermain tic-tac-toe.
[Tidak terdengar] satu, dan satu lebih, dua, di sana.
Ayo up.
>> Jadi mari kita pergi ke depan dan me-restart ini sepenuhnya.
Jadi, hi.
>> AUDIENCE: Hi.
>> SPEAKER: Siapa nama Anda?
>> AUDIENCE: Gorav.
SPEAKER: Gorav.
>> AUDIENCE: Saya Layla.
>> SPEAKER: Dan Layla, dan Layla, maaf.
Ayo up.
Gorav, kita akan memiliki Anda pergi dulu.
Dan aku akan meminta Anda untuk menjadi tidak sangat baik pemain tic-tac-toe.
OK, jadi semua tekanan off pada Anda.
Mari kita lihat, meskipun, bahwa mesin kami pemain benar-benar bisa melakukan sesuatu yang cerdas.
Jadi pergi ke depan.
Anda akan mengetik di mana koordinat Anda ingin menempatkan X di.
A0, OK, dan mesin telah pergi segera dan menaruh tanda di A1.
>> Masukan O pada papan.
Baiklah, sekarang pergi ke depan.
Kamu mau pergi kemana?
C2.
Mesin pemain kami telah mengambil tengah persegi, diblokir Anda.
Jadi itu baik, hal yang cerdas untuk itu harus dilakukan.
Anda telah diblokir itu.
Itu sangat baik.
Dibutuhkan sudut ada.
>> Dan itu akan memaksa Anda untuk mengambil satu ruang terakhir, B0.
Dan permainan berakhir di dasi.
Tapi itu memainkan wajar pertandingan melawan Anda, bukan?
Baiklah, terima kasih banyak, Gorav.
>> [TEPUK TANGAN]
>> Baiklah, Layla, kita akan up permainan di sini.
>> AUDIENCE: Oh, bagus.
>> SPEAKER: Kami akan memberikan Anda empat oleh empat tic-tac-toe.
Sekarang, dalam empat oleh empat, Anda harus menang dengan empat berturut-turut, tidak tiga berturut-turut.
Dan itu semua milikmu.
Jadi Layla mengambil D1.
Kami sekarang akan mengikuti pemain komputer kami di sini.
Tiga oleh tiga tic-tac-toe adalah jenis yang hal yang mudah bagi kita semua.
Tapi masih bagus untuk melihat pemain komputer membuat langkah cerdas.
Empat oleh empat sampai ke menjadi sedikit rumit.
>> Baik dilakukan.
Baiklah, jadi Layla selesai.
Oh, dan kita harus berakhir di sana.
Tapi mari kita lakukan satu lagi di sini.
Jadi Layla, terima kasih.
Baik dilakukan.
>> [TEPUK TANGAN]
>> Jadi pemain tic-tac-toe kami pergi melalui dan menemukan lokasi,
memecahkan mereka menggunakan minimax ini.
Dan saya memiliki pengaturan kedalaman pada itu sehingga
tidak akan berjalan terlalu cepat, yang mungkin mengapa
Layla bisa pergi baik ke depan seperti yang dia lakukan, dan melakukan dengan sangat baik.
Tapi sistem ini yang baru saja pergi melalui dan kekerasan
pergi lebih dalam, dan lebih dalam, dan lebih dalam, dan terus mencari solusi
yang mereka butuhkan, orang-orang macam sistem cukup sukses di ini, baik,
permainan papan standar.
>> Dan pada kenyataannya, jika kita melihat sebuah tiga oleh tiga tic-tac-toe permainan,
ini pada dasarnya adalah masalah diselesaikan.
Dan ini adalah diagram indah dari Randall Munroe di XKCD,
menunjukkan yang menggerakkan Anda harus mengambil, mengingat bergerak lawan.
Ini adalah sesuatu yang kita bisa mudah menentukan depan waktu.
Tapi apa yang terjadi setelah kami mendapatkan lebih game kompleks, permainan lebih rumit,
di mana ada papan besar, lebih kemungkinan, strategi yang lebih dalam?
>> Ternyata ini brute force mencari masih
tidak cukup baik, kecuali ketika Anda sampai ke titik
di mana pohon yang begitu besar bahwa Anda tidak dapat mewakili semuanya.
Bila Anda tidak dapat menghitung seluruh pohon, ketika Anda tidak bisa pergi ke depan dan mendorong
diri ke titik di mana Anda telah mendapatkan seluruh pohon dalam memori,
atau apakah Anda bisa mendapatkannya dalam memori dan akan hanya
membawa Anda terlalu lama untuk mencari melalui itu, Anda harus melakukan sesuatu yang lebih cerdas.
>> Untuk melakukan itu, Anda harus melakukan dua hal.
Pertama, Anda harus menemukan beberapa cara membatasi kedalaman Anda.
Nah, itu OK.
Kita dapat menemukan beberapa yang bagus, telanjang minimum dan berkata, Anda hanya dapat pergi begitu dalam.
Tetapi ketika Anda melakukannya, itu berarti Anda memiliki papan ini sebagian tidak lengkap.
Dan Anda harus memilih, apakah saya suka papan sebagian tidak lengkap ini,
atau papan sebagian tidak lengkap ini?
>> Dan pada kita empat oleh empat tic-tac-toe permainan,
pemain komputer kita turun ke bawah dan berkata,
Aku punya dua papan yang berbeda.
Satu pun adalah menang.
Satu tidak adalah kerugian.
Satu tidak adalah dasi.
Bagaimana cara memilih antara mereka?
Dan itu tidak memiliki cara cerdas melakukan hal itu.
>> Kita melihat seperti ini Evaluasi terjadi sepanjang waktu
seperti yang kita masuk ke permainan yang lebih kompleks.
Catur adalah contoh yang bagus.
Dalam catur, kita harus, pertama dari semua, papan yang lebih besar.
Kami memiliki jauh lebih potongan.
Dan posisi potongan-potongan ini dan cara yang potongan-potongan ini bergerak
sangat penting.
Jadi jika saya ingin menggunakan minimax, Aku harus mampu menentukan
dan mengatakan, forum ini, di mana tidak ada yang menang atau kalah lagi,
entah bagaimana lebih baik daripada ini lain papan, di mana tidak ada yang menang atau kalah.
>> Untuk melakukan itu, saya mungkin melakukan hal-hal seperti aku mungkin hanya
menghitung berapa banyak potongan yang saya miliki dan berapa banyak buah yang Anda miliki?
Atau aku mungkin memberikan yang berbeda potongan poin yang berbeda.
Queen saya adalah senilai 20 poin.
Gadai Anda bernilai satu poin.
Yang memiliki jumlah poin lebih?
Atau aku mungkin mempertimbangkan hal-hal seperti, yang punya posisi papan yang lebih baik?
Giliran itu berikutnya, apa pun yang saya bisa
jangan untuk mengevaluasi lebih akurat yang kemungkinan ini
lebih baik tanpa mendalam mengingat
setiap langkah yang bisa datang setelah itu.
>> Sekarang untuk membuat pekerjaan itu, salah satu hal yang
akan menjadi sangat penting bagi kita tidak hanya bergerak lurus
ke kedalaman tertentu batas, namun mampu mengatakan,
salah satu ide-ide ini yang saya memiliki begitu buruk bahwa itu
tidak layak dipertimbangkan semua cara yang mungkin
bahwa hal-hal dapat pergi dari buruk menjadi lebih buruk.
Untuk melakukan itu, kita akan menambahkan ke minimax Prinsip yang disebut alph-beta.
Dan alpha-beta mengatakan, jika Anda memiliki ide yang buruk,
jangan buang waktu Anda mencoba untuk mencari tahu seberapa buruk itu.
>> Jadi, inilah yang akan kita lakukan.
Kita akan mengambil yang sama prinsip-prinsip yang kita miliki sebelumnya,
jenis minimax yang sama pencarian, hanya kami
akan melacak, tidak hanya dari nilai yang sebenarnya yang kita miliki, tetapi kita akan
melacak terbaik Nilai yang saya bisa,
dan kemungkinan terburuk hasil aku bisa memiliki.
Dan setiap saat kemungkinan terburuk Hal ini mencari kemungkinan,
Aku akan meninggalkan bagian dari pohon.
Dan aku bahkan tidak akan repot-repot melihat itu lagi.
>> Baiklah, jadi bayangkan bahwa kita mulai dengan pohon permainan ini tepat sama.
Dan sekarang kita akan pergi turun lagi, semua jalan ke bawah
untuk yang pojok kiri bawah.
Dan di bawah yang meninggalkan sudut, kami terlihat dan kami mengevaluasi forum ini.
Mungkin itu adalah empat oleh empat tic-tac-toe papan, atau mungkin papan catur.
Tapi kami melihat itu, dan kami mengevaluasi itu, dan kami mendapatkan nilai delapan.
>> Pada saat itu, kita tahu bahwa kita akan mendapatkan setidaknya
delapan poin dari keputusan bawah ini.
Tidak peduli apa yang lain Keduanya, yang tujuh dan dua.
Mereka bisa menjadi nilai-nilai mereka ingin menjadi.
Kita akan mendapatkan di Setidaknya delapan poin.
Baiklah, tapi kita bisa pergi ke depan dan memeriksa.
Mungkin salah satunya adalah lebih baik daripada delapan.
>> Kami melihat tujuh.
Apakah yang lebih baik dari delapan?
Tidak, itu tidak mengubah pendapat kami sama sekali.
Kita melihat dua.
Apakah yang lebih baik dari delapan?
Tidak, itu tidak mengubah pendapat kami sama sekali.
Jadi sekarang kita tahu bahwa kita telah kehabisan semua kemungkinan ada.
Kami tidak akan mendapatkan sesuatu yang lebih baik dari delapan.
Kita akan mendapatkan persis delapan.
>> Dan jadi kami mengubah simpul itu dan mengatakan, bahwa sekarang adalah kepastian.
Kami naik satu tingkat di atas itu.
Dan sekarang kita tahu sesuatu tentang tingkat minimalisasi.
Kita tahu bahwa kita tidak akan pernah mendapatkan lebih dari delapan poin jika kita turun
arah itu.
Karena bahkan jika mereka dua cabang lainnya berubah
menjadi fantastis dan layak ribuan poin masing-masing,
lawan kami akan memberi kita minimum, dan memberi kita delapan.
Baiklah, baik, mari kita lihat.
Kami akan terus turun jalan itu.
Kami pergi ke yang tengah di sebelah kiri.
Kami melihat ke bawah dan kita melihat ada sembilan.
Kita tahu bahwa kita akan mendapatkan setidaknya sembilan poin dengan turun
bahwa jalan tengah.
Dan pada titik ini, kita hanya bisa berhenti.
Dan kita dapat mengatakan, melihat, saya tahu di tingkat atas,
Aku akan mendapatkan tidak lebih dari delapan menunjukkan dengan turun ke arah ini.
Tetapi jika aku pergi di tengah jalan bukan jalan kiri,
Saya akan mendapatkan setidaknya sembilan poin.
>> Lawan saya tidak pernah akan biarkan aku turun bahwa jalan tengah.
Mereka bisa memilih.
Dan mereka akan memilih jalan ke kiri menuju delapan,
bukan di tengah menuju apa setidaknya sembilan poin.
Jadi pada saat itu, aku akan berhenti.
Dan saya akan mengatakannya, kau tahu apa?
Saya tidak perlu melihat lebih lebih turun ke arah itu.
Karena aku tidak akan pernah sampai ke sana.
>> Saya bisa melewatkan yang satu, dan saya bisa melewatkan enam,
karena itu tidak akan pernah terjadi.
Jadi saya akan pergi dan aku akan mempertimbangkan kemungkinan berikutnya.
Saya pergi ke sana dan saya katakan, saya melihat dua.
Saya tahu jika saya bisa di sini, aku akan mendapatkan setidaknya dua.
OKE.
Aku terus berjalan.
Saya melihat empat.
Aku tahu aku akan mendapatkan setidaknya empat.
Masih banyak di antara empat dan delapan, meskipun.
Jadi aku terus.
Aku melihat ke bawah dan saya melihat ada satu.
Baiklah, saya tahu jika Aku turun jalan ini,
Aku akan dapat memilih empat.
Apa lawan saya lakukan?
Antara sesuatu yang memberi saya delapan, sesuatu yang memberi saya empat,
dan sesuatu yang memberi saya setidaknya sembilan,
baik, dia akan memberi saya empat.
Dan aku tahu sekarang di paling atas, aku akan
untuk bisa mendapatkan setidaknya empat poin dari pertandingan ini.
>> Seluruh ide alpha-beta adalah untuk memotong bagian pohon sehingga
bahwa saya tidak melihat mereka lagi.
Tapi masih terlihat seperti aku sudah melihat banyak pohon.
Mari kita terus turun.
Kami akan pergi ke yang berikutnya sekarang.
Turun di bagian bawah, aku menemukan satu a.
Aku tahu aku akan mendapatkan setidaknya satu.
Aku terus mencari.
>> Saya menemukan tiga.
Aku tahu aku akan mendapatkan setidaknya tiga.
Aku terus berjalan.
Saya menemukan lima.
Aku tahu aku akan mendapatkan lima jika saya turun di jalan itu.
Dan aku juga tahu itu bahwa lawan saya, jika saya
memilih tengah tiga pilihan besar,
dia akan memberi saya sesuatu yang lima atau kurang.
>> OKE.
Aku bisa terus ada.
Aku bisa melihat ke bawah dan aku bisa mengatakan, apa yang akan saya
untuk mendapatkan jika saya pergi ke jalan tengah?
Aku akan mendapatkan, baik, tiga di sana.
Aku akan mendapatkan sesuatu itu setidaknya tiga.
Masih ada hal-hal antara tiga dan lima, jadi aku terus mencari.
Oh, sembilan, aku akan pasti mengambil bahwa selama tiga.
Aku akan mendapatkan setidaknya sembilan jika saya turun bahwa jalan tengah.
>> Sekarang lawan saya berhenti dan berkata, terlihat, tidak ada gunanya lagi.
Saya tahu bahwa saya minimalisasi lawan, dia
akan memberi saya hal itu kurang dari atau sama dengan lima,
bukan hal yang lebih besar dari atau sama dengan sembilan.
Aku berhenti.
Saya tidak melihat lagi pada saat itu.
Aku terus berjalan.
>> Aku melihat ke bawah satu ini.
Turun ke bawah, saya menemukan enam.
Aku tahu aku akan mendapatkan setidaknya enam.
Dan apa yang bisa saya lakukan?
Saya bisa berhenti.
Karena ada pilihan antara sesuatu yang setidaknya enam
dan sesuatu yang kurang dari lima, dia
akan memberikan hal yang yang kurang dari lima.
Dan sekarang aku tahu aku akan untuk mendapatkan persis pilihan itu.
Aku akan mendapatkan lima pilihan.
>> Aku kembali naik ke atas.
Yang akan saya memilih antara sesuatu
yang lebih besar dari atau sama dengan empat, atau sesuatu yang sama dengan lima?
Aku akan mengambil sesuatu itu setidaknya lima.
Aku pergi ke jalan terakhir, semua cara turun ke bawah.
Ada satu a.
OK, setidaknya aku akan mendapatkan satu poin.
Aku terus berjalan.
Dua, oh, itu lebih baik dari satu.
Aku akan mendapatkan setidaknya dua.
Saya menemukan tiga.
Aku tahu aku akan mendapatkan tiga.
>> Dan titik di atas itu, lawan saya akan
untuk memberikan sesuatu yang kurang dari atau sama dengan tiga.
Dan sekarang saya bisa berhenti.
Karena dalam pilihan antara saya menjadi bisa mendapatkan lima dan lawan saya
memberi saya sesuatu yang kurang dari tiga, Saya selalu akan mengambil lima.
Jadi saya tidak menilai bahwa bagian bawah pohon sama sekali.
>> Sekarang, ini mungkin tampak kecil.
Tapi ketika sedikit dari aritmatika, lebih besar dari dan kurang dari,
dapat memotong seluruh bagian dari pohon ini tumbuh secara eksponensial,
yang mengarah ke besar jumlah tabungan, tabungan
yang cukup besar yang saya bisa mulai bermain kompetitif
di game lebih kompleks.
>> Baiklah, jika kita melihat ukuran dan kompleksitas permainan yang berbeda,
tic-tac-toe adalah contoh mudah kami.
Kami punya sebuah papan kecil, tiga oleh tiga.
Kami mendapatkan, paling banyak, rata-rata sekitar empat pilihan yang berbeda
seperti yang kita pergi melalui permainan.
Kami memiliki suatu tempat sekitar 10 ke mungkin daun yang berbeda kelima.
Dan membangun tic-tac-toe pemain, baik, kami hanya melakukannya.
Mudah.
>> Jika kita pergi ke sesuatu yang lebih kompleks, seperti Connect Four.
Apakah Anda ingat game ini di mana Anda drop token kecil di?
Ini adalah enam tujuh papan, tidak jauh lebih besar, masih
memiliki sekitar percabangan yang sama faktor sebagai tic-tac-toe.
Aku punya sekitar empat pilihan di mana saya dapat menempatkan hal-hal dalam.
Tapi sekarang, aku punya lebih banyak mengarah, 10 pangkat 21.
Itu sesuatu yang mudah cukup bahwa kita menyelesaikannya segera.
>> Checkers, lebih complex-- Anda mendapat delapan dengan delapan papan.
Anda hanya berada di setengah dari mereka setiap saat, meskipun.
Anda punya percabangan Faktor itu sekitar 2,8.
Nah, kita punya pasangan bergerak Anda dapat mengambil.
Anda punya sekitar 10 sampai 31 daun, lebih besar, dan lebih besar, dan lebih besar ruang.
Seperti yang saya harus mencari ruang-ruang yang lebih besar dan lebih besar,
saat itulah hal-hal seperti alpha-beta dan mampu memotong seluruh cabang
menjadi penting.
>> Sekarang, catur cukup mudah pada tahun 1992.
Sebuah program komputer yang disebut Chinook mengalahkan catur dunia
juara, Marion Tinsley.
Dan sejak itu, tidak ada Pemain tuan manusia memiliki
mampu mengalahkan yang terbaik sistem komputasi.
Jika kita melihat sesuatu seperti catur, sekarang lagi, kami memiliki delapan dengan delapan papan.
Tapi kita harus jauh lebih kompleks potongan, gerakan jauh lebih kompleks.
Kami memiliki faktor percabangan dari sekitar 35, 35 mungkin bergerak rata-rata
bahwa saya dapat mengambil, dan negara ruang, jumlah daun
yang tumbuh 10 pangkat 123, nomor besar kemungkinan.
>> Bahkan masih, prosesor modern mampu melakukan hal ini berhasil.
Pada tahun 1995 dan kemudian pada tahun 1997, komputer program yang disebut Deep Blue dibangun oleh IBM
yang berlari pada superkomputer raksasa mengalahkan juara dunia saat ini,
Garry Kasparov.
Ini adalah titik balik.
Hari ini, meskipun, bahwa pengolahan yang sama daya duduk di MacBook saya.
>> Kecepatan pemrosesan terus semakin cepat dan lebih cepat.
Kita dapat mengevaluasi lebih dan lebih papan lebih cepat dan lebih cepat.
Tapi yang lebih penting, kita harus lebih baik fungsi evaluasi dan pemangkasan yang lebih baik
metode.
Jadi kita dapat mencari lebih banyak ruang secara kompleks.
Yang terbesar dari papan game yang dapat kita pikirkan,
sesuatu seperti Go yang mendapat 19 oleh 19 dewan,
sekarang tiba-tiba, kami melewati titik di mana sistem komputasi bisa menang.
Tidak ada komputasi sistem di luar sana
yang bisa mengalahkan pemain Go profesional.
Sistem peringkat terbaik hari ini itu tentang semacam tingkat amatir yang baik.
Jadi masih ada cukup sedikit keluar ada yang Anda tidak bisa mendapatkan ke belum.
>> Baiklah, ini permainan papan tradisional,
jenis-jenis sistem di mana kita membangun minimax ini, apakah itu punya
alpha-beta atau tidak, algoritma ini bekerja karena ada kendala tertentu.
Kami memiliki informasi yang sempurna tentang dunia.
Kita tahu di mana semua bagian yang.
Dunia yang statis.
Tak ada yang untuk memindahkan potongan sekitar sementara aku
duduk di sana berpikir, mengambil giliran saya.
Ada ruang tindakan yang diskrit.
Saya dapat menempatkan pion saya di sini, atau saya dapat menempatkan pion saya di sini.
Saya tidak diizinkan untuk menempatkan bidak saya di garis di antara dua kotak.
>> Dan akhirnya, tindakan adalah deterministik.
Saya tahu bahwa jika saya mengatakan, benteng untuk ksatria tiga,
benteng saya akan berakhir di knight tiga, selama itu langkah yang valid.
Tidak ada ketidakpastian tentang itu.
Sekarang, saat aku pergi ke lebih berbagai jenis permainan,
kita harus memecahkan asumsi-asumsi.
>> Bagaimana jika saya pergi ke sesuatu seperti video game klasik?
Berikut pilihan video game dari Atari 2600.
Apa yang harus saya atas sana?
Aku punya Frogger, Ruang Penjajah, Pitfall, dan Pac-Man.
Jenis lingkungan apa apakah saya harus di sini sekarang?
Yang asumsi ini apakah saya harus istirahat?
>> Yah, itu tergantung pada permainan.
Saya bisa bermain catur pada 2600, dan itu akan menjadi seperti itu sebelumnya.
Untuk sebagian besar dari sistem ini, ada pengetahuan yang lengkap tentang dunia.
Ada benar-benar tindakan deterministik.
Tapi biasanya, dunia ini tidak lagi statis.
Artinya, sementara aku duduk di sana menunggu, sesuatu yang bergerak.
Hantu datang untuk mendapatkan saya.
Kalajengking yang mengikuti saya di bawahnya.
Penjajah ruang yang datang lebih dekat dan lebih dekat.
Seberapa baik kita bisa lakukan terhadap ini?
>> Beberapa tahun yang lalu, Google telah proyek yang disebut
DeepMind, di mana mereka dilatih komputer Program memainkan Atari 2600 game.
Dan jika Anda berpikir ini tidak serius bisnis, hasil penelitian mereka
diterbitkan di Nature, sehingga hanya tentang sebaik publikasi
seperti yang Anda mungkin bisa mendapatkan.
Dan inilah seberapa baik mereka tampil.
>> Mereka memiliki algoritma yang duduk dan menyaksikan hanya input layar.
Ini tidak punya petunjuk apapun tentang aturan permainan.
Dan itu seharusnya mengetahui, berdasarkan nilai yang, seberapa baik yang dilakukannya.
Ini adalah sistem yang digunakan sesuatu disebut pembelajaran penguatan.
Artinya, itu tampak pada nilai-nya.
Dan jika itu mendapat skor yang baik, katanya, Aku harus ingat hal-hal.
Dan saya harus melakukan hal-lagi.
Dan jika mendapat nilai buruk, katanya, Saya tidak harus melakukan hal-hal lagi.
>> Ini adalah kinerja dari sistem-sistem yang terlatih
diizinkan untuk bermain untuk beberapa jam pada setiap pertandingan,
dibandingkan dengan gamer profesional.
Jadi untuk semua permainan yang ke sisi kiri baris ini,
program komputer self-terlatih ini mengungguli gamer profesional.
Dan untuk semuanya ke kanan, gamer profesional
masih yang terbaik.
Untuk sesuatu yang tahu apa-apa tentang aturan, yang
tahu apa-apa tentang struktur permainan, ini adalah kinerja yang mengesankan.
Dan ini adalah apa yang kita mampu lakukan hari ini.
>> OK, Anda katakan, tapi jika kita berpikir tentang AI di game,
biasanya kita berpikir tentang hal-hal yang kita dapat benar-benar
duduk dan bermain melawan.
Jika saya duduk dan saya bermain StarCraft, atau saya bermain gratis Saringan,
lawan komputer adalah orang mengendalikan Zerg,
atau mengendalikan peradaban lainnya.
Bagaimana para pemain benar-benar menemukan gerakan mereka?
>> Nah, game ini terstruktur banyak cara yang sama seperti papan permainan kami,
game ini yang kita akan kolektif memanggil empat pertandingan X,
mengeksplorasi, expand-- lupa yang.
Apakah mereka?
Jelajahi, memperluas, dan memadamkan, Saya pikir adalah yang terakhir.
Tapi mereka pada dasarnya eksplorasi dan menaklukkan game.
Biasanya, lawan komputer ada memiliki informasi yang terbatas.
Mereka tidak tahu persis apa yang terjadi di balik kabut perang.
Mereka tidak bisa melihat apa yang Anda memiliki dalam persediaan Anda.
>> Ada lingkungan yang dinamis.
Semuanya berubah sepanjang waktu.
Anda tidak bisa duduk dan menunggu untuk mengambil langkah Anda.
Tapi kebanyakan hal masih diskrit.
Saya harus meletakkan kota saya di sini.
Atau aku harus meletakkan kota saya di sini.
Dan semuanya deterministik.
Ketika saya mengatakan, memindahkan unit saya di sini, unit saya bergerak di sini, kecuali hambatan tiba-tiba
datang ke dalam bermain.
Sekarang, itu tidak semua komputer permainan yang di luar sana hari ini.
>> Jika saya pergi dan saya bermain tipe orang pertama permainan, sesuatu seperti Thief atau Fallout
atau Skyrim, atau Halo, sekarang Saya memiliki lawan komputer
yang di luar sana yang memiliki situasi yang sangat berbeda.
Mereka memiliki, lagi, informasi yang terbatas.
Mereka hanya bisa melihat bidang tertentu pandang.
Lingkungan masih dinamis.
Hal-hal yang berubah sepanjang waktu.
>> Tapi sekarang aku punya lebih banyak ruang tindakan terus menerus.
Aku bisa saja mengintip sebuah sedikit keluar dari pintu.
Dan beberapa permainan, saya tindakan yang stokastik.
Aku bisa mencoba untuk melompati dinding itu, tapi aku punya kesempatan gagal.
Jenis permainan semakin dekat dan lebih dekat ke jenis kontroler
yang kita bangun di robotika.
>> Dalam robotika, kita harus mengasumsikan bahwa kita memiliki informasi terbatas.
Kami memiliki sensor yang memberitahu kita tentang dunia.
Kami memiliki selalu berubah, lingkungan yang dinamis.
Kami memiliki sebuah dunia di mana ruang terus menerus, bukan diskrit.
Dan tindakan kita, ketika kita mencoba mereka, memiliki kesempatan gagal.
Dan pada kenyataannya, permainan modern controller untuk lawan Halo Anda,
atau bagi mereka NPC di Skyrim, pada dasarnya menjalankan arsitektur robotika kecil.
>> Mereka merasakan dunia.
Mereka membangun sebuah model dunia.
Mereka menghitung berdasarkan pada satu set tujuan yang mereka ingin capai.
Mereka berencana tindakan berdasarkan pada apa yang mereka ketahui.
Dan mereka adalah persis jenis yang sama sistem yang kita bangun dalam robotika.
Jadi arsitektur ini, untuk membawa kembali ini bersama-sama,
seringkali cukup sama.
>> Jadi mari kita lihat apakah kita dapat melihat bahwa.
Mari kita kembali ke kami tic-tac-toe contoh.
Dan aku akan meminta beberapa saya post-docs untuk datang dan membantu saya.
Jadi Chen Ming, dan Alessandro, dan Olivier, jika kalian akan datang.
Dan aku akan membutuhkan beberapa relawan
>> OK, saya melihat tangan dengan benar ada di tengah.
Biarkan aku mengambil satu lagi, seseorang lanjut di belakang mungkin.
Baiklah, di sana.
Ayo up.
Baiklah.
Jadi mari kita berlindung yang turun.
Dan jika kalian akan datang tepat kembali di sini bagi saya, fantastis.
>> Jadi ini adalah sebuah robot yang disebut Baxter.
Dan Baxter adalah robot itu adalah Platform komersial, dirancang
oleh sebuah perusahaan bernama Rethink.
Dan robot ini dirancang untuk manufaktur skala kecil.
Tapi hari ini kita akan menggunakannya untuk bermain tic-tac-toe.
Sekarang, robot ini juga sesuatu yang relatif unik.
Karena jika saya berdiri di mana saja dekat dengan otomatisasi pabrik standar
sistem, saya akan sangat serius di bahaya terluka.
>> Baxter, bagaimanapun, dirancang untuk menjadi relatif aman untuk berinteraksi dengan.
Dan jadi saya bisa mendorong pada robot ini.
Dan Anda dapat melihat itu sedikit bit fleksibel ketika bergerak di sekitar.
Dan saya dapat reposisi itu di mana saya ingin untuk pergi.
Sekarang dalam sistem robot normal, kita akan memiliki satu set sendi sini
yang akan langsung merespon perintah posisi.
Dan mereka tidak akan selalu peduli jika mereka bergerak melalui udara terbuka,
atau jika mereka bergerak melalui tulang rusuk saya.
>> OKE.
Dan biasanya, jika Anda di sini dengan sistem industri,
Anda akan ke mana-mana dekat itu.
Akan ada kuning pita pengaman di sekitar itu.
Sistem ini memiliki desain yang sedikit berbeda
menjadi ramah dan lebih mudah bagi orang-orang untuk berinteraksi dengan,
di bahwa di setiap sendi, ada mata air.
Dan bukannya mengendalikan posisi yang tepat,
kita mengendalikan sejumlah torsi, sejumlah kekuatan,
bahwa kami ingin berada di musim semi itu.
Baiklah, jadi biar mengambil relawan kami di sini.
Hai siapa namamu?
>> AUDIENCE: Louis.
>> SPEAKER: Louis.
Senang bertemu Anda.
Dan?
>> AUDIENCE: David.
>> SPEAKER: David.
Senang berjumpa dengan mu.
Jika kalian akan menunggu di sini untuk kedua,
Aku akan memberikan Anda kesempatan untuk melakukan hal ini.
Jadi robot ini, jika Anda datang dan jika Anda mendorong lembut di atasnya,
Anda akan melihat bahwa bergerak sedikit.
Dan jika Anda ambil benar di sini di pergelangan tangan hanya
di atas di mana tombol-tombol yang, itu Sepertinya Anda harus mengambil tombol,
tapi ambil tepat di atas itu sebagai gantinya, Anda akan dapat sangat lembut memanipulasi
melalui ruang.
Louis, Anda ingin mencobanya?
Jadi memberikan hanya sedikit mendorong untuk memulai dengan.
Dan kemudian jika Anda menempatkan jari Anda di sana dan terus ke itu,
karena akan bergerak untuk Anda kemudian.
Baiklah, Anda ingin mencobanya?
Ayo up.
Jadi memberikan hanya lembut mendorong ada untuk memulai.
Anda bisa merasakan seperti apa rasanya.
Dan kemudian jika Anda ambil di sana, Anda akan dapat melakukan manuver di sekitar.
>> OKE.
Jadi biasanya, jenis ini robot akan digunakan untuk pembuatan skala kecil.
Dan aku akan menggerakkan lengan ini hanya turun dari jalan sedikit di sini.
Tapi hari ini, kita akan menggunakan Sistem bermain tic-tac-toe yang sama
berdasarkan minimax yang kita dibangun sebelumnya.
OKE?
Jadi, kalian masing-masing akan memainkan game.
Louis, Anda akan menjadi yang pertama.
Biarkan aku hanya terus di sini untuk kedua.
Aku akan memiliki Anda berdiri tepat di sini, hanya sehingga semua orang dapat melihat Anda.
Apakah kalian mengatur di sini?
>> ROBOT: Selamat Datang.
Mari kita bermain tic-tac-toe.
Jangan pegang token Anda sebelum Saya mengatakan bahwa itu adalah giliran Anda.
Saya memulai permainan.
Ini adalah giliran saya.
SPEAKER: Sekarang, jika Anda bisa mengambil salah satu dari potongan dan pergi ke depan dan tempatkan.
ROBOT: Ini adalah giliran Anda.
[TAWA]
Ini adalah giliran saya.
[TAWA]
Giliran Anda.
SPEAKER: Umat manusia adalah mengandalkan Anda di sini, Louis.
>> ROBOT: Ini adalah giliran saya.
>> SPEAKER: Jadi Baxter berhasil diblok di sini.
>> ROBOT: Ini adalah giliran Anda.
Ini adalah giliran saya.
Giliran Anda.
Ini adalah giliran saya.
SPEAKER: Dan kami akan membiarkan Baxter menyelesaikan keluar bergerak terakhirnya di sini.
>> [TAWA]
>> ROBOT: Itu dasi.
Saya akan menang kali.
>> [TAWA]
>> SPEAKER: Baiklah, terima kasih banyak, Louis.
Terima kasih.
Anda dapat pergi dengan cara ini.
>> ROBOT: Saya memulai permainan.
SPEAKER: Jadi mari saya jelaskan Anda satu lagi sedikit
bit sebelum kita mendapatkan pertandingan ulang kami di sini.
Apa sebenarnya yang terjadi?
Jadi robot memiliki kamera di bagian atas sini.
Dan itu melihat ke bawah di papan.
Dan itu melihat apakah itu punya O merah atau biru
dan X. putih Seperti yang bisa ditempatkan pada papan, yang pada dasarnya input yang sama
bahwa kita akan membaca di dari struktur data kami dari layar kami.
Itu berjalan sama algoritma minimax menjadi
mampu menemukan tempat untuk menempatkan tanda yang baik.
>> Dan kemudian kami memberikan perintah tentang di mana kami ingin token untuk ditempatkan.
Lengan bergerak keluar.
Ini menggunakan gripper vakum untuk menerapkan beberapa hisap untuk sepotong kayu,
mengambilnya, memindahkannya ke kanan tempat, dan kemudian melepaskan hisap
dan menjatuhkannya.
Baiklah, kita akan untuk memberikan satu tembakan lebih
dengan sedikit lebih pintar pemain di sini.
Anda siap?
Baiklah, jika Anda akan berdiri di atas di sini dan memberikan a-- jadi begini
sehingga Anda dapat melihat semua orang.
Dan kemudian [tidak terdengar].
>> ROBOT: Ini adalah giliran saya.
>> SPEAKER: Baxter akan mulai.
Giliran Anda.
Ini adalah giliran saya.
Giliran Anda.
Ini adalah giliran saya.
>> [TAWA]
>> SPEAKER: [Berbisik] Hanya biarkan dia pergi ke depan dan menang.
ROBOT: Ini adalah giliran Anda.
SPEAKER: Itu OK.
>> ROBOT: Ini adalah giliran saya.
>> [TAWA]
>> Aku menang.
>> [TAWA]
>> Saya memulai permainan.
>> SPEAKER: Baiklah, terima kasih banyak.
Baiklah, saya pikir kami punya waktu untuk satu lagi yang sangat baik pemain tic-tac-toe,
seseorang yang dapat menempatkan hal ini untuk cocok, siapa yang tahu apa yang mereka lakukan.
>> [TAWA]
>> Siapa yang akan menjadi juara di sini?
Baiklah, teman sukarela Anda.
Itu cukup baik bagi saya.
Katakan padaku nama Anda lagi.
AUDIENCE: Tamir.
SPEAKER: Tamir, bagus untuk melihat Anda.
Baiklah, sekali lagi, kita akan menempatkan Anda sampai di sini sehingga semua orang dapat melihat Anda.
Anda perwakilan kami di pertandingan ini sekarang.
Baxter adalah satu dan oh dan oh.
Atau menyesal, satu oh dan satu.
Dan terserah kepada Anda di sini.
Baxter akan mendapatkan bergerak dulu.
Begitu.
ROBOT: Ini adalah giliran saya.
>> [TAWA]
>> Giliran Anda.
Ini adalah giliran saya.
Giliran Anda.
Ini adalah giliran saya.
Giliran Anda.
>> [TAWA]
ROBOT: Ini adalah giliran saya.
SPEAKER: Ini jauh lebih sulit ketika Anda berdiri di sini, orang-orang.
[TAWA]
ROBOT: Anda manusia begitu mudah untuk mengalahkan.
[Tertawa DAN Tepuk Tangan]
SPEAKER: Terima kasih banyak.
ROBOT: saya menang.
Saya memulai permainan.
>> SPEAKER: Baiklah, jadi terima kasih sangat banyak untuk Olivier, dan Alessandro,
dan Chen Ming.
>> [TEPUK TANGAN]
>> Saya ingin membuat satu titik terakhir.
Jadi Baxter di sangat berakhir di sana, ditipu.
Dan yang tak terduga.
Salah satu fantastis hal tentang AI adalah kita bahwa
melakukan pekerjaan di AI sehingga kita dapat membangun benar-benar menarik dan cerdas
perangkat.
Tapi kami juga melakukan pekerjaan di AI karena memberitahu kita sesuatu
tentang bagaimana manusia cerdas.
>> Salah satu favorit Studi dari laboratorium saya adalah
melihat apa yang terjadi ketika mesin tiba-tiba menipu.
Kami melakukan ini awalnya tidak dengan Baxter bermain tic-tac-toe,
tapi dengan robot kecil bernama Nao, yang bermain batu-kertas-gunting.
Dan kadang-kadang setelah bermain banyak dan banyak
membosankan batu-kertas-gunting game, robot akan melemparkan isyarat,
kalah, dan kemudian tiba-tiba berubah sikap dan mengatakan, saya menang.
>> [TAWA]
>> Sekarang, kadang-kadang kita juga harus robot, hanya sebagai kontrol, melempar isyarat,
menang, dan mengubah sikap nya kehilangan, membuang pertandingan,
menipu untuk kalah.
Dan itu hampir tidak menarik.
Robot yang menipu dalam rangka untuk memenangkan orang
menanggapi seolah-olah itu adalah untuk mendapatkan mereka, seperti itu
secara aktif mencari kehancuran mereka.
>> [TAWA]
>> Ini menjadi agen.
Hal ini seperti seseorang.
Memiliki keyakinan dan niat.
Dan itu bukan niat baik.
Dan robot yang melempar permainan yang hanya rusak.
Ini hanya sebuah perangkat yang rusak.
Mari saya tunjukkan beberapa contoh itu dari beberapa peserta kami.
Jadi, inilah kecurangan untuk kalah.
>> [VIDEO PLAYBACK]
- [Tak terdengar] menang.
Ayo mulai.
>> -Tunggu apa?
>> - [Tak terdengar] menang.
Ayo mulai.
>> [Tak terdengar] menang.
Ayo mulai.
>> SPEAKER: Dan di sini curang untuk menang.
>> -Ya, Saya menang.
Ayo mulai.
>> -Anda Tidak bisa melakukan itu.
>> [TAWA]
>> -Ya, Saya menang.
-Kamu curang.
Anda ditipu sekarang.
>> -Ya, Saya menang.
>> Hei, Anda cheater.
Anda menipu, super cheat.
>> [END PLAYBACK]
>> SPEAKER: berbeda ini reaksi cepat
mengubah persepsi kita tentang perangkat.
Apakah itu berarti bahwa kami sengaja membangun
mesin yang menipu karena itulah rekayasa terbaik yang dapat kita lakukan?
Tidak, tetapi mengatakan sesuatu benar-benar menarik tentang orang-orang.
Hal itu yang menipu Anda dan mencuri kemenangan Anda, itu
sesuatu yang hidup, yang bernyawa, yang keluar untuk mendapatkan Anda.
Ini memiliki kondisi mental.
Memiliki keyakinan.
Ini memiliki niat.
>> Hal itu yang tangan yang permainan untuk Anda, itu tidak.
Itu hanya rusak.
Hal ini dalam banyak hal mengapa mudah untuk membuang permainan dengan anak-anak.
Tetapi jika Anda mencoba untuk menipu mereka dan semacam mengklaim kemenangan
saat, Anda tahu, hanya untuk mempersingkat permainan, mereka akan menangkap Anda segera.
Jenis-jenis efek yang kita lihat keluar dari AI,
mereka mengajarkan kita banyak tentang diri kita sendiri.
>> Baiklah, itu saja untuk hari ini.
Terima kasih banyak untuk David dan tim produksi Harvard
untuk turun.
>> [TEPUK TANGAN]
>> Kami akan melihat Anda untuk kuis satu, dan kemudian untuk satu pesan terakhir.
Semoga hari Anda menyenangkan.
>> [TEPUK TANGAN]
>> [MUSIC PLAYING]
DAVID J Malan: Yah, kita mungkin perlu untuk memperkenalkan beberapa jenis enkripsi,
kanan?
Karena maka header permintaan HTTP ini akan
orak sehingga siapa pun mencoba untuk mengendus lalu lintas Anda
tidak akan benar-benar dapat melihat mereka.
Jadi apa solusi untuk masalah ini?
Nah, kita harus benar-benar memperkenalkan enkripsi ke dalam rumus,
sehingga ketika orang itu adalah transmisi data dari A ke B,
kita bisa aman send--
>> [TAWA]
>> Informasi dengan cara yang musuh tidak dapat, pada kenyataannya, melihatnya.