Like Tree2Likes

Chess opponent

This is a discussion on Chess opponent within the Game Programming forums, part of the General Programming Boards category; Thanks for the advice. My plan was to do a quick binary tree algorithm tonight and then maybe try the ...

  1. #16
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    Thanks for the advice. My plan was to do a quick binary tree algorithm tonight and then maybe try the minmax concept on a tictactoe game. I did a computer AI for connect 4, tictactoe, sudoku solver, basic chess AI and then general unit movement in a space shooter, a side scroller, and a RPG with bosses that had different battle behaviors. I wanted to revisit chess because four years ago when I did it the game fell apart after I started trying to program a advanced level. I had gotten up to the point where I actually had to think to win it then a bug showed up where it started creating copies of its queen when I was winning. I couldn't locate the bug and I ended up making things worse when I tried to fix it one night after drinking lol. That was actually the last program I made that had no classes.

    A 15,000 line game of chess with no classes or headers no wonder I crashed it lol.

  2. #17
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    Minimax really has nothing to do with binary trees. The "tree" in minimax only exists on the call stack (it's a search tree), not really a data structure where you store stuff. It's also not binary at all. The average branching factor in chess midgame is about 35 (that's why it requires many clever optimizations and risky optimizations to reach considerable search depth).

  3. #18
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    With minimax, tictactoe AI is extremely simple. There's no need for any pattern recognition, etc. Just need to be able to evaluate win or lose, and search.

    http://matthewlai.ca/blog/dl/ttt.c

    Be sure to still write it yourself, though.

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Lesshardtofind View Post
    From what I read it completely revolutionized the way computer AI algorithms were written and led to the creation of most modern AI. Apparently GO an Asian board game is now the new frontier in computer AI. The chess AI concept is commonly considered as important for the development of AI and computer algorithms as the fruit fly experiments are considered for genetic engineering.
    No, far from it. Deep Blue used almost all the same algorithms as Hsu had used previously, in Deep Thought, which used almost all the same algorithms as his mentor's chess program.

    Hsu did use some small additions, more - like hill climbing, to give parameters which produced moves matching that of the chess World Champions (Mostly Karpov and Kasparov!). They were not very successful, and took a long time to adjust the parameters. By and large, they were hand tuned by Hsu, and then they brought in an American chess master to advise them further. They especially wanted to avoid the inevitable "cooks" to be found in any encyclopedia of chess openings, and traps in the middle game.

    The BIG advance with Deep Blue, was the hardware - those custom chips Hsu designed (and IBM graciously paid to have made), made Deep Blue's depth of search, absolutely unprecedented at that time.

    (The search algorithms have made several refinements since then, btw. They are able to reach Deep Blue search depths now, with just a single (powrerful) PC!)

    The media coverage and fanfare both before and after the two matches, was absolutely stunning, as well. I've never seen anything like it except Fisher's match in Iceland.

    If you want a weaker level of play, just limit the search depth, and you'll have it. It also makes the game go a lot faster for us impatient types.

    I very much agree with cyberfish, write up your search using Tic-Tac-Toe, and then incorporate it into your chess program.

    Computers don't have that - "it's close to this other thing" kind of ability like humans have, but it will kick Go's butt, as soon as the programming years of effort in the algorithms, and hardware improvements, can match what has been done in Chess programming.

    The holdup seems to me to be that so many people don't play Go, or they're not really good enough at it to find those refinements the game program could benefit from. But it will happen one day - the Go Master's days as king of the hill, are drawing to an end.

  5. #20
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,409
    From what I read it completely revolutionized the way computer AI algorithms were written and led to the creation of most modern AI.
    I think that was in reference to the general idea of what the devlopment of Chess computing has given us. - nice post anyway tho :->
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  6. #21
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    I think the article was referring to how a lot of people became interested in chess programming early on and got them asking questions on how to make a computer smarter. Just like the information obtained in the fruit fly wasn't literally used in every other genetic engineering project but the methods that were required to be derived in order to succeed in the initial project eventually led to a deeper understanding of the approach in general. And those approaches and methods eventually became important in many other applications. Either way it wasnt my article was just sharing info I read on the subject.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Chess
    By Ducky in forum C++ Programming
    Replies: 11
    Last Post: 01-14-2009, 08:20 AM
  2. Chess in C
    By PuhFENDanT in forum C Programming
    Replies: 8
    Last Post: 06-19-2003, 07:07 AM
  3. Chess
    By PJYelton in forum A Brief History of Cprogramming.com
    Replies: 26
    Last Post: 11-11-2002, 10:24 AM
  4. My last opponent's image
    By Sentaku senshi in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 04-01-2002, 03:31 AM
  5. my grandfather's chess algorithm can beat your grandfather's chess algorithm...
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 22
    Last Post: 08-17-2001, 06:52 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21