5 ms·

A 'Brief' History of Game AI Up to AlphaGo

71 points by andreyk 9y ago

John_KZ 9y ago
That degree of laxness when using the term "AI" physically revolts me.
- IanCal 9y ago
  Game AI described here seems perfectly in line with what John McCarthy (who coined the term) describes as "artificial intelligence". http://jmc.stanford.edu/articles/whatisai/whatisai.pdf http://jmc.stanford.edu/articles/whatisai/whatisai.pdf If you have a strong physical reaction to a phrase being used as the originator uses it, as it is widely used in research, widely used in the media and general public, then perhaps the issue is not with everyone else.
  - John_KZ 9y ago
    The originator of GIF calls his creation "jiff". That doesn't make it right. And I don't know what you've been reading, but research and serious journalists don't use the term so lightly. Maybe parts of the general public and some liberal arts oriented journalists do, but that's their problem. Minimax and lookup tables computed by brute force don't make up learning, period.
    - taneq 9y ago
      Who said "learning"? 'Game AI' is distinct from research AI. It exists to provide an entertaining opponent which will challenge the player and then lose satisfyingly. The simpler, cheaper and more robust it can be while achieving that goal, the better. Often a semi-random state machine is enough.
    - swebs 9y ago
      The checkers example actually used machine learning though. Here's the linked PDF: https://www.cs.virginia.edu/~evans/greatworks/samuel1959.pdf https://www.cs.virginia.edu/~evans/greatworks/samuel1959.pdf Scroll down to the section labeled "Learning procedure involving generalizations"
- EvgeniyZh 9y ago
  Sorry that our scientific term doesn't fit your intuition
golergka 9y ago
Term "Game AI" is usually used in context of game development, where it means something completely different: not an agent that is optimized for top perfomance, but an agent that is optimized for maximum player fun. It's a completely different task, solved with completely different methods.
60654 9y ago
It's a nice historical overview of using search and ML for formal games like chess. But - this is not the game developer usage of "game AI". Where are wargames, where are artificial characters, where is interactive storytelling, where are realtime control systems, and so on, and so forth? The doc is missing a lot of the actual history of game AI, which is much wider and more varied than presented here (and ML approaches are still in minority). Anyone interested in game AI history should definitely check out the past proceedings of the AIIDE conference: http://www.aiide.org http://www.aiide.org
- ggggtez 9y ago
  What are you talking about. Storytelling is not part of game AI. Not for Chess. At best, the storytelling can be considered to be purposely making the AI consider fewer ply of moves, to create a more fun experience for lower leveled players.
  - 60654 9y ago
    I can't tell if you're trolling or are just not up to date on game AI, so assuming the latter: you have to think beyond chess. There's much more info on interactive storytelling in the AIIDE proceedings I linked to, it's a very active area of research. Academically it goes back at least to the mid 90s, Oz project at CMU for example, or MIT Media Lab projects. And in commercial production, interactive stories are as old as the industry, probably the best early example is Infocom but back then there wasn't much AI driving it; it's not until the 2000s that people started actually building "drama managers" for shipping games to introduce dramatic conflict dynamically.
    - deleted 9y ago
      [deleted]
    - ggggtez 9y ago
      You can measure research on lots of directions. The purpose of AlphaGo was to win the game, so discussion about AI which are not built to win is largely irrelevant. The difficulty of Go had nothing to do with creating tension (where in many games humans play, AI players can trivially win if the designers wanted them to). In Go this was not the case, as AI lagged behind grandmaster play significantly. Thus, the discussion of research that interests you that has nothing to do with the goals of Go AI, is tangential at best. It's not fair to say the article is faulty just because you wanted them to discuss your favorite research conference.
glaberficken 9y ago
>"since then computers have continued to become exponentially faster, and today humanity’s best Chess players are likely no match for programs you can run on your smartphone." Is this really true? Would a smartphone chess app beat the worlds top ranked player today?
- swebs 9y ago
  >Chess engines continue to improve. In 2009, chess engines running on slower hardware have reached the grandmaster level. A mobile phone won a category 6 tournament with a performance rating 2898: chess engine Hiarcs 13 running inside Pocket Fritz 4 on the mobile phone HTC Touch HD won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. https://en.wikipedia.org/wiki/Computer_chess#Computers_versus_humans https://en.wikipedia.org/wiki/Computer_chess#Computers_versu...
  - glaberficken 9y ago
    oh wow! thanks for the link So, if someone out there can explain, is a program like AlphaGo deterministic? Meaning if the opponent plays the exact same moves in 2 consecutive games will the 2nd game be a replica of the first? My naive guess is that the MTC search part of the algorithm will necessarily introduce some variation in play, no?
    - pixl97 9y ago
      I would be surprised if AG didn't start with a randomly generated seed to prevent this from happening. Of course that just moves the question to, if you start with the same seed and do the same moves...
- andreyk 9y ago
  yep, I got that tidbit from Kasparov himself I think
richard_shelton 9y ago
I'm glad that you've mentioned Kaissa, the famous chess program from Soviet Union. Kaissa was developed in 1972. Before that, in 1963, there was ITEP (ИТЭФ) chess program and in 1965 this program won in the international computer chess match. See details here: https://chessprogramming.wikispaces.com/ITEP+Chess+Program#Stanford-ITEP https://chessprogramming.wikispaces.com/ITEP+Chess+Program#S... By the way, the first computer game in USSR was made in 1957 on computer Strela-1, the author is Yuri Pervin. It was a variant of Dominoes board game in the player vs computer mode. The game was described in "Problemi Kibernetiki", issue 3, pages 171-180.
- andreyk 9y ago
  Very interesting, thanks for the info!

71 points by andreyk 9y ago

John_KZ 9y ago

That degree of laxness when using the term "AI" physically revolts me.

IanCal 9y ago
Game AI described here seems perfectly in line with what John McCarthy (who coined the term) describes as "artificial intelligence". http://jmc.stanford.edu/articles/whatisai/whatisai.pdf http://jmc.stanford.edu/articles/whatisai/whatisai.pdf If you have a strong physical reaction to a phrase being used as the originator uses it, as it is widely used in research, widely used in the media and general public, then perhaps the issue is not with everyone else.
- John_KZ 9y ago
  The originator of GIF calls his creation "jiff". That doesn't make it right. And I don't know what you've been reading, but research and serious journalists don't use the term so lightly. Maybe parts of the general public and some liberal arts oriented journalists do, but that's their problem. Minimax and lookup tables computed by brute force don't make up learning, period.
  - taneq 9y ago
    Who said "learning"? 'Game AI' is distinct from research AI. It exists to provide an entertaining opponent which will challenge the player and then lose satisfyingly. The simpler, cheaper and more robust it can be while achieving that goal, the better. Often a semi-random state machine is enough.
  - swebs 9y ago
    The checkers example actually used machine learning though. Here's the linked PDF: https://www.cs.virginia.edu/~evans/greatworks/samuel1959.pdf https://www.cs.virginia.edu/~evans/greatworks/samuel1959.pdf Scroll down to the section labeled "Learning procedure involving generalizations"
EvgeniyZh 9y ago
Sorry that our scientific term doesn't fit your intuition

golergka 9y ago

Term "Game AI" is usually used in context of game development, where it means something completely different: not an agent that is optimized for top perfomance, but an agent that is optimized for maximum player fun. It's a completely different task, solved with completely different methods.

60654 9y ago

It's a nice historical overview of using search and ML for formal games like chess. But - this is not the game developer usage of "game AI". Where are wargames, where are artificial characters, where is interactive storytelling, where are realtime control systems, and so on, and so forth? The doc is missing a lot of the actual history of game AI, which is much wider and more varied than presented here (and ML approaches are still in minority). Anyone interested in game AI history should definitely check out the past proceedings of the AIIDE conference: http://www.aiide.org http://www.aiide.org

ggggtez 9y ago
What are you talking about. Storytelling is not part of game AI. Not for Chess. At best, the storytelling can be considered to be purposely making the AI consider fewer ply of moves, to create a more fun experience for lower leveled players.
- 60654 9y ago
  I can't tell if you're trolling or are just not up to date on game AI, so assuming the latter: you have to think beyond chess. There's much more info on interactive storytelling in the AIIDE proceedings I linked to, it's a very active area of research. Academically it goes back at least to the mid 90s, Oz project at CMU for example, or MIT Media Lab projects. And in commercial production, interactive stories are as old as the industry, probably the best early example is Infocom but back then there wasn't much AI driving it; it's not until the 2000s that people started actually building "drama managers" for shipping games to introduce dramatic conflict dynamically.
  - deleted 9y ago
    [deleted]
  - ggggtez 9y ago
    You can measure research on lots of directions. The purpose of AlphaGo was to win the game, so discussion about AI which are not built to win is largely irrelevant. The difficulty of Go had nothing to do with creating tension (where in many games humans play, AI players can trivially win if the designers wanted them to). In Go this was not the case, as AI lagged behind grandmaster play significantly. Thus, the discussion of research that interests you that has nothing to do with the goals of Go AI, is tangential at best. It's not fair to say the article is faulty just because you wanted them to discuss your favorite research conference.

glaberficken 9y ago

>"since then computers have continued to become exponentially faster, and today humanity’s best Chess players are likely no match for programs you can run on your smartphone." Is this really true? Would a smartphone chess app beat the worlds top ranked player today?

swebs 9y ago
>Chess engines continue to improve. In 2009, chess engines running on slower hardware have reached the grandmaster level. A mobile phone won a category 6 tournament with a performance rating 2898: chess engine Hiarcs 13 running inside Pocket Fritz 4 on the mobile phone HTC Touch HD won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. https://en.wikipedia.org/wiki/Computer_chess#Computers_versus_humans https://en.wikipedia.org/wiki/Computer_chess#Computers_versu...
- glaberficken 9y ago
  oh wow! thanks for the link So, if someone out there can explain, is a program like AlphaGo deterministic? Meaning if the opponent plays the exact same moves in 2 consecutive games will the 2nd game be a replica of the first? My naive guess is that the MTC search part of the algorithm will necessarily introduce some variation in play, no?
  - pixl97 9y ago
    I would be surprised if AG didn't start with a randomly generated seed to prevent this from happening. Of course that just moves the question to, if you start with the same seed and do the same moves...
andreyk 9y ago
yep, I got that tidbit from Kasparov himself I think

richard_shelton 9y ago

I'm glad that you've mentioned Kaissa, the famous chess program from Soviet Union. Kaissa was developed in 1972. Before that, in 1963, there was ITEP (ИТЭФ) chess program and in 1965 this program won in the international computer chess match. See details here: https://chessprogramming.wikispaces.com/ITEP+Chess+Program#Stanford-ITEP https://chessprogramming.wikispaces.com/ITEP+Chess+Program#S... By the way, the first computer game in USSR was made in 1957 on computer Strela-1, the author is Yuri Pervin. It was a variant of Dominoes board game in the player vs computer mode. The game was described in "Problemi Kibernetiki", issue 3, pages 171-180.

andreyk 9y ago
Very interesting, thanks for the info!