CrazyEngineers
CrazyEngineers

  • Deep Blue Programming

    Kaustubh Katdare

    Administrator

    Updated: Oct 25, 2024
    Views: 1.1K
    Okay, for the uninitiated, "Deep Blue" is the name of the computer that was built to beat the human in the brainy game of 'Chess'!

    I've always been thinking, how did they write the software to calculate the moves of Deep Blue?

    Anyone's got any idea? If you were to write such a software, what would be your approach?
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • Kaustubh Katdare

    Administrator • Oct 8, 2008

    H-e-l-l-o !

    Why do threads like these get no response for a long time? Is everyone sleeping?
    Are you sure? This action cannot be undone.
    Cancel

  • silverscorpion

    Member • Oct 8, 2008

    ok, I'm not very good in programming. But what i read about deep blue is this.
    It has a basic chess engine and a very fast processor. It has millions of chess
    positions in it's memory and compares the current position with it's database.
    It decides which move is the best for current position and makes its move.
    The speed with which it searches is really huge - about 200 million chess
    positions per second.

    so, finally, deep blue is not really intelligent or an efficient chess player. It's
    really a super fast search engine with algoroithm for determining the best
    chess move for any given position.
    Are you sure? This action cannot be undone.
    Cancel

  • Kaustubh Katdare

    Administrator • Oct 8, 2008

    silverscorpion
    It decides which move is the best for current position and makes its move.
    You see, that's the part I want our CEans to discuss. How does it decide the best move?
    Are you sure? This action cannot be undone.
    Cancel

  • silverscorpion

    Member • Oct 8, 2008

    hi,
    May be, it compares the current position with previous games that are stored in the memory. Say, in a previous game, in a position similar to this, the move made was x. then the computer tries x here too. it's a matter of training and prediction i guess.. wat do u say?
    Are you sure? This action cannot be undone.
    Cancel

  • silverscorpion

    Member • Oct 8, 2008

    hi
    sorry i was wrong in the last post. It was pure brute force, as i suggested before.

    Read this : <a href="https://en.wikipedia.org/wiki/IBM_Deep_Blue" target="_blank" rel="nofollow noopener noreferrer">Ibm Deep Blue</a>

    I cant imagine how they packed so much power into a computer, that it defeated a grand master. I was always of the opinion that machines can never overrun humans. I'm not sure now...
    Are you sure? This action cannot be undone.
    Cancel

  • Kaustubh Katdare

    Administrator • Oct 8, 2008

    Yes, I've been guessing the same. Feeding all possible moves is just impossible. Anyone knows how this brute force works in Deep Blue?
    Are you sure? This action cannot be undone.
    Cancel

  • Ashraf HZ

    Member • Oct 8, 2008

    The_Big_K
    H-e-l-l-o !

    Why do threads like these get no response for a long time? Is everyone sleeping?
    Biggie, you're just so eager for a response! Its only been six hours since you first posted it 😛

    No idea how Deep Blue works in detail, but if I were to do a basic chess AI, I'd use some kind of tree algorithm with a database stored with LOTS of possible moves, but to a limit.

    I'd also implement Fuzzy logic to react with the opponent's moves *grin*
    Are you sure? This action cannot be undone.
    Cancel

  • Kaustubh Katdare

    Administrator • Oct 8, 2008

    How about getting the people who programed Deep Blue for Small Talk? 😁 ! Can anyone help us with contacts?
    Are you sure? This action cannot be undone.
    Cancel

  • sriramchandrk

    Member • Oct 13, 2008

    Hi,

    I dont know anyone who were involved in deep blue.

    But i have an idea about how it might be working.

    You have heard of Game-Tree(a sort of decision tree)
    For each possible move what all next possibles and from that point again what all etc.,

    For simple problems the game tree is usually small.
    but when you think of game like chess where billions or possibilities are there, you cant draw the complete game tree which takes you to win position, istead you have to stop drawing game tree at a certain positions based on your resources.

    On a simple machine for example you can think of a gametree of height of 1000 and you need to stop at this level and make the best move or else you will run out of resources.

    But on a better architecture (may be super computer) where in the calculation of game tree is distributed, has more space, power etc., you will get good moves as compared to regular home computers.

    Even a powerful supercomputer cannot draw a complete gametree. The process of calculating the tree goes on as moves happen.

    Hope this will give an idea about how it works.

    Thanks & Regards
    Sriram
    Are you sure? This action cannot be undone.
    Cancel

  • simplycoder

    Member • Sep 7, 2011

    I like this thread a lot, one it shares with chess,two its programing.
    Few months back I programmed a decent chess AI. Trust me its complicated.
    Assume number of legal moves on average in a game is 35

    In terms of Game trees, there is something called as branching factor, in chess this is approx 35(legal moves).
    so at parent node there are 35 possibilites.

    There would 35 child-nodes per parents thus yeilding to 1225 nodes.
    At level three its 42875.
    At level 4 its 1500625.
    At level 5 its 52521875
    At level 6 its 1838265625
    Assuming this, this will cause an explosion.

    To play decent chess, engine must think 6 plies ahead.
    So we shall add up all the nodes to check for the particular position at 6th ply or 6th level
    So total number of nodes at this level is 1892332260

    This is just a huge numbers and the computer is thinking just 3 moves ahead(seriously to rate this, I would say that its not even an average chess player)
    There is time required for move generation and evaluation as well so see this its going to take long time.

    Deep blue defeated Garry Kasparov(GOD of chess), Being a consistent chess player for over 8 years, by studying his games, I can say that Garry Kasparov thinks
    about 10 to 12 moves ahead in critical position.

    I have no guts to write the number of nodes now(35[SUP][SUB]24[/SUB][/SUP]). No processor can beat this huge number.
    brute force is O(n[SUP]b[/SUP]). This is where brute force solution fails.
    So programer thought about bruteforce and later on added some thing to it called as alpha-beta pruning(refer google).
    This has running time of O(n[SUP]b/2[/SUP])
    This is just fantastic now search space is decreased to (branch factor)/2 in the best case and branch factor in worst case, so we can assume that the average case will prune some nodes and search. This increases the speed and hence the depth.
    There are many algorithms that are implemented in deep-blue I just cannot cover each and every one of them. However if I get time, I shall write a tutorial on this for sure, we would learn board game programing for tic-tac-toe AI.

    Thus we donot need to store all positions for chess and we cannot store all positions for chess if we want to make it a decent player.
    Go is even more horrible than chess.
    Are you sure? This action cannot be undone.
    Cancel

  • vinci

    Member • Sep 12, 2011

    Hello friends !!!
    I read above posts and i found this topic really fantastic as well as interesting !!! Deep blue is an IBM super computer(Chess computer) that won game against world champion in 1997.but remember this machine was built by humans so who is more powerful???
    Are you sure? This action cannot be undone.
    Cancel

  • vinci

    Member • Sep 12, 2011

    really nice post .You seems to be a programmer,and very well know data structures.Good .keep write something in AI
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register