Discussion: How would you program a chess game?

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

40 Replies - 8162 Views - Last Post: 02 August 2012 - 11:07 AM Rate Topic: -----

#1 OldWolf  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 13-July 12

Discussion: How would you program a chess game?

Posted 24 July 2012 - 03:23 PM

The idea here is to discuss interesting and unique ways to solve various problems with programming a chess game. There is not specific platform or language requirement, so use whatever you're comfortable with! I'll try to keep the conversation moving by posting different aspects of the game of chess to consider. When it appears time, I'll post another.

I think he might have been quoting or paraphrasing someone, but a programmer I hold in the highest respects (my Dad) once said, "A computer will do exactly what you tell it to. There are a million ways to do what you want, the problem is there are a trillion ways to do absolutely nothing." In that light, I'd like to see as many unique and crazy ways of doing things as possible.

Basic Rules apply:
*Don't get offended
*Disagree politely
*Remember, you can't convert. You can only present your case and hope they select.

-Matt

The first topic I'd like to broach is the idea of creating the chess board.

To wit, how would you do it? 2-dimensional array? For Next Loops? What?

Is This A Good Question/Topic? 1
  • +

Replies To: Discussion: How would you program a chess game?

#2 calvinthedestroyer  Icon User is offline

  • D.I.C Lover

Reputation: 167
  • View blog
  • Posts: 1,908
  • Joined: 13-October 07

Re: Discussion: How would you program a chess game?

Posted 24 July 2012 - 03:54 PM

Who is "he"?....
Was This Post Helpful? -1
  • +
  • -

#3 jared.deckard  Icon User is offline

  • New D.I.C Head

Reputation: 18
  • View blog
  • Posts: 46
  • Joined: 11-July 12

Re: Discussion: How would you program a chess game?

Posted 24 July 2012 - 04:46 PM

Here is what I have so far:
  • The board is a 2D array of pieces
  • Piece is an interface implemented by each specific piece class
  • All pieces have a Color and Position
  • All pieces have a reference to the game board
  • Pieces can be moved and determine their valid positions


Interesting objectives:
  • Keep as much of the logic out of a central "player" as possible
  • Allow the board size to scale arbitrarily
  • Allow the board state to serialize efficiently for simulation
  • Maintain a simulation tree for AI


C# Chess
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Chess
{
	enum Team { Black, White };

	interface Piece
	{
		// Piece properties
		public Team Color { get; private set; }
		public Point Position{ get; private set; }
		private Piece[][] Board;

		// Piece constructor
		public Piece(Team _color, Point _position, ref Piece[][] _board)
		{
			Color = _color;
			Position = _position;
			Board = _board;
		}

		// Calculate valid moves with consideration to Board
		public List<Point> ValidMoves();

		// Update Position and Board
		public void Move(Point _position);
	}
}


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Chess
{
	public class Chess
	{
		Piece[,] board;

		Chess()
		{
			board = new Piece[8, 8];

			// Place pieces on board
		}
	}
}


Was This Post Helpful? 1
  • +
  • -

#4 BobRodes  Icon User is offline

  • Your Friendly Local Curmudgeon
  • member icon

Reputation: 574
  • View blog
  • Posts: 2,989
  • Joined: 19-May 09

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 07:18 AM

Jared, this is good stuff. Oldwolf and I came up with some of it on another thread, and we're thinking along the same lines you are.

Now, we were thinking also about how to represent the board in a UI. I'm seeing one graphic per piece per color per square color; for example a black bishop on a white square would be one graphic, and a black bishop on a black square would be another.

So, I like your simplification of having simply a piece object rather than a piece and a square object, if it can be pulled off. How would you deal with empty squares on the board, since there is no piece on them? Are you saying that a "Piece" is analogous in your construction to a "Square" IRL, which can have a piece on it or not? That said, would you put all the move logic for all of the pieces into a Piece (as you define it) object?

This post has been edited by BobRodes: 26 July 2012 - 07:25 AM

Was This Post Helpful? 0
  • +
  • -

#5 OldWolf  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 13-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 08:47 AM

I literally just got off the phone with my Dad a few minutes ago, we were discussing the pros and cons of having a 'Piece' object in addition to the 'Square' object. Like Mr. Rodes said, I have been using an array of squares...

Public Board(Me.MaxFile, Me.MaxRank) As Square


...where Piece is simply an sByte parameter of each square.

In your case, Jared, it appears you're doing something similar. Did you intend to create 64 pieces and 'morph' them as moves are made? I can see that working one of two ways:

1) Have a 'null' or 'empty' piece-type/parameter that represents an empty square
2) Only create the number of pieces you require and move them (change their position) around the 'board' as required.

Interestingly enough it strikes me that in your system, an empty square doesn't really even need to exist. The 'position' of each piece (I assume stored as (x,y) in some fashion...not really familiar with C#, but I don't see any declaration) can be changed as part of a move and then the 'positions' of all other pieced checked to see if there is another piece there.
Was This Post Helpful? 0
  • +
  • -

#6 jared.deckard  Icon User is offline

  • New D.I.C Head

Reputation: 18
  • View blog
  • Posts: 46
  • Joined: 11-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 09:33 AM

Empty spots on the board are null.

The board will retain the location of each piece inherently, but each piece will be "aware" of its location locally. This structure will allow a piece to know its own position without checking the board, yet allow the piece to check the position of other pieces on the board.

Each move would require the piece's position property to be updated, the piece to be stored in a new "square" on the board, and it's previous position on the board to be null.
Was This Post Helpful? 0
  • +
  • -

#7 OldWolf  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 13-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 09:47 AM

If you want to maintain persistence of individual pieces, that makes sense to me.

Is there anything to gain from being able to 'move' pieces around the board instead of simply creating a new piece-object at the new location and destroying the piece-object at the old location? What is the advantage of the piece 'knowing' it's location?
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7629
  • View blog
  • Posts: 12,857
  • Joined: 19-March 11

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 10:02 AM

Interesting timing for this discussion. I'm just working on a project with another DIC head (Sheph) to develop a generic game-playing framework, the purpose being to allow us to run java challenges for creating Players and playing them against each other in a sort of algorithmic tournament. Of course, to do this, you have to have a framework for developing generic games, and I think we've got a pretty good one.

It's still in pretty rough state, but if you're thinking about developing a chess game that allows you to run automated tournaments, there might be some useful logic in there. If anyone's interested in trying to write a chess game in java using this framework, we'd love to have you in and playing with it. It might be sensible to start with something simpler, though - in the current state of development, I'd be happy to have a dozen people write their versions of tic-tac-toe and rock, paper, scissors, just to get the reactions.

If you want to see what we've got so far, here's a link to the repo. There's also a prose document which is a good overview of the Game model.
Obviously, any feedback is welcome. I've set up a "guest book" page in the wiki, feel free to leave any feedback there. If you get to the point of actually building it, and you file a bug, I'll be very happy.
Was This Post Helpful? 0
  • +
  • -

#9 BobRodes  Icon User is offline

  • Your Friendly Local Curmudgeon
  • member icon

Reputation: 574
  • View blog
  • Posts: 2,989
  • Joined: 19-May 09

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 10:55 AM

Interestingly, this is a micro example of "sparse matrix" vs. "dense matrix." When Lotus 1-2-3 switched to a sparse matrix algorithm to store spreadsheets, their calc times got significantly faster and they were able to support larger sheets as well. The point is that sparse matrix algorithms only store nonzero values.

I'm not sure whether this makes a difference in any meaningful way with 64 items in a matrix, however. To me, the largest overhead is sorting through the move logic. Whichever algorithm best supports the most simple way of applying move logic is the one I would go with.

To get some idea of the complexities involved in move logic, I would suggest that you consider implementations of pawn move logic, since it's the most complicated. Let's see:

pawn move one square forward allowed if empty square, not allowed if not.
pawn move two squares forward allowed if on second rank, and empty square, and intervening square is empty.
pawn move diagonally forward left or right: allowed if occupied by piece of opposite color. If not occupied, allowed if an opposing pawn (and only a pawn) is one square in front of unoccupied square, and on previous move was one square behind it ("en passant" rule).
Concepts of "forward" relative to coordinates are for white pieces and are reversed for black pieces, i. e. second rank for white pieces is seventh rank for black; adding one to y coordinate moves white forward, subtracting one moves black.
Once move is validated, change coordinates to new ones. Remove any piece on same coordinates. In the case of "en passant" above, remove piece (which will always be a pawn) on coordinate of square behind new coordinates.
If pawn moves to 8th rank (first rank as black), piece changes immediately to any piece save king or pawn, at user's choice.
Was This Post Helpful? 0
  • +
  • -

#10 jared.deckard  Icon User is offline

  • New D.I.C Head

Reputation: 18
  • View blog
  • Posts: 46
  • Joined: 11-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 11:30 AM

View PostOldWolf, on 26 July 2012 - 09:47 AM, said:

Is there anything to gain from being able to 'move' pieces around the board instead of simply creating a new piece-object at the new location and destroying the piece-object at the old location? What is the advantage of the piece 'knowing' it's location?


Each piece needs to "remember" its position so it doesn't have to search the board for itself. Having the board as a 2D array allows a piece to quickly check a position without looping over all the pieces to check their positions. Since we are storing a reference to the pieces on the board, it is more efficient to move an existing piece than to create a new one.

public void Move(Point _position){
    // TODO: Check to see if I am taking a piece or just moving
    Board[_position.X,_position.Y] = this;
    Position = _position;
}



In ValidMoves() the piece will check positions this way:
Board[possibleX,possibleY]


Also [][] in the Piece interface should be [,] for board. Oops. I will start a repo if the code gets enough attention.
Was This Post Helpful? 0
  • +
  • -

#11 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7629
  • View blog
  • Posts: 12,857
  • Joined: 19-March 11

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 11:41 AM

Quote

Each piece needs to "remember" its position so it doesn't have to search the board for itself.


There's a DRY violation there. You're storing that information in two places - this can be worth doing, but it poses the usual potential problems and requires some attention that you want to devote to other things.

I'd be tempted to have the Board maintain a list of locations that can be queried by Piece. Then a piece gets its location by asking the Board. Still double-representation, but it centralizes responsibility for tracking that information, which helps.
Was This Post Helpful? 0
  • +
  • -

#12 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 11:45 AM

Well... A 2D board is the obvious choice. Screw obvious. :P

I have to allow for six pieces, two sides, and empty. I can represent all square possibilities in a nibble, so a board in 32 bytes:
1000 BLACK_MASK
0000 WHITE_MASK
0111 PIECE_MASK

0000 Empty

0001 W Pawn
0010 W Bishop
0011 W Knight
0100 W Rook
0101 W Queen
0110 W King

1001 B Pawn
1010 B Bishop
1011 B Knight
1100 B Rook
1101 B Queen
1110 B King



Why? Well, because it's silly. However, chess heuristics are massive. For the geometric progression of the search trees, a small package isn't that bad an idea. You can also compare in strange and curious fashions this way. Not sure if that's helpful, but an eight int compare would be damn fast. I wonder if the dance of bits would be allow of some genetic algorithm connections that humans wouldn't see...
Was This Post Helpful? 2
  • +
  • -

#13 OldWolf  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 13-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 01:45 PM

It would seem the topic has shifted pretty quickly to pieces and how they are represented. Should they be instantiated objects that move around a virtual board? Does the board even need to exist if each piece has it's own coordinates? Does each piece have to be unique, or is each type of piece it's own class of object that would be a property of a given square?

I wouldn't say for certain that Chess heuristics are really all that 'massive' though I admit it depends on what you're comparing to.

What I did in my first version of my chess game was to create an array of 'Square' objects, each had a signed byte property called 'Piece'. I didn't have to worry about piece locations, because the pieces never moved...in fact they didn't exist in the first place. My Move logic would determine the piece being moved and, using a CASE SELECT command would proceed down the piece-specific move rules. After more though I am converting from an signed byte to a custom set of Piece objects for application specific reasons.

I bring up the signed byte parameter concept because it gave some very specific advantages, the greatest of which was that my move logic was color-independant. Negative values were black pieces and positive values were white. CASE SELECT used the absolute value to determine type of piece (pawn, knight, etc) and the actual move logic used the sign to determine allowable directions or if a piece could take another piece. Sadly, I will be losing these advantages.

Examples:

(BTW, variables that start with 'f' or 's' are the final or starting versions. fFile,fRank is the square being moved TO, sPiece is the piece being moved, fPiece is the piece being taken, if any, etc...)

Select Case Math.Abs(sPiece)
                Case 0 'No piece was selected
                    IsMovingPiece = False
                Case 2 'A Knight was selected
                    If ((fFile - sFile) ^ 2 + (fRank - sRank) ^ 2 = 5) Then 'A knight can only move along the hypotenuse of a right triangle with sides of 2 and 1.  Pythagoras told me the hypotenuse squared was five.  I believe him.
                        TryToTakePiece()
                    Else
                        IllegalMove()
                    End If
End Select


Private Sub TryToTakePiece() 'Validates that the piece being taken, if any, is the opposite color
        If (fPiece > 0 And Not WhitesTurn) Or (fPiece < 0 And WhitesTurn) Or fPiece = 0 Then
            IsLegalMove()
        Else
            IllegalMove()
        End If
    End Sub



I like Baavgai's idea of using bitmasks, because it seems elegent and efficient. Would there be any real disadvantage to doing it as simply as that?
Was This Post Helpful? 0
  • +
  • -

#14 jared.deckard  Icon User is offline

  • New D.I.C Head

Reputation: 18
  • View blog
  • Posts: 46
  • Joined: 11-July 12

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 02:40 PM

View PostOldWolf, on 26 July 2012 - 01:45 PM, said:

I like Baavgai's idea of using bitmasks, because it seems elegent and efficient. Would there be any real disadvantage to doing it as simply as that?

It may create a more procedural program.
It looks great for simulation, but my instinct is object oriented design for game play.
Was This Post Helpful? 0
  • +
  • -

#15 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: Discussion: How would you program a chess game?

Posted 26 July 2012 - 05:49 PM

View PostOldWolf, on 26 July 2012 - 04:45 PM, said:

I wouldn't say for certain that Chess heuristics are really all that 'massive' though I admit it depends on what you're comparing to.


Probably everything but Go. There's a reason IBM's parallel computing research lab produced a chess computer. The trees get big and such trees lend themselves to parallel processing.

Quote

there are 318,979,564,000 possible ways to play the first four moves of chess.
-- http://ezinearticles...hess&id=1717732


View Postjared.deckard, on 26 July 2012 - 05:40 PM, said:

It may create a more procedural program.


This is bad why?

OOP allows for some very elegant solutions. It also can create a chaotic mess. The trick is balance.

By thinking in objects, you naturally break the game into a collection of pieces. However, the challenge of a game engine is traversing a decision tree. Analysis and copying are the largest considerations. You either copy a collection of pieces or a board.

Does the board have the brains or do the pieces? Either way works. The starting point leads to different solutions to problems.
Was This Post Helpful? 1
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3