Question About CPP-C#, Performance, and Square Represenation

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bpfliegel
Posts: 71
Joined: Fri Mar 16, 2012 9:16 am

Re: Question About CPP-C#, Performance, and Square Represena

Post by bpfliegel » Sun Sep 30, 2012 9:03 pm

bpfliegel wrote:
rreagan wrote:
bpfliegel wrote:"It's also important to remember that speed is not everything. If you took the #1 top engine in the world and rewrote it in C# or Java, it would still be one of the top engines."

See the proof here:
https://github.com/bpfliegel/Portfish

For me what seems to be the most common problem when implementing a chess engine is C# is memory management. Every second we could create 10+ million objects, which puts a horrible pressure on the GC, so always reuse your objects, never recreate them (see the ObjectBroker.cs for a possible solution).

C vs C# speed ratio was at the end 1:2,7 in case of Portfish.

Good luck!
Balint
Hi Balint, that is very interesting! Do you know what the ELO difference is between Stockfish and Portfish? If Stockfish is about 2.7 times faster, I would guess the ELO difference is around 200 or so?
I think it is less (around 80 ELO), as it is stronger as Junior and Spike - well, according to my tests. So far, no real professional testing was carried out - I hope I start flaming and someone will test it for good :)

Cheers, Balint
Sorry, wanted to say -120 ELO (was absent in school, when they taught substraction). It is still less than expected by myself.

Best, Balint

User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Question About CPP-C#, Performance, and Square Represena

Post by emadsen » Mon Oct 01, 2012 5:39 pm

Erik, doesn't yield kill your performance? I also experimented with it (sounds logical), but had disappointing results.
I don't know. I haven't tested it extensively. The C# yield statement frees me from having to track state inside an enumerator. So I get the benefit of staged move generation (faster compared to generating all moves) without complicating the code. Considering my goal is to write a bug-free chess program from scratch, of modest playing strength- this is good enough for me.

I'd imagine your task is quite different. You're converting a world class codebase to another programming language. I get to look for big performance wins. You inherited hundreds of performance wins. Your job is to avoid performance losses :)
My C# chess engine: http://www.madchess.net

bpfliegel
Posts: 71
Joined: Fri Mar 16, 2012 9:16 am

Re: Question About CPP-C#, Performance, and Square Represena

Post by bpfliegel » Mon Oct 01, 2012 6:42 pm

emadsen wrote:You inherited hundreds of performance wins. Your job is to avoid performance losses :)
You put it into a quite interesting perspective. But it is quite correct I have to say - and was not an easy task at all :)

User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Question About CPP-C#, Performance, and Square Represena

Post by emadsen » Tue Oct 02, 2012 1:18 am

Balint,

No doubt it was a lot of work. Every language / framework has its own pitfalls, performance traps, and counter-intuitive behaviors.

The performance you get with C# is quite impressive, though not surprising to me. It is often the case that people tout an issue of importance on the margin and promote it as if it's the essential thing. Usually this is due to the triumph of marketing (a novice rider buying an expensive bicycle) but sometimes it's done to avoid self criticism (it can't be my code, it must be the language).

I have no doubt that among high-level languages, C and C++ compilers produce the fastest machine code. But there's more to writing fast code than selecting a programming language. The quality and efficiency of data structures / algorithms have a much greater impact on performance than choice of programming language.

-Erik
My C# chess engine: http://www.madchess.net

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Question About CPP-C#, Performance, and Square Represena

Post by stegemma » Tue Oct 02, 2012 8:57 am

I suggest you to create static array of the objects that you use frequently and then just assign values to free ones, instead of creating new objects. I use two array: one for nodes and one for moves. When i store a move, i write the data in a move object then increment the node index (or the node pointer) to access the next move. The same i do for nodes. For any node, keep the index to the first move object and maybe to the last (but this one is equal to the first of the following node). Because move and node are the more created/deleted objects, this could give you a big speed-up. I use this way to do since my assembly programs and is good even for new C++ engine.

Rein Halbersma
Posts: 685
Joined: Tue May 22, 2007 9:13 am

Re: Question About CPP-C#, Performance, and Square Represena

Post by Rein Halbersma » Tue Oct 02, 2012 11:04 am

emadsen wrote:The C# yield statement frees me from having to track state inside an enumerator. So I get the benefit of staged move generation (faster compared to generating all moves) without complicating the code. Considering my goal is to write a bug-free chess program from scratch, of modest playing strength- this is good enough for me.
Hi Erik,

IIRC, in on of your first posts you mentioned that your source code can be downloaded from your website, but I can't seem to locate it. Even though I'm programming in C++, I'm interested in how the yield method would simplify code for move generation. If you could provide a link or code snippet, that would be great!

Rein

User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Question About CPP-C#, Performance, and Square Represena

Post by emadsen » Wed Oct 03, 2012 2:48 pm

Rein,

My use of the yield statement is in code that's not ready for release. Here are some code snippets to give you sense of how it works.

I'll show the capture-only enumerator because it's simpler.

Code: Select all

public override IEnumerator<Move> GetEnumerator&#40;)
&#123;
    // Examine all pieces of the side that just moved in order of piece value descending.
    Moves colMoves;
    // Captures of queens
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Queens&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of rooks
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Rooks&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of bishops and knights
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Minors&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of pawns
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Pawns&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
&#125;
Find attackers of a piece.

Code: Select all

private Moves GetCapturesOfPieces&#40;List<Piece> Pieces&#41;
&#123;
	Moves colMoves = new Moves&#40;);
	foreach &#40;Piece objPiece in Pieces&#41;
	&#123;
		// Determine from which directions piece can be attacked.
		List<Direction> colAttackDirections = this.Board.GetAttackDirections&#40;objPiece.Square, this.Board.SideToMove&#41;;
		// Get attackers.
		List<Piece> colAttackers = this.Board.GetAttackers&#40;objPiece.Square, this.Board.SideToMove, colAttackDirections, false&#41;;
		foreach &#40;Piece objAttacker in colAttackers&#41;
		&#123;
			// Create move for attacker.
			Move objMove;
			int intLocationValue = objAttacker.GetLocationValue&#40;objPiece.Square&#41; - objAttacker.GetLocationValue&#40;objAttacker.Square&#41;;
			int intMaterialGainIfRecaptured = objPiece.MaterialValue - objAttacker.MaterialValue;
			if (&#40;objAttacker.ShortName == Piece.Pawn&#41; && &#40;objAttacker.On7thRank&#41;)
			&#123;
				// Code snipped for pawn promotion
			&#125;
			else
			&#123;
				objMove = new Move&#40;objAttacker.Square.Location, objPiece.Square.Location, objAttacker.ShortName,
              intLocationValue, true, objPiece.MaterialValue, intMaterialGainIfRecaptured&#41;;
				colMoves.Add&#40;objMove&#41;;
			&#125;
		&#125;                
	&#125;
	if (&#40;Pieces.Count > 0&#41; && &#40;Pieces&#91;0&#93;.ShortName == Piece.Pawn&#41; && &#40;this.Board.EnPassantSquare != null&#41;)
	&#123;
		Square objSquare = this.Board.EnPassantSquare.GetNeighbor&#40;Direction.BehindLeft&#41;;
		if &#40;objSquare.IsLegal && objSquare.IsOwnOccupied && &#40;objSquare.Piece.ShortName == Piece.Pawn&#41;)
		&#123;
			// Code snipped for en passant capture.
		&#125;
	&#125;
	foreach &#40;Move objMove in colMoves&#41;
	&#123;
		// Prioritize move.
		this.PrioritizeMove&#40;objMove&#41;;
	&#125;
	// Sort moves.
	colMoves.Sort&#40;this.MoveComparer&#41;;
	// Update node count.
	this.SearchStats.Nodes += colMoves.Count;
	return colMoves;
&#125;
The quiescence search uses the capture enumerator (this.GetCaptureSelector(SearchState, SearchDepth)). The foreach code invokes the enumerator, which runs until it encounters a yield return statement. At that point control is returned to the caller (the quiescence foreach loop). So if a capture of a queen causes a beta cutoff, the code does not waste time finding captures of rooks, bishops, etc. Of course this logic is possible using other techniques. The yield statement makes the code very clean. The enumerator does not have to track state (which pieces have been examined). Tracking state in the all-moves enumerator is more complex (Has the hash move been returned? Pawn promotions? Captures? Killers?)

Code: Select all

public override int RecurseQuiet&#40;SearchState SearchState, SearchDepth SearchDepth, int Alpha, int Beta&#41;
&#123;
    if &#40;SearchState == null&#41;
    &#123;
        throw new ArgumentException&#40;"SearchState is null.");
    &#125;
    if &#40;SearchDepth == null&#41;
    &#123;
        throw new ArgumentException&#40;"SearchDepth is null.");
    &#125;
    // Examine search state.
    this.ExamineSearchState&#40;SearchState&#41;;
    if (!SearchState.Continue&#41;
    &#123;
        // Search was interrupted.
        return SearchState.Evaluation.InterruptedSearchScore;
    &#125;
    // Search for a quiet position where no captures are possible.
    // Update selective depth.
    SearchState.SearchStats.SelectiveDepth = Math.Max&#40;SearchDepth.Depth, SearchState.SearchStats.SelectiveDepth&#41;;
    // Update nodes evaluated count.
    SearchState.SearchStats.NodesEvaluated++;
    // Determine static score.
    StaticScore objStaticScore = SearchState.Evaluation.GetStaticScore&#40;SearchState, SearchDepth, false, Alpha, Beta&#41;;
    if &#40;objStaticScore.Score >= Beta&#41;
    &#123;
        // Prevent worsening of position by making a bad capture.  Stand pat.
        // Beta cutoff
        return Beta;
    &#125;
    Alpha = Math.Max&#40;objStaticScore.Score, Alpha&#41;;
    // Initialize search stats.
    int intLegalCapture = 0;
    int intScore = Alpha - 1;
    foreach &#40;Move objMove in this.GetCaptureSelector&#40;SearchState, SearchDepth&#41;)
    &#123;
        if (!objMove.IsLegal.HasValue&#41;
        &#123;
            // Determine if move is legal.
            objMove.IsLegal = SearchState.Board.IsMoveLegal&#40;objMove&#41;;
        &#125;
        if &#40;objMove.IsLegal == true&#41;
        &#123;
            intLegalCapture++;
        &#125;
        else
        &#123;
            // Skip illegal move.
            continue;
        &#125;
        // Determine if move is futile.
        if &#40;this.IsMoveFutile&#40;SearchState, SearchDepth, objMove, intLegalCapture, objStaticScore, Alpha, Beta&#41;)
        &#123;
            // Move is too weak.
            SearchState.SearchStats.NodesPrunedFutility++;
            // Skip move.
            continue;
        &#125;
        // Play move.
        SearchState.Board.PlayMove&#40;objMove&#41;;
        // Search with full alpha / beta window.
        intScore = -this.RecurseQuiet&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -Beta, -Alpha&#41;;
        // Undo move.
        SearchState.Board.UndoMove&#40;);
        if &#40;intScore >= Beta&#41;
        &#123;
            // Position is not the result of best play by both players.
            SearchState.SearchStats.NodesPrunedAlphaBeta++;
            // Beta cutoff
            return Beta;
        &#125;
        Alpha = Math.Max&#40;intScore, Alpha&#41;;
    &#125;
    // Return score of best move.
    return Alpha;
&#125;
My C# chess engine: http://www.madchess.net

Rein Halbersma
Posts: 685
Joined: Tue May 22, 2007 9:13 am

Re: Question About CPP-C#, Performance, and Square Represena

Post by Rein Halbersma » Wed Oct 03, 2012 9:09 pm

Thanks, Erik, that's a really helpful explanation! Your code does what Fabien Letouzey was wishing for in this thread from last year. Would be nice to be able to do this in C++ as well.

Gerd Isenberg
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Question About CPP-C#, Performance, and Square Represena

Post by Gerd Isenberg » Wed Oct 03, 2012 9:14 pm

emadsen wrote:

Code: Select all

public override IEnumerator<Move> GetEnumerator&#40;)
&#123;
    // Examine all pieces of the side that just moved in order of piece value descending.
    Moves colMoves;
    // Captures of queens
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Queens&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of rooks
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Rooks&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of bishops and knights
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Minors&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
    // Captures of pawns
    colMoves = this.GetCapturesOfPieces&#40;this.Board.Pieces.Pawns&#40;this.Board.SideJustMoved&#41;);
    foreach &#40;Move objMove in colMoves&#41;
    &#123;
        // Select move.
        yield return objMove;
    &#125;
&#125;
The quiescence search uses the capture enumerator (this.GetCaptureSelector(SearchState, SearchDepth)). The foreach code invokes the enumerator, which runs until it encounters a yield return statement. At that point control is returned to the caller (the quiescence foreach loop). So if a capture of a queen causes a beta cutoff, the code does not waste time finding captures of rooks, bishops, etc. Of course this logic is possible using other techniques. The yield statement makes the code very clean. The enumerator does not have to track state (which pieces have been examined). Tracking state in the all-moves enumerator is more complex (Has the hash move been returned? Pawn promotions? Captures? Killers?)
That is really cool. Reminds me on coroutines. It seems Yield need to safe some state variables to "remember" which yield occurred last and to restore its scope and context later recursively on an extra stack for all those iterator objects along the current path searched.

How is Moves defined? List<Move>?

User avatar
emadsen
Posts: 195
Joined: Wed Apr 25, 2012 11:51 pm
Location: Naperville, IL, USA
Contact:

Re: Question About CPP-C#, Performance, and Square Represena

Post by emadsen » Thu Oct 04, 2012 12:45 am

Your code does what Fabien Letouzey was wishing for in this thread from last year.
Interesting. Well, if Fabien would like to use iterators, C# has them. At what cost to performance, I have no idea.
My C# chess engine: http://www.madchess.net

Post Reply