Like Tree1Likes
  • 1 Post By cyberfish

C Chess game lacks power?

This is a discussion on C Chess game lacks power? within the Game Programming forums, part of the General Programming Boards category; Hello C World, I am a beginner to programming and to the C language, so please forgive me if I ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    3

    C Chess game lacks power?

    Hello C World,

    I am a beginner to programming and to the C language, so please forgive me if I am not as knowledgable as I should be. As a side project during my first year of programming I've been working on a chess playing program, with a built in AI (as of now it only plays the black pieces). I want it to be strong enough to beat a couple of chess-playing friends of mine(around 1800 strength), or barring that, a low-strength piece of commercial software like Chess-Titans.

    However a problem I have been running into is that no matter what I try to do to prune the search tree, the search times seem to be unusually slow. As of now, with alpha-beta pruning, and some sorting functions, it can search at a depth of 5 ply at an average of about 1-2 min. per move. I know that in order to be decent, a program should be able to search at least 7-8 ply.

    I know there are more pruning functions that I could add to prune the tree more aggressively. But I can't shake the feeling that that isn't the problem. My friend (non-programmer) suggested that maybe the program isnt' drawing enough resources from the computer. I am sure the basic functions of the code (i.e. the function which checks legality of moves, the piece functions etc.) are poorly optimized, which maybe could cause the slow down. But I have tested with trying to improve the efficiency of the code and it hasn't changed the search times one bit.

    Is there anyone with experience as a programmer/Chess-AI programmer who could provide their insight? If requested I could post my code, but be warned its excessively long and maybe a bit obscure..

    *(I ran the program locally and looked at it in taskmanager. under memory it says its using 680K. Could that be relevant to the slow search times?)

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    I have done a chess AI that plays at about 2200 before (Brainless).

    Do you know if your problem is an excessively large tree or slow node search speed? Try adding node counting to your program, if you don't have it already. See what kind of NPS (nodes per second) you got. Crafty does about 4 million NPS, with a lot of highly optimized inline assembly. My program does about 1.5 million NPS, and is considered fairly fast (it has relatively rudimentary evaluation).

    With alpha-beta and trivial ordering (captures of high values first), you should be able to go 6-7 plies in a few seconds.

    Memory usage has nothing to do with this. You shouldn't need much memory until you implement the transposition table.

  3. #3
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,333
    [Edit]
    Ah. Yea. Don't bother with this. I misread the quoted statement.
    [/Edit]

    You shouldn't need much memory until you implement the transposition table.
    What?

    Soma
    Last edited by phantomotap; 04-26-2011 at 10:58 PM. Reason: none of your business

  4. #4
    Registered User
    Join Date
    Apr 2011
    Posts
    3
    thanks for your response.

    I tested the NPS and it seems very slow, only a few thousand nodes per second. It takes the computer over half a minute to do a full width min-max search at 3 ply during the middlegame. Evaluation function is extremely simple at this point so it can't be due
    to that.

    Do you have any idea why NPS would be so slow? I stored the chessboard in a 3-dimensional array (two dimensions for the board, the third for past and present board positions). My code might be inefficient in many places, but does that account for the lack of search speed?

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    A NPS that low is definitely a problem. The ply count sounds about right for that kind of NPS. You should aim for at least in the 100knps range.

    The reason is probably the inefficient code. No one can tell you what's wrong with it without seeing the code, and probably no one has time to go through your whole program to find out what's wrong since it's probably pretty big.

    That's why a chess AI is not really a good beginner project - it requires you to know how to write fast code, what actually happens in background with every C statement, what constructs are fast, and what constructs are slow and should be avoided (memory access patterns, etc). Unfortunately that really only comes with experience, and if you try to learn all those optimization techniques now, it would be very confusing and distract you from your learning of general programming concepts, which are much more important.

    A fast chess AI is usually ugly (just look at Crafty source code...) out of necessity for performance, but that's not the kind of code you want to be writing as a beginner.

    Therefore, I suggest putting this project aside for now, and work on something else first, and come back to this once you feel more confident about the language, and programming in general.
    MK27 likes this.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    I always wanted to make a chess game that decided its moves by trying to own as much of the board as it could. It would pick whatever move gave it the most control of the most enemy pieces or the most board coverage:

    rkbqKbkr
    pppppppp
    11111111
    00000000
    00000000
    22222222
    pppppppp
    rkbqKbkr

    At the start, everything with a 1 is owned (covered) by the top player. Everything with a 2 is owned by the bottom player. Player 1 would make a move which would own the most squares for them (or control the most enemy pieces - put them in danger). Each piece would have point value that would help decide what was a better piece to cover in the event of a tie.

    No look-ahead. Just try to gobble up as much of the board and pieces as you can. Then I'd just make it play itself to see how it would turn out. But I never get around to doing it.


    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    A more involved form of this concept is present in most chess engines - static exchange evaluation. Basically "score" a capture based on expected exchange of material without a real search. It's used in move ordering, which means all else equal, a move that will win material has better chance than a move that will lose or not win as much material. However, there are obviously many exceptions, that's why it's not usually an evaluation term. The closest idea that's commonly an evaluation term is mobility (essentially number of possible moves). It's pretty important.

    With AIs that do only what you described, the game may be fun to watch, but the program will be very weak.

  8. #8
    Registered User inequity's Avatar
    Join Date
    Nov 2010
    Location
    Seattle, Washington
    Posts
    59
    Quote Originally Posted by Coolio_High View Post
    Hello C World,

    I am a beginner to programming and to the C language, so please forgive me if I am not as knowledgable as I should be. As a side project during my first year of programming I've been working on a chess playing program, with a built in AI (as of now it only plays the black pieces). I want it to be strong enough to beat a couple of chess-playing friends of mine(around 1800 strength), or barring that, a low-strength piece of commercial software like Chess-Titans.

    However a problem I have been running into is that no matter what I try to do to prune the search tree, the search times seem to be unusually slow. As of now, with alpha-beta pruning, and some sorting functions, it can search at a depth of 5 ply at an average of about 1-2 min. per move. I know that in order to be decent, a program should be able to search at least 7-8 ply.

    I know there are more pruning functions that I could add to prune the tree more aggressively. But I can't shake the feeling that that isn't the problem. My friend (non-programmer) suggested that maybe the program isnt' drawing enough resources from the computer. I am sure the basic functions of the code (i.e. the function which checks legality of moves, the piece functions etc.) are poorly optimized, which maybe could cause the slow down. But I have tested with trying to improve the efficiency of the code and it hasn't changed the search times one bit.

    Is there anyone with experience as a programmer/Chess-AI programmer who could provide their insight? If requested I could post my code, but be warned its excessively long and maybe a bit obscure..

    *(I ran the program locally and looked at it in taskmanager. under memory it says its using 680K. Could that be relevant to the slow search times?)
    Have you run a profiler on it? Would probably be way more helpful than task manager at determining what could be optimized.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help on chess game
    By Ducky in forum C++ Programming
    Replies: 0
    Last Post: 03-22-2009, 09:03 AM
  2. Help with A Chess game
    By Dan911 in forum C++ Programming
    Replies: 10
    Last Post: 11-28-2005, 08:39 AM
  3. c++ chess game help
    By jdm71488 in forum C++ Programming
    Replies: 6
    Last Post: 04-26-2004, 09:46 AM
  4. My CHESS Game..
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 02:22 PM
  5. chess game
    By meka in forum C++ Programming
    Replies: 1
    Last Post: 12-06-2001, 01:33 PM

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