How does videogame AI find its path and beat you at chess? (MiniMax, Dijkstra, A*)

How does videogame AI find its path and beat you at chess? (MiniMax, Dijkstra, A*) | Bitwise

Рет қаралды 9,472

Күн бұрын

This video was sponsored by Brilliant.
Keep exploring at brilliant.org/DigiDigger. Get started for free, and hurry-the first 200 people get 20% off an annual premium subscription.
How does the Artificial Intelligence (AI) work in video games? In part 1 of this video we will show how you can make an AI that can beat you at tic-tac-toe or chess and how NPCs can find their way to their destination in a digital world.
I will explain MiniMax trees and pathfinding algorithms such as Breadth-First Search, Dijkstra's Algorithm and A*.
It seems my source was incorrect about the complexity of the Pacman Algorithm. Based on an interview with Toru Iwatani, there is indeed more to it: programmersatwork.wordpress.c...
To learn more check out this wonderful explanation: • Pac-Man Ghost AI Expla...
Timestamps
0:00 Intro
3:00 How do MiniMax trees work?
7:05 How does Breadth First Search work?
8:24 How does Dijkstra's Algorithm work?
10:15 How does A* work?
12:05 Conclusion
My patreon: / digidigger
Music in in outro:
Besus y Abrazor - Rolemusic: freemusicarchive.org/music/Ro... available under a Creative Commons Attribution license creativecommons.org/licenses/...
References
alumni.media.mit.edu/%7Ejorkin...
www.gdcvault.com/play/1020775...
www.cs.mun.ca/%7Edchurchill/pd...
/ artificial_intelligenc...
/ advice_on_building_a_c...
/ building_a_game_ai_for...
dzone.com/articles/from-dijks...
dzone.com/articles/from-dijks...
qiao.github.io/PathFinding.js...
www.bewitched.com/chess/
• The F.E.A.R. AI

Пікірлер: 29

@DigiDigger Жыл бұрын

Keep exploring at brilliant.org/DigiDigger. Get started for free, and hurry-the first 200 people get 20% off an annual premium subscription.

@Krantz_ Жыл бұрын

The Pacman AI is MUCH more than just picking a random direction half the time! Your explanation is fine, but the REAL behaviour is much more interesting and complicated

@DigiDigger Жыл бұрын

It seems my source was incorrect about this! I looked into it further and based on an interview with Toru Iwatani, the creator of pacman there is indeed more to it than is stated in the video. I added a notification to the video as well as a message in the description. Thank you for pointing it out!

@JoyousCreeper Жыл бұрын

1:22 because they don't use random chance at all, there's a whole video explaining it

@degamevlog1219 Жыл бұрын

Heerlijk om te horen hoe je Dijsktra correct uitspreekt

@psyboyo Жыл бұрын

First time that I visualize A* working! Damn! That actually opened up new ideas, thank you!

@techdeth Жыл бұрын

WOW that A* explanation blew my mind! Such an elegant solution to produce massively better results.

@dmMeBikes Жыл бұрын

Thank you for these videos, they are always a treat

@eboatwright_ Жыл бұрын

Ayy, he's back!

@Relivino Жыл бұрын

Nice! How many parts will the series have?

@pitchblack5422 Жыл бұрын

hopefully many

@TarenGarond Жыл бұрын

That is not even close to how the Pac-Man AI works. If someone reads this and are curious how it really works watch the KZfaq-video "Pac-Man Ghost AI Explained" by "Retro Game Mechanics Explained".

@ORANOID 2 күн бұрын

Well, finally I've watched it. Great video.

@emanuelschuchart1788 Жыл бұрын

Keep it up please!!! So good

@freezinfire Жыл бұрын

Finally, you are back

@quentinmcwimberton6797 Жыл бұрын

He didn't forget the catchphrase this time!

@1ups_15 Жыл бұрын

this video made me remember this time when my comp sci teacher made us code the dijkstra algorithm back in 12th grade, tough times 😂

@nikozdev 10 ай бұрын

Nice tutorial. I wish I saw it earlier

@Drmsallam 4 ай бұрын

Please do more videos

@Gurzbujar Жыл бұрын

good stuff

@nicholasricci57 Жыл бұрын

Woohoo! New video

@moth.monster Жыл бұрын

Everyone knows chess was invented by Gary Chess.

@liamdrun Жыл бұрын

Hey, can someone explain to me what is MiniMax Tree

@GoldenBeholden Жыл бұрын

This video explains it pretty well: kzfaq.info/get/bejne/it2Sn9aEsZmRmqc.html

@coverinur6353 Жыл бұрын

It is an arbitrary method of analyzing potential outcomes. By first generating a list of starting values and then selecting values that are most beneficial to each “player” (red vs. blue) in turns, you can abstractly represent a “player's” actions in a game as a set of choices with varying benefits (-1 harmful, 0 neutral, 1 beneficial), where the largest/smallest number, depending on the player, represents victory. In the video we start by having blue select from a number of starting values. Blue's objective is to cause Red to lose by picking numbers (taking actions) with the lowest value. In some cases Blue is forced to pick numbers that are beneficial to Red. Then, from the numbers Blue picked, Red picks the numbers with the highest value and thus beneficial to them. Followed by Blue picking the lowest valued number and ending with Red picking the highest number. If the Number is +1 Red wins, if it is 0 Blue and Red tie, and if it is -1 Red loses and thus Blue wins.

@liamdrun Жыл бұрын

@@coverinur6353 i kinda get it now, thanks!

@liamdrun Жыл бұрын

@@GoldenBeholden lol

@algotn Жыл бұрын

Fix the thumbnails and title!!! Seeing these new videos have so few views really hurts to see. And I'm going to be honest, the videos are very good, but the thumbnail and title just straight up doesn't fit the content. They both look as if this is going to be a long, dry, multipart tutorial about it. Not a interesting, well illustrated educational video. These new two videos could probably have so much more views if only the title and thumbnails where fixed. Both Linus (LTT) and Jimmy (MrBeast) have extensively talked in podcasts about just how huge of a difference both the title and thumbnail can make to a video, and that even changing them on old videos can cause huge influxes of views. (I would strongly recommend Lex Freidman's episode with MrBeast. Even if you don't like MrBeasts content, he is by far the largest channel on youtube (that isn't a large corporate brand channel), and he does know what he is talking about) Take a look at channels like Tom Scott, Atomic frontier, Captain disillution, SmarterEveryDay and many more. They all have rather short, enticing and to the point titles, that doesn't feel clickbaity. Yes some have longer titles, such as SmarterEveryDay, but instead the videos are backed up with awesome thumbnails. This videos title as an example doesn't even fit, it has to be cut of with "..." in the end. You don't really need to mention MiniMax, Dijkstra or A* in the title. Instead let the description host all the excess information that isn't strictly needed for a new viewer. The title is meant to be, well a title, not a full explanation what the videos is about, thats what the description is for. But don't feel as if I'm attacking your channel, I have way less actual practical experience about this than you do. I'm just saying what my gut feeling is saying, and my gut is in no way shape or form an expert in this field. So don't assume I really know what I'm talking about, do your own research. However I can with strong certainty say that they are far from optimal as they are now.