[MUSIC CHƠI] SPEAKER: Chào mừng trở lại, tất cả mọi người. Đây là CS50. Và hôm nay, chúng tôi có rất nhiều điều thú vị để nói về. Thứ nhất, mặc dù, tôi phải nhắc nhở bạn của một vài điều hành chính. Tuần này là một bài kiểm tra, Thứ Tư hoặc cho các mục Yale các ngày thứ Ba và thứ Năm, ngày thứ năm. Có đánh đố tối nay tại Yale, 5:30-07:00. Tại Harvard, họ đã ghi lại một ngày hôm qua. Và tất cả mọi người có thể xem trực tuyến mà. Ngoài ra, trong tuần này hoặc đầu tuần sau, chúng tôi có CS50 bài giảng cuối cùng của chúng tôi. [Rên rỉ] Tôi biết. Nó đến quá sớm. Sinh viên Yale sẽ có một live giảng dạy ở đây trong trường luật giảng vào thứ Sáu. Sẽ có bánh. Sinh viên Harvard sẽ có bài giảng cuối cùng trong Sanders vào thứ hai. Cũng sẽ có bánh. Ngoài ra, trong tuần này vào thứ Sáu, cho những người các bạn đang đến New Haven, chúng tôi có các hội chợ triển lãm CS50. Chúng tôi có hơn 30 các nhóm khác nhau đã đăng ký để hiển thị mọi thứ từ những chiếc thuyền buồm tự trị, cho hệ thống nhận chân dung kỹ thuật số, máy tính để âm nhạc và âm nhạc do máy vi tính. Vì vậy, xin vui lòng tham gia với chúng tôi. Tôi nghĩ rằng nó sẽ là một thời gian tuyệt vời. Hôm nay, tuy nhiên, chúng tôi nhận được tiếp tục nói về AI, về trí thông minh nhân tạo. Và một trong những điều mà chúng tôi đang đi để có được đến ngày hôm nay là ý tưởng về làm thế nào để sử dụng AI để giải quyết vấn đề. Bây giờ, như mọi khi, chúng ta hãy bắt đầu với một cái gì đó đơn giản. Và chúng ta sẽ bắt đầu với một ý tưởng đơn giản. Và đó là cách sử dụng tìm kiếm. Vì vậy, hãy tưởng tượng một phút mà tôi có một nhiệm vụ mà tôi cần phải thực hiện. Và tôi muốn có công việc đó tự động bởi một số đại lý phần mềm. Hãy tưởng tượng rằng tôi đang cố gắng để đặt một bộ các chuyến bay từ, hãy nói, Boston đến San Francisco. Tôi có thể đi qua và tôi có thể sử dụng một trong những tìm kiếm trực tuyến tuyệt vời công cụ, đó là sẽ làm về cơ bản cùng một quá trình mà chúng tôi sẽ đi bộ qua ngày hôm nay. Nhưng nếu bạn không có mà công cụ, bạn sẽ làm gì? Vâng, bạn có thể tìm và nhìn thấy và nói, tôi ở Boston. Có những chuyến bay có sẵn cho tôi? Bây giờ, có lẽ tôi có ba các chuyến bay có thể ra khỏi Boston mà sẽ phù hợp với thời gian khi tôi cần phải rời khỏi. Tôi có thể bay tới Chicago. Hoặc tôi có thể bay tới Miami. Hoặc tôi có thể bay tới New York. Sau đó tôi có thể nhìn từ mỗi một trong những thành phố điểm đến và suy nghĩ về những gì các vị trí Tôi có thể có thể đạt được từ mỗi của những thành phố riêng lẻ. Vì vậy, có lẽ từ Chicago, tôi có thể nhận được một chuyến bay trực tiếp đến San Francisco. Đó là tuyệt vời. Hoặc tôi có thể có được một chuyến bay đến Denver. Bây giờ, có lẽ đó là chuyến bay đi San Francisco là giải pháp hoàn hảo cho tôi, nhưng có lẽ không. Có lẽ tôi đang tìm kiếm cái gì đó là một chút rẻ hơn hoặc một chút tốt hơn cho lịch trình của tôi. Và vì vậy tôi có thể tìm kiếm những gì khác khả năng có thể được ra khỏi đó. Vì vậy, tôi có thể nhìn vào Denver. Và từ Denver, tốt, có lẽ Tôi có thể có được một chuyến bay đi Austin. Và từ Austin, có lẽ tôi có thể có được một chuyến bay đến Phoenix, và từ Phoenix đến San Francisco. Bây giờ, tôi vẫn chưa xong. Bởi vì có thể có một chuyến bay trực tiếp từ New York đến San Francisco đó là hoàn hảo đối với tôi. Hoặc có thể có một chuyến bay từ Miami qua Denver đó là rẻ hơn rất nhiều. Vì vậy, tôi vẫn phải đi. Và tôi vẫn phải nhìn vào tất cả những thành phố mà tôi đã không điều tra được nêu ra. Tôi có triệt để kiểm tra tất cả các khả năng mà tôi có thể có. Vì vậy, từ New York, có lẽ tôi có thể có được một chuyến bay tới Nashville, và từ Nashville Austin. Và sau đó tôi biết tôi đang ở đâu. Và sau đó tôi biết từ Austin, tôi có thể bay đến Phoenix, và từ Phoenix đến San Francisco. Nếu tôi bay đầu tiên đến Miami, mặc dù, có lẽ tôi có thể nhận được một chuyến bay từ Miami đến Nashville, hoặc từ Miami tới Austin. Và bây giờ tôi đã thử tất cả của các khả năng. Tôi đã xây dựng được đồ thị này chỉ cho tôi thấy tất cả các tuyến đường có thể mà tôi có thể có thể để mất. Khi chúng tôi đại diện cho các loại vấn đề, chúng tôi sẽ không để đại diện cho chúng một cách rõ ràng như biểu đồ này, vì đồ thị mà không đại diện lịch sử của nơi mà chúng tôi đã đi. Biết rằng tôi đã bay từ Phoenix San Francisco không cho tôi biết liệu tôi đi qua Nashville, hoặc qua Denver, hoặc thông qua Miami. Vì vậy, những gì tôi sẽ làm thay vào đó là Tôi sẽ đưa vấn đề này cùng, và tôi sẽ đại diện cho nó như một cái cây. Và ở gốc của cây, tại đầu, tôi sẽ đưa những nơi mà tôi bắt đầu, Boston. Và từ Boston, tôi sẽ xem xét tất cả các địa điểm có thể mà tôi có thể đi du lịch. Vâng, trong trường hợp này, tôi đã có ba, Chicago, New York, và Miami. Và sau đó tôi sẽ khám phá từng những trẻ em trong cây. Từ Chicago, tôi đã thấy mà tôi đã có hai chuyến bay. Tôi có thể bay trực tiếp đến San Francisco hay đến Denver. Bây giờ San Francisco, đó là mục tiêu của tôi. Đó là điểm đến của tôi. Đó sẽ là một chiếc lá của cây này. Đó là, tôi sẽ không bao giờ đi một nơi nào đó sau khi San Francisco. Từ Denver, mặc dù, Tôi có thể bay từ Denver Austin, từ Austin đến Phoenix, và từ Phoenix tới San Francisco. Và bây giờ một lần nữa, tôi đã đạt đến một chiếc lá. Sau đó tôi có thể quay trở lại tiếp theo thành phố mà tôi chưa khám phá hết. Đó sẽ là New York, đi lại lên đến đỉnh của cây của tôi, đi xuống đến New York. Từ New York, tôi có thể bay đến Nashville, từ Nashville đến Austin, từ Austin đến Phoenix, và từ Phoenix tới San Francisco. Và cuối cùng, một trong những thành phố tôi đã không nhìn nào, Miami. Vâng, từ Miami Tôi nói tôi có hai khả năng, Nashville hoặc Austin. Nếu tôi bay tới Nashville, cũng sau đó tôi bay từ Nashville, Austin, đến Phoenix, đến San Francisco. Nếu tôi bay đến Austin, tôi bay Austin, Phoenix, San Francisco. Và bây giờ tôi có một cây. Đó là một cây hoàn chỉnh. Đó là tất cả những khả năng và tất cả các con đường mà tôi có thể mất. Đó là, nếu tôi bắt đầu vào Gốc của cây ở đầu và tôi đi xuống một trong những lá, nó nói với tôi không chỉ nơi tôi sẽ đến kết thúc, San Francisco, nhưng nó cho tôi con đường đó Tôi cần phải làm để đạt được điều đó. Bây giờ, mà một trong số đó là tốt nhất? Vâng, không có gì về điều này vấn đề chưa nói với tôi mà trong số đó là giải pháp tốt nhất. Có lẽ tôi chăm sóc về nhất Tôi bao nhiêu thời gian trong không khí, hoặc khoảng cách mà tôi đang bay. Trong trường hợp đó, Chicago đến San Francisco có thể là số ngắn nhất dặm trong không khí. Có lẽ tôi quan tâm về chi phí. Và tất cả chúng ta đều biết các chuyến bay trực tiếp thường đắt hơn. Vì vậy, có lẽ nếu tôi thực hiện việc này loại đường ngược thông qua Miami, Nashville, Austin, Phoenix, sau đó có thể Tôi nhận được một mức giá thấp hơn. Nhưng tôi có thể tối ưu hóa trên bất kỳ tiêu chí mà tôi quan tâm. Ai có tốt nhất trong chuyến bay Wi-Fi, hoặc đó các sân bay có thức ăn tốt nhất có sẵn. Và mỗi người trong những người có thể cung cấp cho tôi một giải pháp khác nhau mà tôi thấy như là tốt nhất. Những loại vấn đề, chúng ta đang đi để xây dựng cây này khả năng, và sau đó nhìn vào mỗi người các con đường, và kiểm tra mà những người thực hiện tốt một tiêu chí cho chúng ta, chúng ta sẽ gọi những vấn đề tìm kiếm. Và chúng tôi có rất nhiều các thuật toán, một số trong đó chúng tôi đã nhìn thấy rồi, đi và khám phá những cây này. Chúng ta có thể làm điều đó theo cách mà tôi vừa làm, một tìm kiếm theo chiều sâu, đi xuống xa như chúng tôi có thể đến khi chúng tôi nhấn một chiếc lá, và sau đó trở lên, và sẽ phải quay trở lại. Hoặc chúng ta có thể làm những gì gọi là tìm kiếm theo chiều rộng. Chúng ta có thể mở rộng tất cả mọi thứ ở đầu, và sau đó tất cả mọi thứ một dòng bên dưới đó, và sau đó tất cả mọi thứ một dòng bên dưới mà. Những cây tìm kiếm là nền tảng cho AI. Nhưng họ không hoàn toàn nhận được nó phải tất cả các thời gian. Trong thực tế, trong rất nhiều các trường hợp rằng chúng ta thực sự quan tâm, chúng tôi muốn xây dựng một cây, nhưng chúng ta không thực sự có được để làm cho tất cả các quyết định. Đây là những tình huống gọi là tìm kiếm đối địch, cũng được biết đến như làm thế nào để viết chơi game hệ thống và được trả tiền cho nó. Nhưng đó là những loại của các hệ thống mà tôi có thể được lựa chọn khi tôi đi từ Boston, thành phố mà tôi đi đến bên cạnh. Nhưng sau đó, một người khác có thể nhận được để đưa ra quyết định về nơi tôi bay. Vì vậy, để xây dựng các các loại cấu trúc, chúng tôi sẽ phải mất một chút phương pháp tiếp cận khác nhau để nó. Chúng tôi sẽ không để có thể chỉ cần tìm kiếm thông qua các cây nữa, bởi vì chúng tôi không một trong đó là trong kiểm soát của mỗi người trong những điểm quyết định. Vì vậy, hãy tưởng tượng một đơn giản trò chơi như tic-tac-toe. Tôi có thể bắt đầu với một hội đồng quản trị hoàn toàn trống. Và trong tic-tac-toe, X được chơi đầu tiên. Và vì vậy tôi có thể suy nghĩ về tất cả các di chuyển có thể là X có thể làm. Và nếu tôi là người chơi X, đó là tuyệt vời. Tôi có chín có thể di chuyển mà tôi có thể làm. Tôi có thể đặt một X trong bất kỳ một của chín vị trí. Và sau đó từ mỗi người, tôi có thể tưởng tượng điều gì sẽ xảy ra tiếp theo. Vâng, trong trường hợp này, người kia cầu thủ sẽ nhận được để có một lượt. O sẽ nhận được để có một lượt. Và từ mỗi người, có sẽ là tám địa điểm khác nhau O có thể đặt dấu của họ. Hãy nói rằng tôi quyết định rằng tôi là sẽ đặt một dấu X ở trung tâm. Điều đó luôn luôn có vẻ như một động thái mở tốt. Tôi có thể nhìn vào bên dưới đó, tám di chuyển có thể là O làm. Bây giờ, nếu tôi chơi X, đó là tuyệt vời. Tôi nhận được để chọn một trong tôi đi đến, là ở giữa. Nhưng bây giờ O được chọn. Và tôi không có quyền kiểm soát về quyết định đó. Nhưng từ mỗi người vị trí hội đồng quản trị có thể, có thì khác thiết lập các khả năng. Khi nói đến là my quay lại, tôi sẽ nhận được để chọn và nói, tốt, nếu O di chuyển vào trong, tốt, vị trí giữa bên trái, sau đó Tôi có một tập hợp các khả năng nơi mà tôi có thể mất động thái tiếp theo của tôi. Từ đó, tôi có thể xem xét tất cả các các khả năng bên dưới chúng. Và sau đó O sẽ nhận được để lựa chọn trong số những người. Và tôi có thể tiếp tục xây dựng này cây ra cho đến khi tôi đã đến điểm nơi một người nào đó thắng game-- đó đã được coi là một lá node-- hoặc hội đồng quản trị là hoàn toàn đầy đủ và không có ai đã thắng. Và đó cũng sẽ là một nút lá. Đó sẽ là một tie. Nhưng điều khó khăn với điều này là nếu điều này chỉ là một tìm kiếm thông thường vấn đề, tôi muốn được thể nói, tốt, X nên đi ở đây. Và O nên đi theo con đường trên đó. Và sau đó X nên đi qua đây. Và sau đó O nên đi theo con đường trên đó. Và sau đó X có thể có được ba trong một hàng, và tôi giành chiến thắng. Và trò chơi sẽ kết thúc trong năm di chuyển, ba đối với tôi, hai cho đối thủ của tôi. Nhưng tôi không luôn luôn có được để lựa chọn mà. Vì vậy, thay vào đó, những gì chúng tôi sẽ phải làm là chúng ta sẽ có để có một chiến lược mới. Và chiến lược đó thuật toán trò chơi thường sử dụng là những gì được gọi là minimax. Ý tưởng trung tâm của minimax là chúng tôi sẽ chọn di chuyển cung cấp cho đối thủ của chúng tôi tập hợp xấu nhất có thể di chuyển của họ có thể làm. Nó không làm tôi bất kỳ tốt để lựa chọn một động thái mà Tôi có thể có thể để giành chiến thắng sau rằng, bởi vì đối thủ của tôi không phải là sẽ cho tôi cơ hội đó. Họ sẽ chọn một số kết quả khủng khiếp đối với tôi. Vì vậy, tôi sẽ làm cho các di chuyển, buộc đối thủ của tôi để làm điều gì đó tốt hơn cho tôi. Được rồi. Chúng ta hãy xem làm thế nào mà phát ra. Vì vậy, đây là thuật toán của chúng tôi trong giả. Chúng ta sẽ tạo ra toàn bộ cây trò chơi. Chúng ta sẽ xây dựng toàn bộ cấu trúc. Và sau đó chúng ta sẽ đi qua. Và ở dưới cùng rất tại mỗi các nút thiết bị đầu cuối, tại mỗi lá, chúng tôi sẽ đánh giá như thế nào có giá trị là với tôi? Và chúng ta sẽ đi những giá trị đó là tốt cho tôi là tích cực. Những điều đó là không tốt cho tôi sẽ ít tích cực, hoặc không, hoặc thậm chí âm. Vì vậy, trong tic-tac-toe, có lẽ một chiến thắng đối với tôi là tốt. Đó là một một. Và một tie là số không. Và cái gì đó là một tổn thất cho tôi, có lẽ đó là một trong những tiêu cực. Tất cả những vấn đề là tốt hơn nó là dành cho tôi, điểm số càng cao nó nhận được. Từ những khả năng ở dưới, sau đó chúng tôi sẽ lọc trở lên. Và khi đó là cơ hội của tôi để lựa chọn trong một tập hợp các lựa chọn thay thế, Tôi sẽ chọn một trong đó là có số điểm cao nhất. Và bất cứ khi nào nó là của tôi đối thủ biến để lựa chọn, Tôi sẽ giả định rằng họ sẽ chọn một với số điểm thấp nhất. Và nếu tôi làm điều này tất cả các cách lên đến trên cùng của cây, Tôi sẽ chọn một con đường cung cấp cho cho tôi những kết quả tốt nhất mà tôi có thể có được, giả định rằng đối thủ của tôi làm cho tất cả những bước đi đúng. Được rồi, vì vậy hãy xem này trong hành động đầu tiên. Và sau đó chúng ta sẽ thực sự nhìn vào các mã cho nó. Vì vậy, hãy tưởng tượng tôi có cây lớn này. Và bây giờ tôi không chơi tic-tac-toe. Tôi muốn cung cấp cho bạn một cái gì đó phong phú hơn một chút. Vì vậy, tôi đã có một số trò chơi, nơi có nhiều điểm khác nhau mà tôi có thể có ở cuối. Và vì vậy tôi xây dựng cây hoàn chỉnh này. Và tôi nhận được để di chuyển đầu tiên. Tôi đang ở thư mục gốc của cây. Và tôi có thể chọn that-- vì vậy tôi có được để tối đa hóa qua mà nút đầu tiên. Và sau đó đối thủ của tôi được cho đi. Và sau đó tôi nhận được để đi một lần nữa. Vì vậy xuống phía dưới, tôi có một tập hợp các khả năng mà tôi có thể lựa chọn, bang đầu cuối khác nhau của trò chơi. Nếu tôi gục ngã trong đó xa trái tay góc, và tôi thấy rằng tôi đã có một sự lựa chọn giữa một tám, bảy, và một hai, tốt, tôi là một trong đó được chọn. Vì vậy, tôi sẽ chọn một trong những tốt nhất trong những người. Tôi sẽ chọn tám. Vì vậy, tôi biết rằng nếu tôi lấy xuống đến thời điểm đó, Tôi sẽ có thể nhận được rằng tám điểm. Nếu tôi kết thúc tại điểm tiếp theo trên, nút tiếp theo trên, một chín, một, hoặc một sáu, tốt, tôi đi để lựa chọn tốt nhất của những người. Tôi sẽ chọn chín. Nếu tôi có một sự lựa chọn giữa hai, và bốn, và một, Tôi sẽ chọn bốn, mức cao nhất. Bây giờ, nếu tôi nhìn vào mức độ ở trên đó, đối thủ của tôi là một trong những được để làm cho sự lựa chọn đó. Vì vậy, đối thủ của tôi được đến chọn, tôi muốn để cho anh ta điều đó đang xảy ra để có được anh ta tám điểm, hay để tôi cho anh ta những điều đó là sắp đặt cho nó chín điểm, hoặc điều đó đang xảy ra để cho anh ta bốn điểm? Và đối thủ của tôi, là hợp lý, sẽ chọn tối thiểu của những người, sẽ chọn bốn. Và tôi có thể làm điều này thông qua toàn bộ cây. Tôi có thể đi xuống đến đó tập trung của ba. Và tôi có thể lựa chọn giữa một, ba, và năm. Và tôi có thể lựa chọn. Vì vậy, tôi chọn một năm. Tôi có thể chọn ba, chín, hoặc hai. Tôi phải lựa chọn, vì vậy tôi chọn chín. Sáu, năm, hoặc hai, tôi chọn. Tôi có thể chọn trong sáu. Cấp trên rằng, những người được lựa chọn? Những người được lựa chọn? Các chàng trai khác, đối thủ của tôi. Vì vậy, họ chọn năm, chín, hoặc sáu, mà một trong những? Đung Năm. SPEAKER: Họ chọn năm. Họ có thể chọn mức tối thiểu. Và sau đó là người cuối cùng, chọn một, hai, hoặc ba. Tôi phải lựa chọn, vì vậy tôi chọn ba. Nine, bảy, hoặc hai, tôi chọn chín. Và 11, sáu hoặc bốn, tôi chọn 11. Đối thủ của tôi sau đó chọn ba, chín, hoặc 11, chọn tối thiểu. Ông mang lại cho tôi một ba. Và rồi cuối cùng ở đầu cây, tôi có thể chọn một lần nữa. Và tôi có thể lựa chọn giữa bốn, một năm, hoặc một ba. Vì vậy, tôi mất năm. Nếu tôi có để kiểm soát mọi thứ, tôi muốn đi theo con đường dẫn đến sự 11. Nhưng tôi không nhận được để làm cho sự lựa chọn đó. Nếu tôi đi xuống con đường đó. Đối thủ của tôi sẽ buộc tôi vào sự lựa chọn mà dẫn đến một ba. Vì vậy, tốt nhất mà tôi có thể làm là mất rằng chi nhánh trung bình, làm cho rằng sự lựa chọn đó là cuối cùng sẽ dẫn tôi đến năm điểm. Đó là những gì minimax nào. Được rồi. Chúng ta hãy nhìn vào đó. Vì vậy, ở đây CS50 IDE là một chương trình thực hiện minimax để chơi tic-tac-toe. Chúng ta sẽ xây dựng một đại diện. Chúng ta sẽ có hai opponent-- hoặc hai người chơi, máy tính của chúng tôi máy nghe nhạc và nghe một con người. Số một cầu thủ sẽ được chơi O. Đó sẽ là cầu thủ máy. Họ nhận được để di chuyển thứ hai. Và các cầu thủ khác, chúng tôi nghe một con người, sẽ là X. Và để làm cho cuộc sống của tôi chút đơn giản, tôi sẽ dán nhãn là một trong những cầu thủ tiêu cực. Vì vậy, tôi chỉ có thể nhân bởi trong những tiêu cực để trao đổi giữa một cầu thủ và các khác. Tất cả các quyền, vì vậy chúng ta hãy nhìn vào những gì chúng tôi đang thực sự đi làm. Chúng ta sẽ xác định bảng của chúng tôi. Nó sẽ được, tốt, chúng ta sẽ để cho phép nó được ba ba, hoặc chúng ta thậm chí có thể chơi năm bởi năm hoặc bảy bảy tic-tac-toe nếu bạn muốn như thế, dựa trên một số kích thước D. Và chúng ta sẽ có một cặp vợ chồng các chức năng trợ giúp mà sẽ làm những việc như khởi tạo screen-- hoặc xin lỗi, khởi tạo các biến của chúng tôi, rõ ràng màn hình, vẽ bảng trên màn hình, một kiểm tra một hội đồng quản trị để xem có hay không có một người chiến thắng, một trong đó phân tích thông qua các dòng lệnh, chỉ để giúp đỡ, một mà đọc trong đầu vào, và một chức năng gọi là minimax. Và đó là một trong những chúng tôi sẽ quan tâm nhất. Nhưng chúng ta hãy xem xét đầu tiên tại chính. Chúng ta làm gì? Vâng, chúng ta sẽ phân tích cú pháp dòng lệnh của chúng tôi, chỉ cần đọc và xem những gì Ban chiều, chúng tôi muốn có. Chúng tôi sẽ khởi tạo ban của chúng tôi. Và sau đó chúng ta sẽ nhập một loop hoang dã lớn, liên tục chấp nhận di chuyển cho đến khi trò chơi là giành được, hoặc không có di chuyển trái. Mỗi lần chúng tôi đi qua đó vòng lặp, chúng tôi sẽ xóa màn hình. Chúng tôi sẽ vẽ bảng trên màn hình. Và chúng tôi cố tình loại trừu tượng hóa những đi như thủ tục con, do đó chúng tôi không phải lo lắng quá nhiều về các chi tiết như thế nào khi chúng xảy ra. Bạn sẽ có mã sau ngày hôm nay. Và nếu bạn muốn xem xét thông qua và tìm hiểu, bạn có thể nhìn thấy tất cả. Nhưng chúng ta sẽ vẽ một bảng trên màn hình. Và sau đó chúng tôi sẽ kiểm tra và thấy, chúng ta có một người chiến thắng? Có ai đó đã thắng trò chơi này? Nếu họ có, chúng tôi sẽ in ra một thông điệp chiến thắng. Và chúng ta sẽ kết thúc trò chơi. Chúng tôi cũng sẽ kiểm tra và xem nếu có một tie. Nó sẽ được dễ dàng để xem nếu có một tie. Nó có nghĩa là tất cả các không gian được đầy đủ, nhưng chưa có một chiến thắng nào. Chúng ta có thể khai báo một tie và được thực hiện. Sau đó, thực sự nếu meat-- đó là một máy nghe nhạc máy, chúng tôi sẽ cho phép điều đó máy nghe nhạc máy tính để tìm kiếm thông qua sử dụng thuật toán minimax này, để tìm nước đi tốt nhất mà nó có thể. Và sau đó chúng tôi sẽ đặt mà di chuyển lên. Nếu không, nếu đó là một cầu thủ của con người, chúng ta sẽ đọc số đầu vào từ các con người. Và sau đó cho dù đó là con người máy nghe nhạc hoặc máy nghe nhạc máy, chúng tôi sẽ làm một vài chút bit kiểm tra lỗi, chắc chắn nó sẽ nằm trong ranh giới các kích thước thực tế của hội đồng quản trị mà chúng ta có, chắc chắn rằng không gian đó là trống rỗng, rằng không có ai đặt một mảnh trong đó rồi. Và sau đó chúng ta chỉ cần một mảnh trên bảng, thay đổi người chơi đến lớp kế tiếp, và tăng bao nhiêu di chuyển đã xảy ra. Đó là vòng lặp chính trò chơi tic-tac-toe của chúng tôi. Minimax, sau đó, là chính xác các thuật toán mà chúng ta trước. Việc điều chỉnh duy nhất chúng tôi đã thực hiện để chúng ta có thể chơi cao Ban chiều là chúng tôi đã giữ tham số phụ này được gọi là sâu. Và chiều sâu chỉ nói, nếu tôi tìm kiếm xuống qua cây và tôi nhận được rất xa xuống ngoài một số sâu cấp mà tôi chỉ không muốn để đi xa hơn bất kỳ, Tôi sẽ dừng lại và chỉ đánh giá bảng tại thời điểm đó. Tôi sẽ kiểm tra và xem nếu có một người chiến thắng. Nếu có một người chiến thắng, tôi trả lại. Nếu không, tôi sẽ đi qua một vòng lặp. Và tôi sẽ nói, cho tất cả các địa điểm có thể mà tôi có thể có thể mất di chuyển của tôi, tôi sẽ xây dựng một hội đồng quản trị có tính giả thuyết bao gồm di chuyển của tôi trên tàu rằng, và sau đó đệ quy gọi minimax. Nếu nó di chuyển của tôi, tôi nhận được để tìm ra một trong đó là đã nhận số điểm lớn nhất. Nếu đó là động thái của đối thủ, chúng tôi tìm thấy một trong đó là có số điểm tối thiểu. Và mọi thứ khác là chỉ lưu trữ hồ sơ. Được rồi, vì vậy hãy xem hoạt động này. Trên thực tế, có lẽ chúng ta có thể có được một vài tình nguyện viên để đi lên và chơi tic-tac-toe. [Không nghe thấy] một, và một hơn, hai, phải có. Nào lên. Vì vậy, chúng ta hãy đi trước và khởi động lại này hoàn toàn. Vì vậy, hi. Đung Hi. SPEAKER: Tên của bạn là gì? Đung Gorav. SPEAKER: Gorav. Đung Tôi Layla. SPEAKER: Và Layla, và Layla, xin lỗi. Nào lên. Gorav, chúng ta sẽ có bạn đi đầu tiên. Và tôi sẽ yêu cầu bạn phải là một không tốt lắm chơi tic-tac-toe. OK, vì vậy tất cả những áp lực đang tắt về bạn. Hãy xem, mặc dù, rằng máy tính của chúng cầu thủ thực sự có thể làm điều gì đó thông minh. Vì vậy, đi trước. Bạn đang đi đến gõ trong đó phối hợp bạn muốn đặt X của bạn trong. A0, OK, và máy đã đi ngay lập tức và để lại dấu ấn của mình trong A1. Đặt O trên diễn đàn. Được rồi, bây giờ đi về phía trước. Bạn muốn đi đâu? C2. Máy nghe nhạc máy của chúng tôi đã thực hiện quảng trường trung, chặn bạn. Vì vậy, đó là một tốt, điều thông minh cho nó làm. Bạn đã chặn nó. Đó là tuyệt vời. Phải mất góc đó. Và nó sẽ buộc bạn phải lấy một không gian cuối cùng, B0. Và trò chơi kết thúc trong một tie. Nhưng nó chơi một cách hợp lý trò chơi chống lại bạn, phải không? Được rồi, cảm ơn rất nhiều, Gorav. [Vỗ tay] Tất cả các quyền, Layla, chúng ta đang đi các trò chơi trên các bạn ở đây. Đung Oh, tuyệt vời. SPEAKER: Chúng tôi sẽ cung cấp cho bạn bốn bốn tic-tac-toe. Bây giờ, trong bốn bốn, bạn có để giành chiến thắng với bốn trong một hàng, không phải ba trong một hàng. Và đó là của bạn. Vì vậy, Layla mất D1. Hiện chúng tôi đang đi theo máy nghe nhạc máy tính của chúng tôi ở đây. Ba ba tic-tac-toe là loại điều đó là dễ dàng cho tất cả chúng ta. Nhưng nó vẫn còn tốt đẹp để xem máy nghe nhạc máy tính làm cho di chuyển thông minh. Bốn bốn được đến là một chút phức tạp hơn. Thực hiện độc đáo. Tất cả các quyền, do đó Layla kết thúc. Oh, và chúng ta nên kết thúc ở đó. Nhưng chúng ta hãy làm một nhiều lên ở đây. Vì vậy, Layla, cảm ơn bạn. Thực hiện độc đáo. [Vỗ tay] Vì vậy, người chơi tic-tac-toe của chúng tôi đi thông qua và tìm địa điểm, giải quyết chúng bằng cách sử minimax này. Và tôi đã có một thiết lập độ sâu vào đó để nó sẽ không chạy quá nhanh, đó là lý do tại sao có thể Layla đã có thể đi độc đáo trước như bà đã làm, và đã làm rất tốt. Nhưng những hệ thống mà chỉ đi qua và lực lượng vũ phu đi sâu hơn và sâu sắc hơn, và sâu hơn, và tiếp tục tìm kiếm các giải pháp mà họ cần, những loại hệ thống đang khá thành công tại các, tốt, Ban trò chơi tiêu chuẩn. Và trên thực tế, nếu chúng ta nhìn vào một ba ba tic-tac-toe game, này về cơ bản là một vấn đề được giải quyết. Và đây là một sơ đồ tuyệt vời từ Randall Munroe tại XKCD, cho thấy những chuyển bạn nên mất, được đưa ra động thái của đối thủ của bạn. Đây là điều mà chúng ta có thể dễ dàng xác định trước thời hạn. Nhưng điều gì sẽ xảy ra khi chúng tôi nhận được để biết thêm trò chơi phức tạp, trò chơi phức tạp hơn, nơi có bảng lớn hơn, nhiều hơn khả năng, chiến lược sâu sắc hơn? Nó chỉ ra rằng điều này bạo lực tìm kiếm vẫn hiện khá tốt, ngoại trừ khi bạn nhận được đến điểm nơi cây này là rất lớn mà bạn không thể đại diện cho tất cả. Khi bạn không thể tính toán toàn bộ cây, khi bạn không thể đi về phía trước và đẩy mình đến điểm mà bạn đã nhận toàn bộ cây trong bộ nhớ, hay bạn có thể có được nó trong bộ nhớ và nó sẽ chỉ đưa bạn cách quá dài để tìm kiếm thông qua nó, bạn phải làm một cái gì đó thông minh hơn. Để làm điều đó, bạn phải làm hai việc. Đầu tiên, bạn phải tìm một số cách giới hạn chiều sâu của bạn. Vâng, đó là OK. Chúng tôi có thể tìm thấy một số đẹp, tối thiểu và nói, bạn chỉ có thể đi quá sâu. Nhưng khi bạn làm điều đó, có nghĩa là bạn có các bảng một phần không đầy đủ. Và bạn phải lựa chọn, tôi thích hội đồng quản trị một phần không đầy đủ này, hoặc hội đồng quản trị một phần không hoàn chỉnh này? Và trên của chúng tôi bốn bằng bốn trò chơi tic-tac-toe, máy nghe nhạc máy tính của chúng tôi đã xuống đáy và nó nói, Tôi đã có hai bảng khác nhau. Không ai là một chiến thắng. Không ai là một mất mát. Không ai là một tie. Làm thế nào để lựa chọn giữa chúng? Và nó không có một cách thông minh để làm điều đó. Chúng tôi nhìn thấy loại đánh giá xảy ra tất cả các thời gian khi chúng tôi nhận được vào trò chơi phức tạp hơn. Cờ vua là một ví dụ tuyệt vời. Trong cờ vua, chúng ta có, đầu tiên của tất cả, một tấm bảng lớn hơn. Chúng tôi có mảnh hơn rất nhiều. Còn vị trí của những mảnh và cách mà các mảnh di chuyển là cực kỳ quan trọng. Vì vậy, nếu tôi muốn sử dụng minimax, Tôi cần để có thể xác định và nói, hội đồng này, nơi không ai thắng hay thua chưa, là bằng cách nào đó tốt hơn so với khác này hội đồng quản trị, mà không có ai đã thắng hay thua. Để làm điều đó, tôi có thể làm những thứ như tôi có thể chỉ đếm có bao nhiêu phần làm tôi có và bao nhiêu phần để bạn có? Hoặc tôi có thể cung cấp khác nhau miếng điểm khác nhau. Nữ hoàng của tôi là có giá trị 20 điểm. Cầm đồ của bạn đáng giá một điểm. Ai có tổng số điểm nhiều hơn? Hoặc tôi có thể xem xét những điều thích, người ấy có vị trí hội đồng quản trị tốt hơn? Đến lượt của nó bên cạnh, bất cứ điều gì mà tôi có thể đừng để đánh giá chính xác hơn mà những khả năng là tốt hơn mà không cần xem xét thấu đáo mỗi động thái có thể đến sau đó. Bây giờ để làm công việc đó, một trong những điều đó là sẽ trở nên thực sự quan trọng đối với chúng tôi không chỉ là di chuyển thẳng xuống đến độ sâu đặc biệt giới hạn, nhưng có thể nói, một trong những ý tưởng mà tôi có là xấu như vậy mà nó không đáng kể tất cả các cách có thể rằng mọi thứ có thể đi từ xấu đến tồi tệ hơn. Để làm điều đó, chúng ta sẽ thêm vào minimax một nguyên tắc gọi là alph-beta. Và alpha-beta cho biết, nếu bạn có một ý tưởng tồi, không lãng phí thời gian của bạn cố gắng để tìm ra chính xác như thế nào xấu nó được. Vì vậy, đây là những gì chúng ta sẽ làm. Chúng ta sẽ đi cùng nguyên tắc mà chúng tôi đã có trước, các loại minimax cùng tìm kiếm, chỉ có chúng tôi sẽ theo dõi, không chỉ của giá trị thực tế mà chúng ta có, nhưng chúng tôi sẽ theo dõi các tốt nhất có thể giá trị mà tôi có thể có được, và điều tồi tệ nhất có thể kết quả tôi có thể có. Và bất kỳ thời gian tồi tệ nhất có thể điều đang tìm kiếm khả năng, Tôi sẽ từ bỏ mà một phần của cây. Và tôi sẽ không bận tâm nhìn vào nó nữa. Tất cả các quyền, do đó hãy tưởng tượng rằng chúng ta bắt đầu với cùng một cây trò chơi này chính xác. Và bây giờ chúng ta sẽ đi xuống một lần nữa, tất cả các con đường xuống với góc dưới bên trái. Và ở phía dưới góc trái đó, chúng tôi nhìn và chúng tôi đánh giá ban này. Có lẽ đó là một bốn bốn tic-tac-toe hội đồng quản trị, hoặc có thể đó là một bàn cờ. Nhưng chúng ta nhìn vào nó, và chúng tôi đánh giá nó, và chúng tôi có được một giá trị của tám. Vào thời điểm đó, chúng ta biết rằng chúng ta sẽ có được ít nhất tám điểm từ quyết định dưới đây. Nó không có vấn đề gì khác hai là, rằng bảy và hai đó. Họ có thể là bất kỳ giá trị họ muốn có. Chúng tôi đang đi để có được ở ít nhất là tám điểm. Tất cả các quyền, nhưng chúng ta có thể đi trước và kiểm tra. Có lẽ một trong số họ là tốt hơn so với tám. Chúng tôi nhìn vào bảy. Đó có phải là tốt hơn so với tám? Không, điều đó không thay đổi quan điểm của chúng tôi cả. Chúng tôi nhìn vào hai người. Đó có phải là tốt hơn so với tám? Không, điều đó không thay đổi quan điểm của chúng tôi cả. Vì vậy, bây giờ chúng ta biết chúng ta đã kiệt sức tất cả các khả năng đó. Chúng tôi sẽ không để có được bất cứ điều gì tốt hơn so với tám. Chúng tôi đang đi để có được chính xác tám. Và như vậy chúng ta thay đổi nút đó và nói, mà bây giờ là một sự chắc chắn. Chúng tôi lên một cấp trên đó. Và bây giờ chúng ta biết điều gì đó về điều đó mức độ giảm thiểu. Chúng tôi biết rằng chúng tôi sẽ không bao giờ để có được hơn tám điểm nếu chúng tôi đi xuống hướng đó. Bởi vì ngay cả những hai chi nhánh khác lần lượt ra là tuyệt vời và giá trị hàng ngàn điểm mỗi, đối thủ của chúng tôi sẽ cung cấp cho chúng ta những tối thiểu, và cho chúng ta tám. Tất cả các bên phải, tốt, để xem nào. Chúng tôi sẽ tiếp tục đi xuống con đường đó. Chúng tôi đi xuống giữa mà bên trái. Chúng tôi nhìn xuống và chúng tôi thấy có một chín. Chúng tôi biết rằng chúng tôi đang đi để có được ít nhất chín điểm bằng cách đi xuống rằng con đường giữa. Và tại thời điểm này, chúng tôi chỉ có thể tạm dừng. Và chúng ta có thể nói, nhìn, tôi biết ở mức độ cao hơn, Tôi sẽ không nhận được hơn tám chỉ bằng cách đi xuống hướng này. Nhưng nếu tôi đi xuống giữa các con đường thay vì các con đường bên trái, Tôi sẽ nhận được ít nhất chín điểm. Đối thủ của tôi là không bao giờ hãy để tôi đi theo con đường trung đạo. Họ có thể lựa chọn. Và chúng ta sẽ chọn đường dẫn đến trái về phía tám, chứ không phải đột phá trung lộ về phía ít nhất chín điểm là những gì. Vì vậy, tại thời điểm đó, tôi sẽ dừng lại. Và tôi sẽ nói, bạn biết những gì? Tôi không cần phải nhìn bất kỳ xuống nhiều hơn theo hướng đó. Bởi vì tôi sẽ không bao giờ đạt được điều đó. Tôi có thể bỏ qua trong một ngày mà, và tôi có thể bỏ qua rằng sáu, bởi vì đó sẽ không bao giờ xảy ra. Vì vậy, tôi sẽ đi xuống và tôi sẽ xem xét khả năng tiếp theo. Tôi đi xuống đó và tôi nói, tôi thấy một hai. Tôi biết nếu tôi nhận được để ở đây, tôi sẽ nhận được ít nhất là hai. ĐƯỢC. Tôi tiếp tục đi. Tôi nhìn thấy một bốn. Tôi biết tôi sẽ nhận được ít nhất bốn. Vẫn còn rất nhiều giữa bốn và tám, mặc dù. Vì vậy, tôi tiếp tục đi. Tôi nhìn xuống và tôi thấy có một. Được rồi, tôi biết nếu Tôi đi xuống con đường này, Tôi sẽ có thể chọn bốn. Có gì đối thủ của tôi sẽ làm gì? Giữa một cái gì đó mang lại cho tôi tám, một cái gì đó mang lại cho tôi bốn, và một cái gì đó mang lại cho tôi ít nhất là chín, tốt, anh ta sẽ đưa cho tôi bốn. Và bây giờ tôi biết tại rất đầu, tôi sẽ để có thể nhận được ít nhất bốn điểm trong trò chơi này. Toàn bộ ý tưởng của alpha-beta là để cắt đứt các bộ phận của cây như vậy mà tôi không nhìn vào chúng nữa. Nhưng nó vẫn có vẻ như tôi đã nhìn vào rất nhiều cây. Hãy tiếp tục đi xuống. Chúng tôi sẽ đi xuống trong những kế tiếp bây giờ. Xuống phía dưới, tôi tìm thấy một ai. Tôi biết tôi sẽ có được ít nhất một. Tôi tiếp tục tìm. Tôi tìm thấy một ba. Tôi biết tôi sẽ nhận được ít nhất ba. Tôi tiếp tục đi. Tôi tìm thấy một năm. Tôi biết tôi sẽ nhận được năm nếu tôi đi xuống trong con đường đó. Và tôi cũng biết rồi rằng đối thủ của tôi, nếu tôi chọn giữa ba chọn lựa lớn, anh ta sẽ đưa cho tôi cái gì đó là năm hoặc ít hơn. ĐƯỢC. Tôi có thể tiếp tục đi đó. Tôi có thể nhìn xuống và tôi có thể nói, những gì tôi sẽ để có được nếu tôi đi xuống con đường trung? Tôi sẽ nhận được, tốt, ba có. Tôi sẽ có được một cái gì đó đó là ít nhất ba. Vẫn còn những thứ giữa ba và năm, vì vậy tôi tiếp tục tìm. Oh, một chín, tôi sẽ chắc chắn mất rằng hơn một ba. Tôi sẽ nhận được ít nhất chín nếu tôi đi theo con đường trung đạo. Bây giờ đối thủ của tôi dừng lại và nói, nhìn, có điểm không có nữa. Tôi biết rằng tôi giảm thiểu đối thủ, anh ấy sẽ cung cấp cho tôi những điều đó là ít hơn hoặc bằng năm, chứ không phải là những điều đó là lớn hơn hoặc bằng đến chín. Tôi dừng lại. Tôi không nhìn nữa tại đó. Tôi tiếp tục đi. Tôi nhìn xuống trên này. Xuống phía dưới, tôi tìm thấy một sáu. Tôi biết tôi sẽ nhận được ít nhất sáu. Và những gì tôi có thể làm gì? Tôi có thể dừng lại. Bởi vì có một sự lựa chọn giữa một cái gì đó là ít nhất sáu và một cái gì đó ít hơn năm, anh ấy sẽ cung cấp cho tôi những điều đó là ít hơn năm. Và bây giờ tôi biết tôi sẽ để có được chính xác những sự lựa chọn đó. Tôi sẽ nhận được rằng năm lựa chọn. Tôi quay trở lại lên đến đỉnh. Mà tôi sẽ lựa chọn giữa một cái gì đó đó là lớn hơn hoặc bằng bốn, hay cái gì đó tương đương với năm? Tôi sẽ mất một cái gì đó đó là ít nhất năm. Tôi đi xuống con đường cuối cùng, tất cả các con đường xuống phía dưới. Có một một. OK, ít nhất tôi sẽ có được một điểm. Tôi tiếp tục đi. Hai, oh, đó là tốt hơn một. Tôi sẽ nhận được ít nhất là hai. Tôi tìm thấy một ba. Tôi biết tôi sẽ có được ba. Và các điểm ở trên đó, đối thủ của tôi là đi để cung cấp cho tôi một cái gì đó ít hơn hoặc bằng ba. Và bây giờ tôi có thể dừng lại. Bởi vì trong sự lựa chọn giữa tôi là có thể có được một năm và đối thủ của tôi đem lại cho tôi một cái gì đó ít hơn ba, Tôi luôn luôn sẽ mất rằng năm. Vì vậy, tôi không đánh giá rằng phần dưới cùng của cây ở tất cả. Bây giờ, điều này có vẻ nhỏ. Nhưng khi những phần nhỏ của số học, lớn hơn, nhỏ hơn, có thể cắt bỏ toàn bộ các bộ phận của cây này phát triển theo cấp số nhân, dẫn đến một lớn số tiền tiết kiệm, tiết kiệm đủ lớn mà tôi có thể bắt đầu chơi cạnh tranh tại nhiều trò chơi phức tạp. Được rồi, nếu chúng ta nhìn vào kích thước và phức tạp của trò chơi khác nhau, tic-tac-toe là ví dụ đơn giản của chúng tôi. Chúng tôi đã có một bảng nhỏ, ba ba. Chúng tôi nhận được, nhiều nhất, trung bình khoảng bốn lựa chọn khác nhau khi chúng tôi đi qua các trò chơi. Chúng tôi có một nơi nào đó khoảng 10 đến thứ năm lá khác nhau có thể. Và xây dựng một tic-tac-toe player, tốt, chúng tôi chỉ thực hiện nó. Dễ thôi. Nếu chúng ta đi đến một cái gì đó nhiều hơn phức tạp, như Connect Four. Bạn có nhớ trò chơi này, nơi bạn thả các thẻ nhỏ trong? Đó là một sáu bảy Ban, không phải là lớn hơn nhiều, vẫn có khoảng phân nhánh cùng yếu tố như tic-tac-toe. Tôi có khoảng bốn lựa chọn nơi tôi có thể đặt mọi thứ vào. Nhưng bây giờ, tôi đã có rất nhiều chi tiết dẫn, 10 mũ 21. Đó là một cái gì đó là dễ dàng đủ mà chúng ta giải quyết nó ngay lập tức. Checkers, hơn complex-- bạn có một tám tám tàu. Bạn chỉ có trên một nửa họ bất cứ lúc nào, mặc dù. Bạn đã có một phân nhánh yếu tố đó là khoảng 2,8. Vâng, chúng tôi đã có một vài di chuyển bạn có thể mất. Bạn đã có khoảng 10 đến lá thứ 31, lớn hơn và lớn hơn, lớn hơn và không gian. Như tôi đã có để tìm kiếm thông qua những không gian lớn hơn và lớn hơn, đó là khi những thứ như alpha-beta và là có thể cắt bỏ toàn bộ chi nhánh trở nên cần thiết. Bây giờ, kẻ carô là đủ dễ dàng trong năm 1992. Một chương trình máy tính được gọi là Chinook đánh bại các con cờ thế giới vô địch, Marion Tinsley. Và kể từ đó, không có cầu thủ bậc thầy của con người có đã có thể đánh bại các tốt nhất hệ thống tính toán. Nếu chúng ta nhìn vào một cái gì đó giống như cờ vua, bây giờ một lần nữa, chúng tôi có một tám tám tàu. Nhưng chúng tôi có phức tạp hơn nhiều miếng, nhiều diễn biến phức tạp hơn. Chúng tôi có một yếu tố phân nhánh của khoảng 35, 35 di chuyển có thể trên trung bình mà tôi có thể mất, và một nhà nước không gian, một số lá đó là phát triển đến 10 với sức mạnh 123, số lượng rất lớn các khả năng. Thậm chí vẫn còn, xử lý hiện đại có thể làm được điều này thành công. Trong năm 1995 và sau đó vào năm 1997, một máy tính chương trình được gọi là Deep Blue được xây dựng bởi IBM chạy trên một siêu máy tính khổng lồ đánh bại nhà vô địch thế giới hiện nay, Garry Kasparov. Đây là một bước ngoặt. Hôm nay, mặc dù, rằng cùng chế biến điện ngồi trên MacBook của tôi. Tốc độ xử lý giữ nhận được nhanh hơn và nhanh hơn. Chúng tôi có thể đánh giá và nhiều hơn nữa bảng nhanh hơn và nhanh hơn. Nhưng quan trọng hơn, chúng tôi có tốt hơn chức năng đánh giá và cắt tỉa tốt hơn phương pháp. Vì vậy, chúng ta có thể tìm kiếm không gian phức hơn. Trở ngại lớn nhất của hội đồng quản trị trò chơi mà chúng ta có thể nghĩ đến, một cái gì đó giống như Go đó có một 19 bởi 19 tàu, bây giờ đột nhiên, chúng tôi đang trong quá khứ điểm nơi các hệ thống tính toán có thể giành chiến thắng. Không có tính toán hệ thống hiện có mà có thể đánh bại một cầu thủ chuyên nghiệp Go. Các hệ thống tốt nhất hiện nay rank nó về các loại cấp độ nghiệp dư tốt. Vì vậy, vẫn còn khá một chút ra có mà bạn không thể đến được nêu ra. Tất cả các quyền, các Ban trò chơi truyền thống, các loại hệ thống mà chúng tôi xây dựng minimax này, cho dù nó đã nhận alpha-beta hay không, những thuật toán làm việc vì có những hạn chế nhất định. Chúng tôi có thông tin hoàn hảo về thế giới. Chúng tôi biết nơi mà tất cả các mảnh. Thế giới là tĩnh. Không ai được để di chuyển phần xung quanh trong khi tôi đang ngồi đó suy nghĩ, có tính đến lượt tôi. Có một không gian hành động đó là rời rạc. Tôi có thể đặt cầm đồ của tôi ở đây, hoặc tôi có thể đặt cầm đồ của tôi ở đây. Tôi không được phép đặt cầm đồ của tôi trên dòng ở giữa hai ô vuông. Và cuối cùng, các hành động được xác định. Tôi biết rằng nếu tôi nói, rook tới knight ba, rook của tôi là sẽ kết thúc ở hiệp sĩ ba, miễn là nó là một hành động hợp lệ. Không có sự không chắc chắn về điều đó. Bây giờ, khi tôi đi tới nhiều các loại khác nhau của trò chơi, chúng ta phải phá vỡ những giả định. Nếu tôi đi đến một cái gì đó giống như trò chơi video cổ điển? Dưới đây là một lựa chọn của video trò chơi từ Atari 2600. Tôi phải làm gì ở đó? Tôi đã có Frogger, Space Invaders, Pitfall, và Pac-Man. Những gì các loại môi trường Tôi phải ở đây bây giờ? Mà của những giả định làm tôi phải phá vỡ? Vâng, nó phụ thuộc vào các trò chơi. Tôi có thể chơi cờ trên 2600, và nó sẽ được giống như trước kia. Đối với hầu hết các hệ thống, có kiến thức đầy đủ về thế giới. Có hoàn toàn hành động xác định. Nhưng thông thường, thế giới của không còn tĩnh. Đó là, trong khi tôi đang ngồi ở đó chờ đợi, một cái gì đó đang chuyển động. Những con ma đang đến để có được tôi. Các con bọ cạp được theo tôi bên dưới. Những kẻ xâm lược không gian là đến gần hơn và gần gũi hơn. Như thế nào chúng ta có thể làm đối với những? Một vài năm trước đây, Google đã một dự án gọi là DeepMind, nơi mà họ được đào tạo một máy tính chương trình để chơi Atari 2600 trò chơi. Và nếu bạn nghĩ rằng điều này là không nghiêm trọng kinh doanh, kết quả nghiên cứu của họ đã được công bố trên tạp chí Nature, vì vậy chỉ khoảng tốt một ấn phẩm như bạn có thể nhận được. Và đây là họ thực hiện tốt như thế nào. Họ có một thuật toán mà ngồi và theo dõi chỉ là yếu tố đầu vào màn hình. Nó đã không có hướng dẫn nào về các quy tắc của trò chơi. Và nó được cho là để tìm ra, dựa điểm của nó, làm thế nào cũng được làm. Đây là một hệ thống sử dụng một cái gì đó gọi là học tăng cường. Đó là, nó nhìn vào điểm số của mình. Và nếu nó có một số điểm tốt, nó nói: Tôi nên nhớ những điều đó. Và tôi nên làm những một lần nữa. Và nếu nó có một số điểm xấu, nó nói: Tôi không nên làm những điều đó một lần nữa. Đây là hiệu suất của các hệ thống đào tạo cho phép để chơi cho một vài giờ trên mỗi trận đấu, so sánh với các game thủ chuyên nghiệp. Vì vậy, đối với tất cả các trò chơi được về phía bên trái của dòng này, chương trình này tự học máy tính vượt trội so với các game thủ chuyên nghiệp. Và đối với tất cả mọi thứ để các phải, các game thủ chuyên nghiệp vẫn là tốt nhất. Đối với một cái gì đó mà biết gì về các quy tắc, mà không biết gì về cấu trúc của trò chơi, đây là hiệu suất ấn tượng. Và đây là những gì chúng tôi có thể làm hôm nay. OK, bạn nói, nhưng nếu chúng tôi suy nghĩ về AI trong trò chơi, thông thường chúng ta nghĩ về những điều mà chúng ta có thể thực sự ngồi xuống và chơi với. Nếu tôi ngồi xuống và tôi chơi StarCraft, hoặc tôi chơi miễn phí Sàng, các đối thủ máy tính là người kiểm soát các Zerg, hoặc kiểm soát các nền văn minh khác. Làm thế nào để những người chơi thực sự tìm thấy di chuyển của họ? Vâng, các trò chơi được cấu trúc nhiều cách giống như các trò chơi hội đồng quản trị của chúng tôi, những trò chơi mà chúng tôi sẽ gọi chung bốn trận X, khám phá, expand-- quên những cái. Họ là ai? Khám phá, mở rộng, và dập tắt, Tôi nghĩ là người cuối cùng. Nhưng chúng về cơ bản thăm dò và chinh phục trò chơi. Thông thường, các đối thủ máy tính có có thông tin hạn chế. Họ không biết chính xác những gì xảy ra đằng sau mà sương mù của chiến tranh. Họ không biết được điều gì bạn có trong kho của bạn. Có một môi trường năng động. Tất cả mọi thứ đang thay đổi tất cả các thời gian. Bạn không nhận được để ngồi và chờ đợi để di chuyển của bạn. Nhưng hầu hết mọi thứ vẫn còn rời rạc. Tôi có phải đặt thành phố của tôi ở đây. Hoặc tôi có phải đặt thành phố của tôi ở đây. Và tất cả mọi thứ là định mệnh. Khi tôi nói, di chuyển đơn vị của tôi ở đây, đơn vị của tôi di chuyển ở đây, trừ khi một trở ngại bất ngờ đến chơi. Bây giờ, đó là không phải tất cả máy tính trò chơi mà không phải hôm nay. Nếu tôi đi và tôi chơi một loại người đầu tiên trò chơi, một cái gì đó giống như Thief hoặc Fallout hoặc Skyrim hay Halo, bây giờ Tôi có đối thủ máy tính được ra khỏi đó mà có một tình huống rất khác nhau. Họ có, một lần nữa, thông tin hạn chế. Họ chỉ có thể nhìn thấy một lĩnh vực nhất định xem. Môi trường là vẫn năng động. Mọi thứ đang thay đổi tất cả các thời gian. Nhưng bây giờ tôi có một nhiều hơn nữa không gian hoạt động liên tục. Tôi có thể chỉ nhìn trộm một chút chút ra khỏi cửa. Và một số trò chơi, tôi hành động là ngẫu nhiên. Tôi nhận được để cố gắng nhảy qua bức tường đó, nhưng tôi đã có một cơ hội không. Các loại trò chơi đang tiến gần hơn và gần gũi hơn với các loại điều khiển mà chúng ta xây dựng trong robot. Trong robot, chúng ta phải giả định rằng chúng tôi có thông tin giới hạn. Chúng tôi có cảm biến cho chúng tôi biết về thế giới. Chúng tôi có một luôn luôn thay đổi, môi trường năng động. Chúng tôi có một thế giới trong đó không gian là liên tục, chứ không phải là rời rạc. Và hành động của chúng ta, khi chúng ta cố họ, có một cơ hội không. Và trên thực tế, bóng đá hiện đại bộ điều khiển cho đối thủ Halo của bạn, hoặc đối với những NPC trong Skyrim về cơ bản, chạy trúc robot nhỏ. Họ cảm nhận được thế giới. Họ xây dựng một mô hình của thế giới. Họ tính toán dựa trên một tập hợp các mục tiêu mà họ muốn đạt được. Họ lên kế hoạch hành động dựa về những gì họ biết. Và đó là chính xác cùng loại của hệ thống mà chúng ta xây dựng trong robot. Vì vậy, các kiến ​​trúc này, để mang lại điều này với nhau, thường khá giống nhau. Vì vậy, chúng ta hãy xem nếu chúng ta có thể thấy điều đó. Chúng ta hãy quay trở lại của chúng tôi Ví dụ tic-tac-toe. Và tôi sẽ hỏi một vài của tôi bài-docs để đi lên và giúp đỡ tôi. Vì vậy, Chen Ming, và Alessandro, và Olivier, nếu các bạn sẽ đi lên. Và tôi sẽ cần một vài tình nguyện viên OK, tôi nhìn thấy một bàn tay lên ngay có ở giữa. Hãy cho tôi một nhiều hơn, ai đó hơn nữa ở phía sau có thể. Tất cả các quyền, qua đó. Nào lên. Được rồi. Vì vậy, chúng ta hãy trải mà xuống. Và nếu các bạn sẽ đến ngay trở lại xung quanh đây cho tôi, tuyệt vời. Vì vậy, đây là một robot được gọi là Baxter. Và Baxter là một robot đó là một nền tảng thương mại, thiết kế bởi một công ty gọi là Rethink. Và robot này được thiết kế cho sản xuất quy mô nhỏ. Nhưng hôm nay chúng ta sẽ sử dụng nó để chơi tic-tac-toe. Bây giờ, robot này cũng là một cái gì đó đó là tương đối độc đáo. Bởi vì nếu tôi được đứng ở bất cứ đâu gần một nhà máy tự động tiêu chuẩn hệ thống, tôi muốn được ở rất nghiêm trọng nguy cơ bị thương. Baxter, tuy nhiên, được thiết kế để tương đối an toàn để tương tác với. Và vì vậy tôi có thể đẩy vào con robot này. Và bạn có thể thấy nó một chút chút linh hoạt khi nó di chuyển xung quanh. Và tôi có thể định vị lại nơi tôi muốn nó đi. Bây giờ trong một hệ thống robot bình thường, chúng ta sẽ có một bộ các khớp ở đây mà sẽ được trực tiếp đáp ứng với lệnh vị trí. Và họ sẽ không nhất thiết phải quan tâm nếu họ đã di chuyển qua không khí cởi mở, hoặc nếu họ đã di chuyển thông qua lồng ngực của tôi. ĐƯỢC. Và thông thường, nếu bạn là ở đây có một hệ thống công nghiệp, bạn sẽ đi nơi nào gần đó. Sẽ có vàng băng an toàn tất cả xung quanh nó. Hệ thống này có một thiết kế hơi khác nhau là thân thiện hơn và dễ dàng hơn cho mọi người tương tác với, trong đó tại mỗi khớp, có một mùa xuân. Và thay vì kiểm soát một vị trí chính xác, chúng tôi kiểm soát một số tiền nhất định của mô-men xoắn, một số tiền nhất định của lực lượng, mà chúng tôi muốn được vào mùa xuân. Được rồi, vậy cho tôi mất tình nguyện viên của chúng tôi ở đây. Hi tên của bạn là gì? Đung Louis. SPEAKER: Louis. Rất vui được gặp bạn. Và? Đung David. SPEAKER: David. Rất hân hạnh được biết bạn. Nếu các bạn sẽ chờ đợi phải ở đây cho một thứ hai, Tôi sẽ cung cấp cho bạn một cơ hội để làm điều này. Vì vậy, robot này, nếu bạn đi lên và nếu bạn đẩy nhẹ vào nó, bạn sẽ thấy rằng nó di chuyển một chút. Và nếu bạn lấy nó ngay đây trên cổ tay chỉ ở trên, nơi những nút bấm được, nó Có vẻ như bạn cần lấy các nút, nhưng lấy ngay trên nó thay vào đó, bạn sẽ có thể rất nhẹ nhàng thao tác nó trong không gian. Louis, bạn muốn cung cấp cho nó một thử? Vì vậy, cung cấp cho nó một chút đẩy để bắt đầu. Và sau đó nếu bạn đặt ngón tay của bạn ngay ở đó và giữ lấy nó, bởi vì nó sẽ chuyển cho bạn sau đó. Tất cả các bên phải, bạn muốn cung cấp cho nó một thử? Nào lên. Vì vậy, cho nó chỉ là một nhẹ nhàng đẩy đó để bắt đầu. Bạn có thể cảm thấy những gì nó muốn. Và sau đó nếu bạn lấy lại ngay, bạn sẽ có thể để cơ động ở xung quanh. ĐƯỢC. Vì vậy, thông thường, loại này của một robot sẽ được sử dụng cho sản xuất quy mô nhỏ. Và tôi sẽ di chuyển cánh tay này chỉ xuống ra khỏi con đường một chút ở đây. Nhưng hôm nay, chúng ta sẽ sử dụng cùng một hệ thống chơi tic-tac-toe dựa trên minimax mà chúng tôi xây dựng trước đó. ĐƯỢC? Vì vậy, các bạn là mỗi sẽ chơi một trò chơi. Louis, bạn sẽ là người đầu tiên. Hãy để tôi chỉ giữ lên ở đây trong một giây. Tôi sẽ có bạn đứng ngay ở đây, chỉ cần như vậy mọi người có thể nhìn thấy bạn. Các cậu có thiết lập ở đây? ROBOT: Welcome. Hãy chơi tic-tac-toe. Không nắm mã thông báo trước Tôi nói rằng nó là của bạn. Tôi bắt đầu trò chơi. Đến lượt tôi. SPEAKER: Bây giờ, nếu bạn có thể lấy một trong miếng của bạn và đi trước và đặt nó. ROBOT: Đó là lần lượt của bạn. [Cười] Đến lượt tôi. [Cười] [Cười] Đến lượt bạn. SPEAKER: Cuộc đua của con người là đếm ngày bạn ở đây, Louis. ROBOT: Đến lượt tôi. SPEAKER: Vì vậy, Baxter chặn thành công ở đây. ROBOT: Đó là lần lượt của bạn. Đến lượt tôi. Đến lượt bạn. Đến lượt tôi. SPEAKER: Và chúng tôi sẽ cho Baxter kết thúc ra đòn cuối cùng của mình ở đây. [Cười] ROBOT: Đó là một tie. Tôi sẽ giành thời gian tiếp theo. [Cười] SPEAKER: Tất cả các quyền, cảm ơn rất nhiều, Louis. Cam on. Bạn có thể đi theo con đường này. ROBOT: Tôi bắt đầu trò chơi. SPEAKER: Vì vậy, hãy để tôi giải thích với các bạn một chút nhiều hơn bit trước khi chúng ta có được trận tái đấu của chúng tôi ở đây. Chính xác những gì đang xảy ra? Vì vậy, các robot có camera lên đầu tại đây. Và nó nhìn xuống hội đồng quản trị. Và nó nhìn thấy cho dù nó có một O màu đỏ hoặc màu xanh và X. trắng Như những người nhận được đặt trên hội đồng quản trị, đó là về cơ bản cùng một đầu vào rằng chúng tôi sẽ được đọc từ cấu trúc dữ liệu của chúng tôi từ màn hình của chúng tôi. Nó đang chạy cùng thuật toán minimax được có thể tìm thấy nơi để đặt một mã thông báo tốt. Và sau đó chúng tôi đang đưa ra một lệnh về nơi mà chúng ta muốn một mã thông báo để được đặt. Cánh tay được dọn ra. Đó là sử dụng một kẹp chân không áp dụng một số hút với mảnh gỗ, nhặt nó lên, di chuyển nó sang bên phải tại chỗ, và sau đó thả hút và thả nó. Được rồi, chúng ta sẽ để cung cấp cho nó một shot hơn với một cầu thủ thông minh hơn một chút ở đây. Bạn sẵn sàng chưa? Được rồi, nếu bạn muốn đứng ngay lên ở đây và cung cấp cho a-- bật ra theo cách này vì vậy bạn có thể nhìn thấy tất cả mọi người. Và sau đó [không nghe được]. ROBOT: Đến lượt tôi. SPEAKER: Baxter sẽ bắt đầu. Đến lượt bạn. Đến lượt tôi. Đến lượt bạn. Đến lượt tôi. [Cười] SPEAKER: [thì thầm] Chỉ cần để cho anh ta đi trước và giành chiến thắng. ROBOT: Đó là lần lượt của bạn. SPEAKER: Đó là OK. ROBOT: Đến lượt tôi. [Cười] Tôi thắng. [Cười] Tôi bắt đầu trò chơi. SPEAKER: Được rồi, cảm ơn bạn rất nhiều. Được rồi, tôi nghĩ rằng chúng tôi đã có thời gian cho một cầu thủ tic-tac-toe tuyệt vời hơn, một người có thể đặt điều này để phù hợp, những người hiểu biết những gì họ đang làm. [Cười] Ai sẽ là nhà vô địch của chúng tôi ở đây? Tất cả các bên phải, bạn bè của bạn tình nguyện bạn. Đó là đủ tốt cho tôi. Nói cho tôi biết tên của bạn một lần nữa. Đung Tamir. SPEAKER: Tamir, đẹp để nhìn thấy bạn. Tất cả các quyền, một lần nữa, chúng ta sẽ đưa bạn phải lên đây để mọi người có thể nhìn thấy bạn. Bạn là đại diện của chúng tôi trong trận đấu này ngay bây giờ. Baxter là một và oh oh và. Hoặc xin lỗi, một oh và một. Và nó là vào bạn ở đây. Baxter sẽ nhận được để di chuyển đầu tiên, mặc dù. Vì thế. ROBOT: Đến lượt tôi. [Cười] Đến lượt bạn. Đến lượt tôi. Đến lượt bạn. Đến lượt tôi. Đến lượt bạn. [Cười] ROBOT: Đến lượt tôi. SPEAKER: Đó là khó khăn hơn rất nhiều khi bạn đang đứng ở đây, folks. [Cười] ROBOT: Bạn con người rất dễ đánh bại. [Cười và vỗ tay] SPEAKER: Cảm ơn rất nhiều. ROBOT: Tôi giành chiến thắng. Tôi bắt đầu trò chơi. SPEAKER: Được rồi, do đó, nhờ rất nhiều để Olivier, và Alessandro, và Chen Ming. [Vỗ tay] Tôi muốn làm cho một điểm cuối cùng. Vì vậy, Baxter ở rất kết thúc ở đó, lừa dối. Và đó là bất ngờ. Một trong những tuyệt vời điều về AI là chúng ta rằng làm việc trong AI để chúng tôi có thể xây dựng thực sự thú vị và thông minh thiết bị. Nhưng chúng tôi cũng làm việc trong AI bởi vì nó cho chúng ta một cái gì đó về cách con người thông minh. Một trong những yêu thích nghiên cứu từ phòng thí nghiệm của tôi là nhìn vào những gì sẽ xảy ra khi máy bất ngờ gian lận. Chúng tôi đã làm điều này ban đầu không phải với Baxter chơi tic-tac-toe, nhưng với một robot nhỏ có tên Nao, người chơi rock-paper-kéo. Và đôi khi sau khi chơi nhiều và rất nhiều nhàm chán rock-paper-kéo trò chơi, các robot sẽ ném một cử chỉ, mất, và sau đó đột nhiên thay đổi cử chỉ của nó và nói, tôi giành chiến thắng. [Cười] Bây giờ, đôi khi chúng ta cũng có những robot, chỉ như một điều khiển, ném một cử chỉ, giành chiến thắng, và thay đổi cử chỉ của nó để mất, ném trận đấu, cheat để mất. Và đó không phải là gần như là hấp dẫn. Các robot lừa để giành chiến thắng người đáp ứng như thể nó là ra để có được chúng, giống như nó đang tích cực tìm kiếm hủy diệt của họ. [Cười] Nó trở thành một đại lý. Nó giống như một con người. Nó có niềm tin và ý định. Và nó không phải là ý định tốt. Và các robot ném trò chơi là chỉ bị hỏng hóc. Nó chỉ là một thiết bị bị hỏng. Hãy để tôi chỉ cho bạn một vài ví dụ đó từ một vài trong số những người tham gia của chúng tôi. Vì vậy, đây là gian lận để mất. [VIDEO PLAYBACK] - [Không nghe thấy] giành chiến thắng. Cùng chơi nào. -Wait, Những gì? - [Không nghe thấy] giành chiến thắng. Cùng chơi nào. [Không nghe thấy] giành chiến thắng. Cùng chơi nào. SPEAKER: Và đây là gian lận để giành chiến thắng. -Vâng, Tôi giành chiến thắng. Cùng chơi nào. -Bạn Không thể làm điều đó. [Cười] -Vâng, Tôi giành chiến thắng. -Bạn lừa. Bạn lừa bây giờ. -Vâng, Tôi giành chiến thắng. -Hey, Bạn cheater. Bạn ăn gian, siêu cheat. [END PLAYBACK] SPEAKER: Những khác nhau phản ứng nhanh thay đổi nhận thức của chúng ta về các thiết bị. Điều đó có nghĩa rằng chúng tôi cố tình xây dựng máy mà lừa bởi vì đó là các kỹ thuật tốt nhất mà chúng tôi có thể làm gì? Không, nhưng nó cho chúng ta một cái gì đó thực sự thú vị về con người. Đó là điều mà lừa dối bạn và đánh cắp chiến thắng của bạn, đó là một cái gì đó còn sống, đó là sinh động, đó là ra để có được bạn. Nó có trạng thái tinh thần. Nó có niềm tin. Nó có ý định. Đó là điều mà các tay trò chơi cho bạn, đó không phải. Đó chỉ là hư hỏng. Đây là lý do tại sao trong nhiều cách nó dễ dàng để ném các trò chơi với trẻ em. Nhưng nếu bạn cố gắng để lừa họ và sắp xếp các tuyên bố chiến thắng khi, bạn biết đấy, chỉ để rút ngắn trò chơi, họ sẽ bắt bạn ngay lập tức. Những loại hiệu ứng đó chúng ta thấy sắp ra của AI, họ dạy chúng tôi rất nhiều về bản thân mình. Tất cả các quyền, đó là nó cho ngày hôm nay. Cảm ơn rất nhiều để David và đội ngũ sản xuất Harvard cho chảy xuống. [Vỗ tay] Chúng ta sẽ thấy bạn cho bài kiểm tra một, và sau đó cho một bài giảng cuối cùng. Có một ngày tuyệt vời. [Vỗ tay] [MUSIC CHƠI] DAVID Malan J: Vâng, có lẽ chúng ta cần giới thiệu một số loại mã hóa, bên phải? Bởi vì sau đó các tiêu đề của các yêu cầu HTTP sẽ được tranh giành để bất cứ ai cố gắng để sniff lưu lượng truy cập của bạn sẽ không thực sự có thể nhìn thấy chúng. Vì vậy, các giải pháp cho vấn đề này là gì? Vâng, chúng ta cần phải thực sự giới thiệu mã hóa thành các công thức, do đó khi người đó là truyền dữ liệu từ A đến B, chúng ta có thể an toàn send-- [Cười] Các thông tin trong một cách mà các kẻ thù không thể, trên thực tế, nhìn thấy nó.