Deep copying an array c# without serialization

Question

Basically I have the problem that my MinMax algorithm isn't really working as intended.

What I need is to make my array pieces be copied to newPieces so that pieces isn't changed when newPieces is.

Here is an extract of the MinMax algorithm:

private int MinMax(
    int depth, Piece[] pieces, bool blacksTurn, 
    List<Move> Moves, Game game, int alpha, Move nextMove) {

    Piece[] newPieces=new Piece[24];
    Moves=Game.possibleMoves(pieces, blacksTurn, false);
    if(depth==0||Moves.Count==0) {
        return Evaluation(ref pieces);
    }

    int value;

    if(blacksTurn==true) {
        foreach(Move i in Moves) {
            newPieces=DeepCopy.ObjectExtensions.Copy(pieces);
            game.MovePiece(newPieces, blacksTurn, i.Moving, i.Destination, true);
            game.DisplayBoard(pieces);
            value=minMax(depth-1, newPieces, !blacksTurn, Moves, game, alpha, nextMove);

            if(alpha>value) {
                alpha=value;
                nextMove=i;
            }

    // ... 

Here is the Piece class.

[StructLayout(LayoutKind.Sequential)]
public class Piece
{

    public CellReference Location;
    public bool isBlack { get; set; }
    public bool isKing { get; set; }
    private int Value { get; set; }
    public bool taken { get; set; }

    public Piece()
    {

    }

    public Piece(int i, bool isBlack, bool isKing, int CellsEast, int CellsNorth, bool taken)
    {
        this.Value = i;
        Location.CellsEast = CellsEast;
        Location.CellsNorth = CellsNorth;
        this.isBlack = isBlack;
        this.isKing = isKing;
        this.taken = taken;
    }
}

Henghold

Is Piece complex enough to warrant a class over a struct? Depending on what game this is, there is also the option of not copying the board at all but instead record information that will let you revert a move after it's been evaluated. – Grandioso

Is this question about a "more efficient deep copy" or is it about a "more efficient min-max"? – Myrtia

@DJKRAZE the OP asked specifically for a deep copy, MemberwiseClose is documented as performing a shallow copy – Thoughtless

That's correct Peter..I over looked that I will remove my comment – Deville

@500 I tried changing it to a struct, everything seemed to break so I changed it back. Also how would you suggest going about recording all of the information? – Henghold

Answer 1

Add attribute as this to class/structure Piece:

using System.Runtime.InteropServices;

[StructLayout(LayoutKind.Sequential)]
public class Piece {

And the code is following

namespace DeepCopy {
    public static class ObjectExtensions {
        public static T[] Copy<T>(this T[] pieces) {
            return pieces.Select(x => {
                var handle=Marshal.AllocHGlobal(Marshal.SizeOf(typeof(T)));

                try {
                    Marshal.StructureToPtr(x, handle, false);
                    return (T)Marshal.PtrToStructure(handle, typeof(T));
                }
                finally {
                    Marshal.FreeHGlobal(handle);
                }
            }).ToArray();
        }
    }
}

I temporarily modify Piece.Value to be public for the test, and have tested with a test class

public static partial class TestClass {
    public static void TestDeepCopy(Piece[] pieces) {
        Piece[] newPieces=new Piece[24];

        newPieces=DeepCopy.ObjectExtensions.Copy(pieces);

        newPieces[0].isKing=true;
        newPieces[0].Value=3;

        newPieces[1].isKing=true;
        newPieces[1].taken=true;
        newPieces[1].Value=4;

        Console.WriteLine("=== newPieces ===");
        foreach(var x in newPieces)
            Console.WriteLine(
                "x.isKing={0}; x.isBlack={1}; x.Value={2}",
                x.isKing, x.isBlack, x.Value
                );

        Console.WriteLine();
        Console.WriteLine("=== pieces ===");
        foreach(var x in pieces)
            Console.WriteLine(
                "x.isKing={0}; x.isBlack={1}; x.Value={2}",
                x.isKing, x.isBlack, x.Value
                );
    }

    public static void StartTest() {
        var pieceA=new Piece(1, false, false, 1, 1, false);
        var pieceB=new Piece(2, true, false, 1, 1, false);
        var pieces=new[] { pieceA, pieceB };
        TestDeepCopy(pieces);
    }
}

and it works. To perform the test, call

TestClass.StartTest();

Aponeurosis

It's still not working... I am frankly at a loss, every single copy seems to have the same results and the whole thing still doesn't work. – Henghold

Wow ... what did you do? What's the problem before ..? I'd like to discover that – Aponeurosis

Well its screwed up again but this time at least I know where the problem lies. It's not the copying at all it is in fact somewhere buried in my move function. I should actually be able to find the problem in there though. So your work was perfectly fine, it's just me that screwed it up ;D. – Henghold

Might want to be more careful with the AllocHGlobal. If it blows up while copying then you've got a memory leak. – Darkling

Answer 2

I would implement ICloneable ICloneable<T> on the Piece class.

public interface ICloneable<T>
{
    T Clone();
}

pieces.Select(p => p.Clone()).ToArray(); or just use a foreach loop.

Darkling

I suggest implementing just the Clone method. There's no benefit to implementing the ICloneable interface, and you can't even have the "nice" return type, forcing it to be object. – Omora

Or make an ICloneable<T>. – Darkling

When I do this it says it cannot convert type object[] to Piece[]. – Henghold

Implement ICloneable<T> on Piece or you'll need to cast it pieces.Select(p => (Piece)p.Clone()).ToArray(). – Darkling

Answer 3

I think this may help to solve your problem. It uses the ICloneable interface to make objects aware on how to clone themselves.

Hindrance