paint-brush
Trên máy chơi: Lịch sử của AI và trò chơitừ tác giả@samin
1,225 lượt đọc
1,225 lượt đọc

Trên máy chơi: Lịch sử của AI và trò chơi

từ tác giả Shreya Amin1m2022/06/26
Read on Terminal Reader
Read this story w/o Javascript

dài quá đọc không nổi

Loạt bài này bao gồm lịch sử của Trí tuệ nhân tạo và trò chơi (cho đến Deep Blue) và tập trung vào các máy chơi cờ vua, cờ caro và cờ hậu. Nó cũng hỏi (và cố gắng trả lời) những câu hỏi sau: Trò chơi lý tưởng là gì? Tại sao chúng ta quan tâm đến trí tuệ nhân tạo (AI) và trò chơi? Khi đó, đối với con người chúng ta, điều gì sẽ khiến một trò chơi trở nên lý tưởng? Một trò chơi lý tưởng sẽ liên quan đến việc người chơi nhận ra những khao khát sâu sắc nhất trong cuộc đời, niềm đam mê hoặc giá trị của mình. Và thông qua hành trình của mình, anh ấy sẽ tạo ra một con đường để những người khác phát triển và nhận ra tiềm năng của họ, trở thành tất cả những gì anh ấy có thể.

People Mentioned

Mention Thumbnail
Mention Thumbnail

Companies Mentioned

Mention Thumbnail
Mention Thumbnail
featured image - Trên máy chơi: Lịch sử của AI và trò chơi
Shreya Amin HackerNoon profile picture

Series Machines That Play đã bị chia thành 7 phần.


Loạt bài này bao gồm lịch sử của Trí tuệ nhân tạo và các trò chơi (cho đến Deep Blue) và tập trung vào các máy chơi cờ vua, cờ caro và cờ hậu. Các chủ đề sau đây được đề cập đến: cách chế tạo máy chơi cờ, công việc của Shannon về cờ vua, công việc của Turing về cờ vua, The Turk, El Ajedrecista, MANIAC, chương trình cờ Bernstein, cờ của Samuel, Mac Hack VI, Cray Blitz, BKG, HiTech, Chinook, Deep Thought, TD-Gammon và Deep Blue.


  • Phần 1: Máy chơi được (Tổng quan) - phần này
  • Phần 2: Máy chơi (Chế tạo máy chơi cờ)
  • Phần 3: Máy chơi (Cờ vua trước Deep Blue)
  • Phần 4: Máy chơi (Deep Blue)
  • Phần 5: Máy chơi (Post Deep Blue)
  • Phần 6: Máy chơi (Cờ caro)
  • Phần 7: Máy chơi (Backgammon)

Phần 1: Máy chơi được (Tổng quan)

Đây là Phần 1 của loạt bài và giới thiệu tổng quan về những nỗ lực của AI liên quan đến các trò chơi: cờ vua, cờ caro, cờ hậu bị. Nó cũng hỏi (và cố gắng trả lời) những câu hỏi sau: Thế nào là một trò chơi lý tưởng? Tại sao chúng ta quan tâm đến trí tuệ nhân tạo (AI) và trò chơi?

Trước khi nói về trò chơi và máy móc, trước tiên hãy nói về trò chơi và con người.

Một trò chơi lý tưởng là gì?

Một trò chơi là một cái gì đó có các quy tắc và một mục tiêu. Chúng tôi “chơi” một trò chơi khi chúng tôi thực hiện các hành động, bị ràng buộc bởi các quy tắc này, để đạt được mục tiêu đã thiết lập.

Chúng ta (con người) dường như cần chơi nhiều như chúng ta cần thức ăn, nước uống, không khí, nơi ở và các công cụ để tồn tại. Khi đó, đối với con người chúng ta, điều gì sẽ khiến một trò chơi trở nên lý tưởng? Đây là một câu hỏi khó trả lời, nhưng tôi tưởng tượng rằng một trò chơi lý tưởng có thể có ít nhất một số đặc điểm sau:


  • Trò chơi trong đó tất cả người chơi đều có kỹ năng cao (hoặc ở các cấp độ tương tự) : Trò chơi trong đó người chơi có thể sử dụng kỹ năng của mình để vượt qua thử thách mà (các) đối thủ đưa ra. Niềm vui lý tưởng nằm ở việc sử dụng kỹ năng của mình để vượt qua hoặc qua mặt một đối thủ cũng rất giỏi trong trò chơi.
  • Một trò chơi không quá dễ, cũng không quá khó để người chơi “chỉ cần thắng” : Trò chơi trong đó một người chơi đánh bại (các) đối thủ của mình, người cũng có thành tích gần với cấp độ kỹ năng của mình. Đó là một trò chơi mà anh ấy có thể thua, nhưng không thua. Anh ấy thắng. Và anh ấy thắng vì trò chơi cho phép anh ấy tăng chỉ hơn (các) đối thủ một chút; anh ta chinh phục các yếu tố may rủi và thực hiện quyền kiểm soát đối với môi trường của mình (và bản thân).
  • Trò chơi buộc người chơi phải phát triển và đạt được tiềm năng cao nhất của mình để giành chiến thắng : Trò chơi trong đó người chơi phát triển các kỹ năng cao nhất để vượt trội hoặc vượt trội hơn đối thủ của mình. Sự phát triển lý tưởng có nghĩa là anh ta có thể nhận ra tiềm năng của mình, trở thành tất cả những gì anh ta có thể là. Anh ta phát triển kỹ năng tuyệt vời đến mức nguy cơ thất bại gần như bị loại bỏ.
  • Trò chơi thay đổi tâm lý của người chơi : Một trò chơi làm thay đổi trạng thái tâm trí của người chơi và ngoài việc nhận ra tiềm năng cao nhất của anh ta, trò chơi còn cho phép anh ta đắm mình hoàn toàn để đạt được thành công. Đó là một trò chơi mà anh ấy sẽ chọn để tiếp tục chơi miễn là anh ấy có thể để anh ấy có thể hoàn thành (điều mà sau này anh ấy gọi là) những hành động có ý nghĩa. Và sau trận đấu, anh ấy sẽ nhận thấy rằng anh ấy đã thay đổi từ trải nghiệm chơi trò chơi và tâm trí của anh ấy đã được bổ sung thêm các kỹ năng mới, kinh nghiệm mới và thành tích mới.
  • Một trò chơi buộc người chơi trở thành chất xúc tác cho sự thay đổi toàn cầu (hãy nhớ đây là một trò chơi lý tưởng): Một trò chơi trong đó người chơi cần phải biến đổi (hoặc thậm chí siêu việt) bản thân, những người khác hoặc thậm chí toàn bộ thế giới ở mức tối đa Để giành chiến thắng. Một trò chơi lý tưởng sẽ liên quan đến việc người chơi nhận ra những khao khát, đam mê hoặc giá trị sâu sắc nhất của mình (và cả con người). Nếu không phải là điều này, thì trò chơi ít nhất sẽ tiêu thụ anh ta sâu sắc đến mức giải thoát anh ta khỏi xiềng xích của cuộc sống hàng ngày của anh ta. Và thông qua hành trình của mình, anh ấy sẽ tạo ra một con đường để những người khác phát triển và nhận ra tiềm năng của họ.

Có một trò chơi lý tưởng?

Tôi không biết liệu có một trò chơi lý tưởng hay không, nhưng, theo ý kiến của tôi, ví dụ sau đây khá gần với việc trở thành một trò chơi; nó không chỉ thỏa mãn nhiều đặc điểm được liệt kê trước đó, mà còn thách thức và làm mờ đi những đặc điểm tương tự đó.

Con dấu thứ bảy của Ingmar Bergman

[Video clip] Điều kiện là anh cho tôi sống bao lâu tôi còn có thể chống lại anh.


Death: Chà, tôi là một người chơi cờ khá điêu luyện.

Knight: Nhưng tôi cá là bạn không giỏi bằng tôi.

Tử thần: Tại sao lại muốn ta đánh cờ với ta?

Knight: Đó là việc của tôi.

Cái chết: Thật vậy.

Hiệp sĩ: Điều kiện là anh để tôi sống chừng nào tôi còn có thể chống lại anh.

Hiệp sĩ: Nếu tôi thắng, bạn để tôi đi.


Người chơi chọn chơi miễn là anh ta còn sống (hoặc có thể). Tiền đặt cược quá cao và anh ấy không thể không cố gắng.


[Video clip] Đây là bàn tay của tôi. Tôi có thể biến nó. Máu tôi chảy ra trong đó. Trời vẫn còn nắng và gió vẫn thổi. Và tôi… tôi, Antonius Block, đang chơi cờ với Ác quỷ.


Chúng tôi không bao giờ đấu với Thần chết (và gần như chiến thắng). Hành động của chúng ta, trong hầu hết các trò chơi, gần như không “có ý nghĩa” như việc cứu mạng người khác. Trò chơi của chúng tôi không cho chúng tôi cơ hội đối mặt với sự tuyệt vọng không thể tránh khỏi của chúng tôi cũng như không thể biến đổi hoàn toàn (hoặc vượt lên) bản thân hoặc cuộc sống của người khác.


Trong thực tế có lẽ không có trò chơi lý tưởng. Tại sao chúng ta vẫn chơi sau đó? Một câu trả lời mơ hồ và đơn giản là “vì trò chơi rất vui và / hoặc hữu ích”, nhưng điều đó dường như là chưa đủ. Chúng tôi tiếp tục tạo và chơi trò chơi và chúng tôi tiếp tục vì các trò chơi vẫn thể hiện sự kết hợp khác nhau của các đặc điểm đã nêu ở trên.

Một số trò chơi lâu đời nhất của chúng tôi

Chúng tôi luôn chơi trò chơi. Trò chơi là một trong những nguồn chơi lâu đời nhất của chúng tôi. Có thể trước đó con người đã chơi trò chơi để luyện tập các kỹ năng chuẩn bị cho việc săn bắn và chiến đấu. Ví dụ, cung tên được phát minh vào cuối thời kỳ đồ đá cũ trên .


Bắn cung là kỹ năng sử dụng cung để bắn tên. Trong hầu hết các nền văn hóa thời tiền sử, bắn cung là một kỹ năng quân sự và săn bắn quan trọng. Thực hành bắn cung (hoặc chơi để luyện tập hoặc cải thiện) sẽ cải thiện xác suất thành công của người bắn cung. Theo nghĩa này, những trò chơi vật lý như vậy có thể đã được chơi để tăng cơ hội sống sót và thành công của chúng ta.


Sau đó, con người bắt đầu định cư ở một nơi, có nghĩa là họ không di chuyển nhiều nữa. Điều này đã tạo cho họ một số trò chơi thường ngày và các trò chơi thể chất bắt đầu chuyển sang trò chơi trên bàn. Những trò chơi này khai thác vào nhiều mong muốn của chúng tôi. Một số trò chơi lâu đời nhất là:


  • Senet (~ 3100 TCN): Tên đầy đủ của trò chơi bảng đua này có nghĩa là "trò chơi vượt qua". Người Ai Cập cổ đại tin vào thế giới bên kia và cuộc hành trình sang thế giới bên kia yêu cầu người đã chết thực hiện các nghi lễ và vượt qua các chướng ngại vật. Vào thời Tân Vương quốc ở Ai Cập, senet được xem như một đại diện cho cuộc hành trình sang thế giới bên kia. Có vẻ như senet không chỉ là một trò chơi, nó đại diện cho cuộc đấu tranh của chúng tôi để đạt được sự bất tử. [Những trò chơi kiểu này đánh vào mong muốn bẩm sinh của chúng ta để tồn tại ngoài trạng thái con người này.]
  • Royal Game of Ur (~ 3000 năm trước Công nguyên): Đây là một trò chơi trên bàn đua chiến lược hai người chơi. Game of Ur nhận được tên gọi của nó vì nó được phát hiện bởi nhà khảo cổ học người Anh, Sir Leonard Woolley trong cuộc khai quật Nghĩa trang Hoàng gia tại Ur từ năm 1922 đến năm 1934. Tại một số thời điểm, mọi người bắt đầu gắn ý nghĩa tâm linh vào trò chơi và các sự kiện trong trò chơi được cho là sẽ phản ánh tương lai của người chơi cũng như truyền tải thông điệp từ những đấng siêu nhiên. [Các trò chơi kiểu này khai thác vào khao khát được biết và kiểm soát tương lai của chúng ta.]
  • Mancala (~ thế kỷ thứ 6 sau Công Nguyên): Mancala không phải là bất kỳ trò chơi nào, nó là phân loại hoặc loại trò chơi: bất kỳ trò chơi bảng chiến lược theo lượt 2 người chơi nào. Mục đích là để bắt tất cả hoặc một số bộ quân cờ của đối thủ (hạt giống, đá, đậu, v.v.). [Các trò chơi kiểu này đánh vào mong muốn tồn tại từ xa xưa của chúng ta bằng cách xây dựng nơi trú ẩn, săn bắn, thu thập thức ăn và chiến thắng.]


Chúng tôi đã chơi (và tiếp tục chơi) trò chơi vì nhiều lý do:

  • Chúng tôi chơi để trải nghiệm niềm vui (niềm vui)
  • Chúng tôi chơi để loại bỏ sự nhàm chán / để thoát khỏi thực tế
  • Chúng tôi chơi để luyện tập và nâng cao kỹ năng
  • Chúng tôi chơi để học cách suy nghĩ chín chắn và chiến lược
  • Chúng tôi chơi để chinh phục sự không chắc chắn, cơ hội, may mắn và xác suất
  • Chúng tôi chơi để chơi để tạo ra mọi thứ để trao quyền cho bản thân.
  • Chúng tôi chơi để phá hủy mọi thứ để giảm bớt sự tức giận và thất vọng của chúng tôi
  • Chúng tôi chơi để giải quyết sự khác biệt
  • Chúng tôi chơi để cộng tác
  • Chúng tôi chơi để đáp ứng tất cả mong muốn của con người (thời tiền sử và hiện tại): nuôi dưỡng, săn bắn, giết người, chinh phục, chiến đấu, cạnh tranh, cộng tác, sáng tạo, tồn tại
  • Chúng tôi chơi để giành chiến thắng - để cảm thấy một cảm giác thành tựu


Trong suốt lịch sử, chúng tôi đã tạo và chơi các trò chơi để thử thách trí thông minh, sức mạnh, chiến lược, cảm xúc và hơn thế nữa. Trong trò chơi, chúng tôi đến với nhau và đồng ý với một bộ quy tắc tùy ý. Chúng tôi cạnh tranh và hợp tác, chúng tôi lập chiến lược để chinh phục cơ hội và sự không chắc chắn, chúng tôi đặt ra và đạt được mục tiêu, chúng tôi thực hiện trí tưởng tượng và trải nghiệm niềm vui thành công.

Tại sao lại là AI và trò chơi?

Trò chơi là khó. Trò chơi là thú vị. Trò chơi là giường thử nghiệm cho AI.

Khi công nghệ phát triển, trò chơi của chúng tôi cũng vậy. Công nghệ gần đây đã cung cấp cho chúng ta những đồng đội mới cũng như những đối thủ mới, dưới dạng máy móc. Mặc dù lịch sử của trò chơi rất hấp dẫn, chúng tôi sẽ tập trung vào tự động hóa, trí tuệ nhân tạo (AI) và các trò chơi trong loạt trò chơi này. Cụ thể hơn, chúng tôi sẽ tập trung vào các trò chơi mà AI đã học cách chơi tốt như chúng tôi hoặc tốt hơn. Cuộc hành trình này sẽ trở thành một lời nhắc nhở khiêm tốn:


Bất kể tốc độ cải tiến đối với con người là bao nhiêu, một khi máy móc bắt đầu học hỏi, chúng ta sẽ khó theo kịp chúng - quá trình học tập và tiến bộ của chúng sẽ được đo lường theo cấp số nhân. Và của chúng tôi sẽ không.


Kể từ những ngày đầu tiên của máy tính, mọi người đã tự hỏi liệu máy móc có thể sánh ngang hoặc vượt qua trí thông minh của con người hay không. Trí tuệ nhân tạo là việc xây dựng những cỗ máy có thể thực hiện các nhiệm vụ mà (chúng tôi nghĩ) yêu cầu "trí thông minh". Nhưng các phương pháp tiếp cận và thuật toán AI trước đây không đủ để giải quyết các vấn đề trong thế giới thực vì bản chất phức tạp và không rõ ràng của chúng. Lập trình máy để chơi trò chơi thành công là một cách để máy tính học các chiến thuật và chiến lược mà sau này có thể được áp dụng cho các lĩnh vực đời thực khác.


Mô phỏng quá trình suy nghĩ của con người trong trò chơi

Các nhà nghiên cứu AI ban đầu nhấn mạnh việc mô phỏng quá trình suy nghĩ của con người trong các trò chơi vì họ tin rằng những cỗ máy chơi trò chơi tốt nhất có thể được tạo ra bằng cách dạy chúng cách bắt chước suy nghĩ của con người. Họ lý luận rằng nếu máy móc có thể giải quyết trò chơi thành công thì rất có thể chúng sẽ thể hiện một loại trí thông minh nào đó.


Hiểu cách trí óc con người hoạt động

Các nhà nghiên cứu AI ban đầu hy vọng rằng việc lập trình máy để chơi trò chơi thành công sẽ giúp hiểu được cách thức hoạt động của bộ óc con người, cách nó suy nghĩ, cách nó giải quyết vấn đề và cuối cùng là trí thông minh là gì. Họ cho rằng việc chế tạo máy móc để thực hiện các nhiệm vụ đòi hỏi trí thông minh sẽ cung cấp cái nhìn sơ lược về cách thức hoạt động của trí thông minh của chúng ta.


Chúng ta sẽ thấy rằng ngay cả khi máy móc vượt qua con người trong các trò chơi, chúng không nhất thiết phải cung cấp cái nhìn sâu sắc về hoạt động của tâm trí chúng ta. Tuy nhiên, họ đã giúp thúc đẩy tiến bộ trong khoa học máy tính (và do đó là các lĩnh vực liên quan khác). Và sau đó, nghiên cứu đã giúp chúng tôi giải quyết một số vấn đề phức tạp trong thế giới thực.


“Các trò chơi rất vui và dễ đo lường. Rõ ràng ai thắng ai thua, và bạn luôn có chuẩn mực của con người… Bạn có thể làm tốt hơn con người không? ” Murray Campbell


Trò chơi, cụ thể là trò chơi trên bàn cờ, là một trong những nhánh lâu đời nhất của AI, bắt đầu với Shannon và Turing 1950. Họ đã cung cấp một cách tốt để đo lường năng lực của các ý tưởng AI vì 1) tính đơn giản của chúng về khách quan, 2) các quy tắc được xác định rõ ràng và 3) một loạt các chiến lược khả thi để đạt được mục tiêu cuối cùng. Mỗi khi AI chinh phục một trò chơi, nó giúp chúng ta giải quyết ít nhất một số vấn đề phức tạp trong thế giới thực.

Độ phức tạp của trò chơi

Trước khi bắt đầu, hãy xem một số cách để đo độ phức tạp của trò chơi .


Độ phức tạp của không gian-trạng thái của trò chơi là số lượng vị trí trò chơi hợp pháp có thể đạt được từ vị trí ban đầu của trò chơi.


Kích thước cây trò chơi là tổng số trò chơi có thể chơi được: số nút lá trong cây trò chơi mọc rễ tại vị trí ban đầu của trò chơi.


Yếu tố phân nhánh là số lượng nút con ở mỗi nút. Ví dụ, cờ vua, giả sử rằng một "nút" được coi là một vị trí hợp pháp, thì hệ số phân nhánh trung bình được ước tính là khoảng 35. Điều này có nghĩa là trung bình một người chơi có khoảng 35 nước đi hợp pháp ở mỗi lượt. Để so sánh, hệ số phân nhánh trung bình cho trò chơi cờ vây là 250!


Trạng thái tối ưu : không thể hoạt động tốt hơn (một số mục này do con người giải quyết)


Siêu nhân : hoạt động tốt hơn tất cả con người


Độ phức tạp của một số trò chơi


Bây giờ, hãy nói về máy móc.


Loạt blog sẽ bao gồm các chủ đề sau. Liên kết đến hình ảnh có trong blog gốc.

Trọng tâm của loạt bài này là về một số “cái đầu tiên” trong AI và trò chơi (và đôi khi là một số cái trước của những chương trình đó), chứ không phải bao gồm * tất cả * hoặc * càng nhiều càng tốt * các chương trình trò chơi.

Xây dựng máy chơi cờ vua

Chúng ta thường chơi trò chơi này như thế nào? Chúng tôi làm như sau:

  1. Xem xét tất cả các nước đi hợp pháp mà người chơi có thể thực hiện
  2. Tính toán vị trí mới có được từ mỗi lần di chuyển
  3. Đánh giá để xác định nước đi tốt nhất tiếp theo
  4. Thực hiện điều đó (tốt nhất)
  5. Chờ đối thủ ra tay
  6. Trả lời bằng cách lặp lại các bước trên

Từ góc độ này, hầu như tất cả các máy tính chơi cờ vua đều phải xử lý các bước cơ bản này. Và để làm điều đó, một máy tính chơi cờ vua sẽ phải giải quyết các vấn đề chính sau:

  1. Đại diện cho "hội đồng quản trị"
  2. Tạo tất cả các trạng thái tiếp theo hợp pháp
  3. Đánh giá một vị trí

HowStuffWorks

Có hai cách tiếp cận triết học chính để phát triển máy tính chơi cờ vua: giả lập so với kỹ thuật - máy tính có nên mô phỏng kiến thức của con người và ra quyết định hay máy tính nên cải thiện tìm kiếm thông qua vũ lực? Những người tập trung vào cách tiếp cận đầu tiên sẽ xây dựng các chương trình có nhiều kiến thức về cờ vua và tập trung vào tìm kiếm tương đối nhỏ hơn. Những người tập trung vào cách tiếp cận kỹ thuật sẽ tập trung vào sức mạnh tính toán, bằng cách sử dụng phần cứng có mục đích đặc biệt và các đổi mới tìm kiếm. Chúng ta sẽ thấy rằng các máy tính chơi cờ vua tốt nhất đã sử dụng cách tiếp cận thứ hai, nhưng thậm chí chúng vẫn sử dụng rất nhiều kiến thức cờ vua và các kinh nghiệm đánh giá phức tạp.

Đọc thêm…

Chỉ con người (The Turk)

  • Trò chơi: Cờ vua. Năm: 1770
  • Vào mùa xuân năm 1770, Wolfgang von Kempelen đã tạo ra một cảm giác; ông đã giới thiệu chiếc ô tô tự động chơi cờ đầu tiên trên thế giới, cái mà ông gọi là kỳ thủ Cờ vua tự động, được biết đến trong thời hiện đại với cái tên The Turk.

Đọc thêm


The Turk (https://upload.wikimedia.org/wikipedia/commons/d/d2/Turk-engraving4.jpg)

Một nỗ lực trung thực hơn (El Ajedrecista (Người chơi cờ))

  • Trò chơi: Cờ vua. Năm: 1910s
  • Vào đầu những năm 1910, Torres y Quevedo đã chế tạo một máy tính tự động gọi là El Ajedrecista (Người chơi cờ vua), ra mắt lần đầu tiên tại Đại học Paris vào năm 1914. Nó được coi là một trong những trò chơi máy tính đầu tiên trên thế giới.

Đọc thêm

Torres y Quevedo xây dựng El Ajedrecista (Kỳ thủ cờ vua)

Một số lý thuyết về trò chơi

  • Nhiều trò chơi: cờ vua , cờ caro , cờ vây , othello . Năm: 1928–1944.
  • John von Neumann thành lập lĩnh vực lý thuyết trò chơi. Năm 1928, ông chứng minh định lý minimax. Định lý này nói rằng trong các trò chơi có tổng bằng không (tức là nếu một người chơi thắng, thì người chơi kia thua) với thông tin hoàn hảo (tức là trong đó người chơi biết, tại mỗi thời điểm, tất cả các nước đi đã diễn ra cho đến nay), có một cặp chiến lược cho cả hai người chơi cho phép mỗi người giảm thiểu tổn thất tối đa của mình, do đó có tên là minimax.

Từ những năm 1940 đến đầu những năm 1950, những người tiên phong đầu tiên tập trung vào việc chế tạo những cỗ máy có thể chơi cờ giống như con người, do đó, sự tiến bộ của cờ vua ban đầu chủ yếu dựa vào kinh nghiệm cờ vua (quy tắc ngón tay cái) để chọn ra nước đi tốt nhất. Họ nhấn mạnh việc mô phỏng quá trình suy nghĩ cờ vua của con người vì họ tin rằng việc dạy một cỗ máy cách bắt chước suy nghĩ của con người sẽ tạo ra những cỗ máy chơi cờ tốt nhất.

Các cỗ máy trong tương lai sẽ chơi cờ như thế nào

  • Trò chơi: cờ vua. Năm: 1950.
  • Bắt đầu từ giữa những năm 1940, các nhà khoa học từ các lĩnh vực khác nhau (toán học, tâm lý học, kỹ thuật, v.v.) đã bắt đầu thảo luận về khả năng tạo ra một cỗ máy có thể suy nghĩ, một cỗ máy có thể cạnh tranh hoặc thậm chí vượt qua con người trong nhận dạng khuôn mẫu, tính toán, giải quyết vấn đề. và thậm chí cả ngôn ngữ. Claude Shannon đã viết bài báo đầu tiên được xuất bản về lập trình máy tính để chơi cờ vua. Ông đã xuất bản một bài báo trên Tạp chí Triết học với tựa đề Lập trình máy tính để chơi cờ vua.

Đọc thêm

Claude Shannon trình diễn một ô tô tự động chơi cờ mà ông đã chế tạo cho phiên bản giới hạn của cờ vua, cho nhà vô địch cờ vua Edward Laske


Sức mạnh máy tính bị hạn chế vào những năm 1950 nên máy móc chỉ có thể chơi ở mức rất cơ bản. Đây là thời kỳ mà các nhà nghiên cứu đã phát triển các kỹ thuật cơ bản để đánh giá các thế cờ và tìm kiếm các nước đi có thể có (và các nước đi phản công của đối thủ). Những ý tưởng này vẫn còn được sử dụng cho đến ngày nay.

Chương trình đầu tiên chơi cờ vua (Turochamp)

  • Trò chơi: cờ vua. Năm: 1948–1953

  • Năm 1953, Alan Turing đã xuất bản một bài báo về chương trình cờ vua của mình (Máy tính kỹ thuật số được áp dụng cho trò chơi) trong cuốn sách Nhanh hơn suy nghĩ của B. Bowden. Shannon đã không nói về bất kỳ chương trình cụ thể nào trong bài báo của mình. Chính Turing là người viết chương trình cờ vua đầu tiên. Và anh ấy đã viết nó trước cả khi máy tính tồn tại! Anh biết máy tính đang đến và một khi chúng đủ mạnh, chúng sẽ có thể chơi cờ vua. Năm 2012, Garry Kasparov thi đấu với Turochamp và đánh bại nó chỉ sau 16 nước đi. Kasparov nói (video) , “Tôi cho rằng bạn có thể gọi nó là sơ khai, nhưng tôi sẽ so sánh nó với một chiếc xe hơi đời đầu - bạn có thể cười nhạo họ nhưng đó vẫn là một thành tích đáng kinh ngạc…


[Turing] đã viết các thuật toán mà không cần có máy tính - nhiều nhà khoa học trẻ sẽ không bao giờ tin rằng điều đó là khả thi. Đó là một thành tích xuất sắc. ”


Đọc thêm

Alan Turing (1912–1954)

MANIAC: Chạy chương trình cờ vua đầu tiên

  • Trò chơi: Cờ vua. Năm: 1956
  • Nhóm lập trình MANIAC được dẫn đầu bởi Stanislaw Ulam (người đã phát minh ra lực đẩy xung hạt nhân và thiết kế bom H cùng với Edward Teller), Paul Stein, Mark Wells, James Kister, William Walden và John Pasta. Do bộ nhớ hạn chế của MANIAC, chương trình đã sử dụng bàn cờ 6 × 6 và không có quân cờ. MANIAC Tôi đã thực hiện chiến lược Shannon Loại A vũ phu. Nó thực hiện 11.000 hoạt động mỗi giây và có 2.400 ống chân không. Phải mất 12 phút để tìm kiếm ở độ sâu bốn lần di chuyển (thêm hai giám mục sẽ mất ba giờ để tìm kiếm ở cùng độ sâu).

Đọc thêm…

Paul Stern (trái) và Nick Metropolis chơi cờ vua với máy tính MANIAC (ComputerHistory.org)

Chương trình cờ vua Bernstein: Chương trình hoàn chỉnh đầu tiên

  • Trò chơi: Cờ vua. Năm: 1957
  • Alex Bernstein, một nhân viên của IBM, đã tạo ra chương trình đầu tiên có thể chơi một ván cờ hoàn chỉnh. Ông đã tạo ra nó cùng với các đồng nghiệp Michael Roberts, Thomas Arbucky và Martin Belsky, Bernstein tại Viện Công nghệ Massachusetts. Chương trình chạy trên IBM 704 và có thể thực hiện 42.000 lệnh mỗi giây. Đây là một trong những máy tính ống chân không cuối cùng. Mất khoảng 8 phút để thực hiện một động thái.

Chương trình Cờ vua Bernstein đã sử dụng chiến lược Shannon Loại B (tìm kiếm có chọn lọc).

Đọc thêm…

Xem video: Lập trình viên kiêm kỳ thủ cờ vua của IBM, Alex Bernstein chơi một trong những trò chơi cờ vua máy tính hoàn chỉnh đầu tiên trên IBM 704 (Lịch sử máy tính)

AI trước AI (quân cờ của Samuel)

  • Trò chơi: Cờ caro. Năm: 1952–1962
  • Năm 1952, Arthur Samuel hoàn thành chương trình kiểm tra đầu tiên của mình trên IBM 701 - máy tính thương mại lớn đầu tiên. Đến năm 1955, Samuel đã làm được một điều gì đó đột phá; ông đã tạo ra một chương trình có thể học - điều mà trước đây chưa ai làm - và nó đã được trình diễn trên truyền hình vào năm 1956. Samuel đã suy nghĩ về học máy kể từ khi gia nhập IBM và muốn tập trung vào việc xây dựng các chương trình có thể học cách chơi trò chơi cờ caro. Năm 1959, ông đặt ra thuật ngữ "máy học".

Đọc thêm

Arthur Samuel chơi cờ caro trên IBM 701

Học cách chơi một trò chơi hoàn hảo Tic-Tac-Toe (MENACE)

  • Trò chơi: Tic Tac Toe. Năm: 1960
  • Trong Thế chiến thứ hai, Donald Michie, một nhà khoa học máy tính người Anh, làm việc cho Bộ luật Chính phủ và Trường Cypher tại Công viên Bletchley và giúp phá mã “Tunny” của Đức. Năm 1960, ông đã phát triển Machine Educable Noughts And Crosses Engine (MENACE), một trong những chương trình đầu tiên có khả năng học cách chơi một trò chơi hoàn hảo Tic-Tac-Toe. Máy tính không có sẵn nên anh đã sử dụng 304 hộp diêm chứa đầy hạt màu để học chơi. Sắp có

MENACE

Vào cuối những năm 1960, các chương trình cờ vua trên máy tính đã đủ tốt để thỉnh thoảng đánh bại các kỳ thủ cấp câu lạc bộ hoặc nghiệp dư.

Chương trình cờ vua đầu tiên để thi đấu trong các giải đấu của con người (Mack Hack VI)

  • Trò chơi: Cờ vua. Năm: 1967
  • Mac Hack (còn được gọi là Chương trình Cờ vua Greenblatt) là một chương trình cờ vua dựa trên kiến thức được xây dựng bởi Richard Greenblatt vào năm 1967. Cùng năm, Mac Hack VI trở thành máy tính đầu tiên thi đấu với con người trong điều kiện thi đấu của con người. Chương trình MacHack là “chương trình cờ vua được phân phối rộng rãi đầu tiên”, chạy trên nhiều máy PDP. Nó trở thành máy tính đầu tiên đạt tiêu chuẩn của những người chơi giải đấu trung bình. Nó vượt trội hơn hẳn so với tất cả các chương trình cờ vua trước đây cũng như hầu hết những người chơi bình thường. Năm 1965, Hubert Dreyfus nói, " Không có chương trình cờ vua nào có thể chơi được ngay cả cờ vua nghiệp dư ." Năm 1967, Mac Hack VI đánh bại Dreyfus.

Đọc thêm…

MAC Hack 6 (Robert Q) đang chạy trên DEC PDP-6


Trong những năm 1970 và 1980, ông không nhấn mạnh vào tốc độ phần cứng. Trong những năm 1950 và 1960, những người đi tiên phong đầu tiên đã tập trung vào suy nghiệm cờ vua (các quy tắc ngón tay cái) để chọn nước đi tiếp theo tốt nhất. Các chương trình trong những năm 1970 và 1980 cũng sử dụng một số phương pháp phỏng đoán cờ vua, nhưng tập trung mạnh hơn nhiều vào cải tiến phần mềm cũng như sử dụng phần cứng nhanh hơn và chuyên dụng hơn. Phần cứng và phần mềm tùy chỉnh cho phép các chương trình tiến hành tìm kiếm sâu hơn nhiều cây trò chơi (ví dụ: liên quan đến hàng triệu thế cờ), điều mà con người không làm (vì họ không thể) làm.

Cray Blitz: Siêu máy tính (cờ vua) đầu tiên

  • Trò chơi: Cờ vua. Năm 1986–1980
  • Cray Blitz, được phát triển bởi Robert Hyatt, Harry L. Nelson và Albert Gower, đã tham gia Giải vô địch cờ vua máy tính Bắc Mỹ của ACM vào năm 1976. Nó trở thành một đối thủ nặng ký vào năm 1980 khi nó được chuyển sang siêu máy tính Cray-1, trở thành chương trình cờ vua đầu tiên để sử dụng một cỗ máy mạnh mẽ như vậy. Điều này giúp Cray Blitz có thể điều chỉnh một cách tiếp cận chủ yếu là thuật toán và tính toán trong khi vẫn giữ lại hầu hết kiến thức cờ vua (sâu rộng) của mình.

Đọc thêm…

Harry Nelson và Cray Blitz


Chương trình đầu tiên đánh bại nhà vô địch thế giới (BKG)

  • Trò chơi: Ván bài lật ngửa. Năm: 1979.
  • BKG, một chương trình backgammon do Hans Berliner tạo ra, là lần đầu tiên một cỗ máy đánh bại một nhà vô địch thế giới trong bất kỳ trò chơi nào. Và nó đã làm được điều đó với những chiếc máy tính chậm chạp của những ngày đó. [Lưu ý: Berliner đã phát triển thuật toán tìm kiếm B * để tìm kiếm trên cây trò chơi.]

Đọc thêm

Hans Berliner, một người chơi cờ hậu và một nhà nghiên cứu cờ vua máy tính

HiTech: Thạc sĩ quốc tế đầu tiên

  • Trò chơi: Cờ vua. Năm: 1980
  • HiTech là một cỗ máy chơi cờ với phần cứng và phần mềm có mục đích đặc biệt. Nó được xây dựng bởi Hans Berliner và những người khác tại CMU. Phần cứng tùy chỉnh của nó có thể phân tích ~ 175.000 bước di chuyển mỗi giây và nó có thể thực hiện tìm kiếm theo chiều sâu trước hết có chiều rộng đầy đủ. Đó là một cỗ máy mạnh mẽ. Năm 1985, nó đã đạt được xếp hạng 2530, trở thành máy đầu tiên (và duy nhất vào thời điểm đó) có xếp hạng trên 2400.

Đọc thêm…

Lịch sử máy tính


Đi trước những người chơi mạnh nhất là người mạnh nhất (Chinook) vài dặm

  • Trò chơi: Cờ caro. Năm: (1989–1996)

  • Sau khi Samuel làm việc với cờ caro, có một ấn tượng sai lầm rằng cờ caro là một trò chơi "đã được giải quyết". Kết quả là, các nhà nghiên cứu chuyển sang cờ vua và hầu như bỏ qua cờ caro cho đến khi Jonathan Schaeffer bắt đầu nghiên cứu về Chinook vào năm 1989. Mục tiêu của Schaeffer là phát triển một chương trình có khả năng đánh bại người chơi cờ caro giỏi nhất. Rõ ràng cầu thủ quan trọng nhất trong sơ đồ chiến thuật của Marion Tinsley. Trong một trận đấu, Chinook đã thắng một trận đấu với Tinsley, mà Schaeffer đã trả lời,


“Chúng tôi vẫn là thành viên của loài người và Chinook đánh bại Tinsley trong một trò chơi duy nhất có nghĩa là chỉ còn là vấn đề thời gian trước khi máy tính trở nên tối cao trong cờ caro, và cuối cùng là trong các trò chơi khác như cờ vua.”


Đọc thêm để xem Chinook vs. Tinsley diễn ra như thế nào.

Từ trái sang: Duane Szafron, Joe Culberson, Paul Lu, Brent Knight, Jonathan Schaeffer, Rob Lake và Steve Sutphen. Chuyên gia kiểm tra của chúng tôi, Norman Treloar, đã mất tích

Suy nghĩ sâu sắc

Bảng mạch Deep Thought


Vào những năm 1990, các chương trình cờ vua bắt đầu thử thách các võ sư Cờ vua Quốc tế và sau đó là các Đại kiện tướng. Một máy đánh cờ chuyên dụng, tên là Deep Blue, sẽ đánh bại Garry Kasparov, người chơi cờ giỏi nhất của con người. Chúng tôi cũng đã chứng kiến những ứng dụng thành công của học tăng cường (điều mà AlphaGo sẽ thực hiện nhiều năm sau đó).

TD-Gammon

  • Trò chơi: Ván bài lật ngửa. Năm: 1992–1997
  • TD-Gammon là chương trình backgammon được phát triển vào năm 1992 bởi Gerald Tesauro của IBM. TD-Gammon đã áp dụng phương pháp học tăng cường, quay trở lại chương trình Người kiểm tra của Samuel (sau này chúng ta sẽ thấy alphaGo cũng vậy). Tesauro nói rằng phương pháp tự giảng dạy của TD-Gammon đã dẫn đến một chương trình mạnh mẽ đáng ngạc nhiên. TD-Gammon 3.0 (1997) sử dụng tìm kiếm 3 lớp có chọn lọc và đã ở hoặc rất gần trình độ của những người chơi giỏi nhất thế giới. Về lâu dài, TD-Gammon được kỳ vọng sẽ chơi tốt hơn cả các kiện tướng vì những kiện tướng đó chỉ là con người. Và con người cảm thấy mệt mỏi. Con người có thành kiến, nhưng TD-Gammon thì không. TD-Gammon chơi khác với con người - một chủ đề mà chúng ta sẽ ngày càng chú ý hơn. Đọc thêm .

Gerald Tesauro

Giống như một con người, nhưng (vẫn) không phải là con người: Deep Blue

  • Trò chơi: Cờ vua. Năm: 1996–1997

  • Cái này dài (và siêu thú vị). Chắc chắn sẽ đọc nó.

  • Deep Blue mới chỉ là một đứa trẻ hai tuần tuổi khi nó đối mặt với Garry Kasparov vào năm 1996. Hsu, một trong những người tạo ra nó nói, “ Liệu có phải chính Hercules bé đã bóp cổ hai con rắn do Nữ thần Hera gửi đến không? Hay là chúng ta gửi một đứa trẻ bơ vơ đến như một sự tưởng nhớ để xoa dịu con quái vật biển Cetus, nhưng không có sự trợ giúp của Perseus? Chúng tôi sợ rằng nó sẽ là thứ sau này ”. Trận đấu đầu tiên nó từng đấu với Kasparov, nó đã thắng - khiến Kasparov phải tự vấn bản thân và hỏi, “ … điều gì sẽ xảy ra nếu thứ này là bất khả chiến bại?” Nó sẽ không thể bất khả chiến bại và Kasparov sẽ đánh bại nó với tỷ số 4–2. Trận đấu này đã gần hơn nhiều so với mọi người nghĩ ( Đọc thêm ).

  • Sau trận đấu, Kasparov đã nói (về Deep Blue),


"Tôi có thể cảm thấy - tôi có thể ngửi thấy - một loại trí thông minh mới trên bàn."


  • Sẽ có một trận tái đấu vào năm 1997. Lần này đội Deep Blue đã cải thiện đáng kể cỗ máy của họ (đọc về các cải tiến, kiến trúc hệ thống, chiến lược tìm kiếm, chip cờ, v.v.) Lần này Deep Blue chơi một trò chơi không ai mong đợi và đánh bại Garry Kasparov. Kasparov ám chỉ IBM đã gian lận (IBM không gian lận) bởi vì trò chơi của Deep Blue có một thành phần của "con người". Sau trận đấu này, Kasparov nói,


“Tôi không có tâm trạng chơi đùa gì cả..Tôi là một con người. Khi tôi nhìn thấy điều gì đó vượt quá tầm hiểu biết của mình, tôi sợ hãi. ''


  • Đây là trận đấu mà mọi người đều có ý kiến - Deep Blue có thông minh không? Ai là người chơi tốt hơn? Deep Blue có nghĩ không? Một chiến thắng như vậy nói gì về chúng tôi? Cho đến Deep Blue, con người đã chiến thắng trong cờ vua. Máy móc thực sự không thể đánh bại những con người giỏi nhất - thậm chí không thể gần hơn . Nhưng rồi Deep Blue đã chiến thắng. Và ngay sau đó, các máy tính khác cũng vậy và chúng đã đánh bại chúng ta kể từ đó. Sự phát triển lớn mạnh này là đặc điểm nhận dạng của chúng - bất kể tốc độ cải tiến của chúng ta là bao nhiêu, một khi máy móc bắt đầu cải tiến, việc học hỏi và tiến bộ của chúng sẽ được đo lường theo cấp số nhân. Và của chúng tôi thì không. Đọc thêm để biết chi tiết về cách máy này được chế tạo, ai tham gia, loại nỗ lực mà nhóm cần thực hiện vào dự án, cách Kasparov đối phó với thất bại và cách nó trở thành một dấu ấn quan trọng trong lịch sử AI.

IBM’s Deep Blue Team (từ trái sang phải): Joe Hoane, Joel Benjamin, Jerry Brody, F.H. Hsu, C.J. Tan và Murray Campbell. Nguồn: Daniel King, Kasparov v Deeper Blue


Đọc thêm (Deep Blue)…

Mọi người tin rằng Kasparov vẫn là một người chơi tốt hơn, nhưng cảm xúc của anh ấy đã bị ảnh hưởng. Dù bằng cách nào, một trong những điều rút ra lớn nhất từ trận đấu này là chúng ta đã đánh giá thấp cả khía cạnh tâm sinh lý của trận đấu.


Cảm xúc, nỗi sợ hãi, mong muốn và nghi ngờ của chúng ta là cách để chúng ta đạt được điều tốt nhất… Và đây là một vấn đề duy nhất của con người, một vấn đề mà các đối thủ máy móc của chúng ta không phải lo lắng.


Đọc thêm (Đăng Deep Blue)

Giải bài kiểm tra

  • Trò chơi: Cờ caro. Năm: 2007
  • Vào năm 2007, những người tạo ra Chinook đã xuất bản một bài báo trên tạp chí Science thông báo rằng Chinook đã hoàn toàn giải được Checkers: chương trình không còn có thể bị đánh bại bởi bất kỳ ai, con người hay cách khác. Jonathan Schaeffer và nhóm của ông đã làm việc để giải quyết vấn đề cờ caro kể từ năm 1989. Bài báo viết rằng, “ … cờ đam bây giờ đã được giải quyết: Chơi hoàn hảo của cả hai bên dẫn đến hòa. Đây là trò chơi phổ biến thử thách nhất được giải quyết cho đến nay, phức tạp gấp một triệu lần Connect Four. ”Cờ caro là trò chơi lớn nhất đã được giải cho đến nay, với không gian tìm kiếm là 5 × 10 ^ 20. “Số lượng phép tính liên quan là 10 ^ 14 , được thực hiện trong khoảng thời gian 18 năm. Quá trình này bao gồm từ 200 máy tính để bàn lúc cao điểm xuống còn khoảng 50 ”. Sắp có

Chúng ta sẽ đi đâu từ đây?

Có vẻ như đúng khi kết thúc bằng bài nói chuyện TED của Garry Kasparov và quan điểm của ông về trải nghiệm này.


Điều tôi học được từ kinh nghiệm của chính mình là chúng ta phải đối mặt với nỗi sợ hãi nếu chúng ta muốn tận dụng tối đa công nghệ của mình và chúng ta phải chinh phục những nỗi sợ đó nếu chúng ta muốn khai thác tốt nhất con người của chúng ta.


Trong khi liếm vết thương của mình, tôi có rất nhiều cảm hứng từ những trận chiến chống lại Deep Blue. Như câu nói cũ của người Nga, nếu bạn không thể đánh bại họ, hãy tham gia cùng họ. Sau đó, tôi nghĩ, điều gì sẽ xảy ra nếu tôi có thể chơi với máy tính - cùng với máy tính bên mình, kết hợp sức mạnh của chúng ta, trực giác của con người cộng với tính toán của máy, chiến lược của con người, chiến thuật của máy, kinh nghiệm của con người, bộ nhớ của máy. Nó có thể là trò chơi hoàn hảo từng chơi? Nhưng không giống như trước đây, khi máy móc thay thế động vật nông trại, lao động chân tay, giờ đây chúng đang đến sau những người có bằng đại học và có tầm ảnh hưởng chính trị. Và là một người đã chiến đấu với máy móc và thua cuộc, tôi ở đây để nói với bạn rằng đây là một tin tuyệt vời, tuyệt vời. Cuối cùng, mọi ngành nghề sẽ phải cảm thấy những áp lực này, nếu không, điều đó có nghĩa là nhân loại đã không còn tiến bộ. Chúng ta không được lựa chọn khi nào và nơi nào mà tiến bộ công nghệ dừng lại.


Chúng ta không thể chậm lại. Trên thực tế, chúng tôi phải tăng tốc độ. Công nghệ của chúng tôi vượt trội trong việc loại bỏ những khó khăn và sự không chắc chắn khỏi cuộc sống của chúng tôi, và vì vậy chúng tôi phải tìm kiếm những thách thức khó khăn hơn, không chắc chắn hơn bao giờ hết. Máy móc có tính toán. Chúng tôi có sự hiểu biết. Máy móc có hướng dẫn. Chúng tôi có mục đích. Máy móc có tính khách quan. Chúng tôi có niềm đam mê. Chúng ta không nên lo lắng về những gì máy móc của chúng ta có thể làm ngày hôm nay. Thay vào đó, chúng ta nên lo lắng về những gì họ vẫn chưa thể làm được ngày hôm nay, bởi vì chúng ta sẽ cần sự trợ giúp của những cỗ máy mới, thông minh để biến ước mơ vĩ đại nhất của chúng ta thành hiện thực. Và nếu chúng ta thất bại, nếu chúng ta thất bại, đó không phải là do máy móc của chúng ta quá thông minh, hoặc không đủ thông minh. Nếu chúng ta thất bại, đó là vì chúng ta đã trở nên tự mãn và hạn chế tham vọng của mình. Con người của chúng ta không được xác định bởi bất kỳ kỹ năng nào, như vung búa hay thậm chí là chơi cờ vua. Có một điều chỉ con người mới có thể làm được. Đó là giấc mơ. Vì vậy, chúng ta hãy ước mơ lớn lao ”.

https://www.youtube.com/watch?v=NP8xt8o4_5Q&feature=emb_imp_woyt


Vì vậy, chúng ta hãy ước mơ lớn.