EzDevInfo.com

Programmer Puzzle: Encoding a chess board state throughout a game

Not strictly a question, more of a puzzle...

Over the years, I've been involved in a few technical interviews of new employees. Other than asking the standard "do you know X technology" questions, I've also tried to get a feel for how they approach problems. Typically, I'd send them the question by email the day before the interview, and expect them to come up with a solution by the following day.

Often the results would be quite interesting - wrong, but interesting - and the person would still get my recommendation if they could explain why they took a particular approach.

So I thought I'd throw one of my questions out there for the Stack Overflow audience.

Question: What is the most space-efficient way you can think of to encode the state of a chess game (or subset thereof)? That is, given a chess board with the pieces arranged legally, encode both this initial state and all subsequent legal moves taken by the players in the game.

No code required for the answer, just a description of the algorithm you would use.

EDIT: As one of the posters has pointed out, I didn't consider the time interval between moves. Feel free to account for that too as an optional extra :)

EDIT2: Just for additional clarification... Remember, the encoder/decoder is rule-aware. The only things that really need to be stored are the player's choices - anything else can be assumed to be known by the encoder/decoder.

EDIT3: It's going to be difficult to pick a winner here :) Lots of great answers!

What is the significance of initializing direction arrays below with given values when developing chess program?

I am new to competitive programming, and I noticed frequently, many of the great coders have these four lines in their code (particularly in those involving arrays):

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };

What does this really signify and what is technique used for?

Object Oriented Design for a Chess game

I am trying to get a feel of how to design and think in an Object Oriented manner and want to get some feedback from the community on this topic. The following is an example of a chess game that I wish to design in an OO manner. This is a very broad design and my focus at this stage is just to identify who is responsible for what messages and how the objects interact each other to simulate the game. Please point out if there are elements of bad design (high coupling, bad cohesion etc.) and how to improve on them.

The Chess game has the following classes

• Board
• Player
• Piece
• Square
• ChessGame

The Board is made up of squares and so Board can be made responsible for creating and managing Square objects. Each piece also is on a square so each piece also has a reference to the square it is on. (Does this make sense?). Each piece then is responsible to move itself from one square to another. Player class holds references to all pieces he owns and is also responsible for their creation (Should player create Pieces?) . Player has a method takeTurn which in turn calls a method movePiece which belongs to the piece Class which changes the location of the piece from its current location to another location. Now I am confused on what exactly the Board class must be responsible for. I assumed it was needed to determine the current state of the game and know when the game is over. But when a piece changes it's location how should the board get updated? should it maintain a seperate array of squares on which pieces exist and that gets updates as pieces move?

Also, ChessGame intially creates the Board and player objects who in turn create squares and pieces respectively and start the simulation. Briefly, this might be what the code in ChessGame may look like

Player p1 =new Player();
Player p2 = new Player();

Board b = new Board();

while(b.isGameOver())
{
  p1.takeTurn(); // calls movePiece on the Piece object
  p2.takeTurn();

}

I am unclear on how the state of the board will get updated. Should piece have a reference to board? Where should be the responsibility lie? Who holds what references? Please help me with your inputs and point out problems in this design. I am deliberately not focusing on any algorithms or further details of game play as I am only interested in the design aspect. I hope this community can provide valuable insights.

Chess piece hierarchy design: inheritance vs type fields

I have a base class for pieces

 class piece;

and an array containing derived objects

piece* board[8][8];

Advantage, clean design through virtual functions. Disadvantage, if I have to find a piece in the board or compare a piece I have to revert to dynamic casting (or typeid). It’s ugly and could be a performance hog when making millions of requests.

In the other hand, if I make an array of a single piece class, that has a type field for identifying pieces, I don’t have this problem (and it should be faster) but I have to make super ugly switch statements. I guess that since the number of pieces is finite and I don’t see myself making that many of switches, this could be in the end a better choice, what do you think?

This is for fun (so no bitboard).

EDIT 1

Reading some answers, I think using type fields only for operator overloading (==,!=...) could bring the best of both words.

The boost::variant looks very interesting too.

Best chess engine under permissive free software license [closed]

What is the best chess engine released under permissive free software license? By permissive free software license I mean, that it is legal to incorporate the engine's code into my project without having to release the source code of my whole project.

What is the state of the art in computer chess tree searching?

I'm not interested in tiny optimizations giving few percents of the speed. I'm interested in the most important heuristics for alpha-beta search. And most important components for evaluation function.

I'm particularly interested in algorithms that have greatest (improvement/code_size) ratio. (NOT (improvement/complexity)).

Thanks.

PS Killer move heuristic is a perfect example - easy to implement and powerful. Database of heuristics is too complicated.

How do I model a chessboard when programming a computer to play chess?

What data structures would you use to represent a chessboard for a computer chess program?

Chess game in JavaScript [closed]

Is there any Chess game API , purely written in JavaScript ? No Flash! Anybody know the algorithm(in general) used in Chess games ?

What are some good resources for writing a chess engine? [closed]

I'm interested in writing a chess engine (mostly as a learning exercise) and would be interested in any resources that people know of that could be of interest or use, anything really: Papers, Books, Theory, Tutorials, anything that could be useful.

Is there a perfect algorithm for chess?

I was recently in a discussion with a non-coder person on the possibilities of chess computers. I'm not well versed in theory, but think I know enough.

I argued that there could not exist a deterministic Turing machine that always won or stalemated at chess. I think that, even if you search the entire space of all combinations of player1/2 moves, the single move that the computer decides upon at each step is based on a heuristic. Being based on a heuristic, it does not necessarily beat ALL of the moves that the opponent could do.

My friend thought, to the contrary, that a computer would always win or tie if it never made a "mistake" move (however do you define that?). However, being a programmer who has taken CS, I know that even your good choices - given a wise opponent - can force you to make "mistake" moves in the end. Even if you know everything, your next move is greedy in matching a heuristic.

Most chess computers try to match a possible end game to the game in progress, which is essentially a dynamic programming traceback. Again, the endgame in question is avoidable though.

Edit: Hmm... looks like I ruffled some feathers here. That's good.

Thinking about it again, it seems like there is no theoretical problem with solving a finite game like chess. I would argue that chess is a bit more complicated than checkers in that a win is not necessarily by numerical exhaustion of pieces, but by a mate. My original assertion is probably wrong, but then again I think I've pointed out something that is not yet satisfactorily proven (formally).

I guess my thought experiment was that whenever a branch in the tree is taken, then the algorithm (or memorized paths) must find a path to a mate (without getting mated) for any possible branch on the opponent moves. After the discussion, I will buy that given more memory than we can possibly dream of, all these paths could be found.

Chess Quiescence Search ist too extensive

I have been creating a simple chess engine in c# over the last month and made some nice progress on it. It is using a simple Alpha-Beta algorithm.

In order to correct the Horizon-Effect, I tried to implement the Quiescence Search (and failed several times before it worked). The strength of the engine seems to have improved quiet a bit from that, but it is terribly slow!

Before, I could search to a 6 ply depth in about 160 secs (somewhere in a midgame state), with the quiescent search, it takes the computer about 80secs to get a move on search depth 3!

The brute-force node counter is at about 20000 Nodes at depth 3, while the quiescent node counter is up to 20 millions!

Since this is my first chess engine, I don't really know if those numbers are normal or if I might have made a mistake in my Quiescence-Algorithm. I would appreciate if someone more experienced could tell me what the usual ratio of BF Nodes/Quiescent nodes is.

Btw, just to have a look at: (this Method is called by the BF tree whenever the searchdepth is 0)

public static int QuiescentValue(chessBoard Board, int Alpha, int Beta)
    {
        QuiescentNodes++;

        int MinMax = Board.WhoseMove; // 1 = maximierend, -1 = minimierend
        int Counter = 0;
        int maxCount;


        int tempValue = 0;
        int currentAlpha = Alpha;
        int currentBeta = Beta;
        int QuietWorth = chEvaluation.Evaluate(Board);

        if(MinMax == 1) //Max
        {
            if (QuietWorth >= currentBeta)
                return currentBeta;
            if (QuietWorth > currentAlpha)
                currentAlpha = QuietWorth;
        }

        else            //Min
        {
            if (QuietWorth <= currentAlpha)
                return currentAlpha;
            if (QuietWorth < currentBeta)
                currentBeta = QuietWorth;
        }




        List<chMove> HitMoves = GetAllHitMoves(Board);
        maxCount = HitMoves.Count;

        if(maxCount == 0)
            return chEvaluation.Evaluate(Board);


        chessBoard tempBoard;

        while (Counter < maxCount)
        {
            tempBoard = new chessBoard(Board);
            tempBoard.Move(HitMoves[Counter]);
            tempValue = QuiescentValue(tempBoard, currentAlpha, currentBeta);

            if (MinMax == 1) //maximierend
            {
                if (tempValue >= currentBeta)
                {
                    return currentBeta;
                }

                if (tempValue > currentAlpha)
                {
                    currentAlpha = tempValue;
                }

            }

            else            //minimierend
            {
                if (tempValue <= currentAlpha)
                {
                    return currentAlpha;
                }
                if (tempValue < currentBeta)
                {
                    currentBeta = tempValue;
                }
            }

            Counter++;
        }

        if (MinMax == 1)
            return currentAlpha;
        else
            return currentBeta;

    }

Recommended data format for describing the rules of chess

I'm going to be writing a chess server and one or more clients for chess and I want to describe the rules of chess (e.g. allowable moves based on game state, rules for when a game is complete) in a programming language independant way. This is a bit tricky since some of the chess rules (e.g. King Castling, en passent, draws based on 3 or more repeated moves) are based not only on the board layout but also on the history of moves.

I would prefer the format to be:

• textual
• human readable
• based on a standard (e.g. YAML, XML)
• easily parsable in a variety of languages

But I am willing to sacrifice any of these for a suitable solution.

My main question is: How can I build algorithms of such a complexity that operate on such complex state from a data format?

A followup queston is: Can you provide an example of a similar problem solved in a similar manner that can act as a starting point?

Edit: In response to a request for clarity -- consider that I will have a server written in Python, one client written in C# and another client written in Java. I would like to avoid specifying the rules (e.g. for allowable piece movement, circumstances for check, etc.) in each place. I would prefer to specify these rules once in a language independant manner.

Jagged array versus one big array?

Not so sure how to ask this question, but I have 2 ways (so far) for a lookup array

Option 1 is:

bool[][][] myJaggegArray;

myJaggegArray = new bool[120][][];
for (int i = 0; i < 120; ++i)
{
  if ((i & 0x88) == 0)
  {
    //only 64 will be set
    myJaggegArray[i] = new bool[120][];
    for (int j = 0; j < 120; ++j)
    {
      if ((j & 0x88) == 0)
      {
        //only 64 will be set
        myJaggegArray[i][j] = new bool[60];
      }
    }
  }
}

Option 2 is:

bool[] myArray;
//                [998520]
myArray = new bool[(120 | (120 << 7) | (60 << 14))];

Both ways work nicely, but is there another (better) way of doing a fast lookup and which one would you take if speed / performance is what matter?

This would be used in a chessboard implementation (0x88) and mostly is

[from][to][dataX] for option 1

[(from | (to << 7) | (dataX << 14))] for option 2

Preventing cheating in online chess games?

In many online chess lobbies, I've seen instances of 'engining', where a cheater would open a chess program at the same time as the main game window. He would then set it up so that the opponent's moves are relayed to the computer, then which he would copy the computer's moves, until he (almost always) wins.

As a game developer and moderator, what is there to do about this situation?

Javascript chess notation conversion function

I am looking for a javascript library to convert PGN files with move notations including piece and destination like:

... 3. cxd5 Qxd5 ...

Into notation only with the square co-ordinates, like:

... 3. c4-d5 h5-d5 ...

Without a library, it would be a fair amount of work to make this rock solid, as it would have to step through each move, and validate legal moves to determine which piece can reach the destination square.

Is there anything in javascript to help me, or in another language that I could easily port?