Friday, July 04, 2008

ADO.NET Entity Framework Vote of No Confidence?

Several MVPs and other .NET Entity Framework testers (partly from the NHibernate camp) signed an open letter some weeks ago describing their concerns on some design decisions and the current state of what is about to become version 1.0 of the ADO.NET Entity Framework. Here is Microsoft's Tim Mallalieu's response.

Now I won't pretend to be an expert on Entity Framework (I spent two or three days playing around with it). I do have some Hibernate experience though (admitted, in the Java space). So this clearly qualifies me to throw in my 5 cents too, now doesn't it? ;-)

Here is what I think:

INORDINATE FOCUS THE DATA ASPECT OF ENTITIES LEADS TO DEGRADED ENTITY ARCHITECTURES
To be honest, my Hibernate POJOs never contained any logic code, they were plain data holders. This was a design decision that always worked fine for me, even if luminaries like Martin Fowler tend to criticize it. I think the requirement to combine data and logic code in entity objects, although comprehendible from an OOP perspective, is kind of overrated. Anyway one can still place that code in partial classes, what else can we ask for? What might be problematic in some application scenarios is that entity classes are linked to the whole Entity Framework by inheritance and code. They cannot exist "standalone" (e.g. in another tier without EF being around). One alternative are dynamic proxy classes being generated at runtime, but they have some drawbacks as well.

EXCESS CODE NEEDED TO DEAL WITH LACK OF LAZY LOADING
Once again, some people can't live without lazy loading. But lazy loading also might open a can of worms, e.g. in distributed environments like the ones I have to deal with. LazyInitializationException, anybody? I mostly prefer other loading strategies, like "Join Fetch". It boils down whether you (A) want to abstract the fact that there is a SQL database behind the hoods and only want to work on a cloud of objects or (B) the reason you use an ORM is to prevent tight coupling, database dependency and writing loads of mapping, routine SQL and infrastructure code (transaction management, etc) on your own, but still need to be in control of when and how data access actually happens. I am more of kind (B). EntityCollection.Load is just fine for me!

SHARED, CANONICAL MODEL CONTRADICTS SOFTWARE BEST PRACTICES
In this case the "best practice" depends on the type of application one is building. Nobody is being forced to have only "one model to rule them all" - one can as well apply the EF model within a single layer only.

LACK OF PERSISTENCE IGNORANCE CAUSES BUSINESS LOGIC TO BE HARDER TO READ, WRITE, AND MODIFY, CAUSING DEVELOPMENT AND MAINTENANCE COSTS TO INCREASE AT AN EXAGGERATED RATE
While I agree that PI-support is desirable in this area, this is not really a killer argument in my current project scenario. And from what I have heard this issue is going to be addressed in EF V2.

EXCESSIVE MERGE CONFLICTS WITH SOURCE CONTROL IN TEAM ENVIRONMENTS
This is true, that was one of the first things I noticed when I got introduced to the Entity Framework.

But hey guys, this is only version 1.0 of the Entity Framework. To me it still looks promising. Please keep up the good work. And you have a Vote of Confidence from me!

Tuesday, July 01, 2008

Battleship Game Algorithm Explained (Part 4)

This is part 4 of the mini-series explaining the inner workings of the Cubido C# Pirates Winner Algorithm.

Please note:

This code was not optimized for speed and has plenty of potential for performance improvement, esp. regarding nested looping. The competition rules included an upper time limit of 500ms per shot. This implementation runs at 1ms per shot in average, so there was no point in tuning that esp. as readability might have suffered.

The algorithm does not take into consideration opponents' behavior. The C# Pirates competition environment itself placed the ships randomly, and did not provide state storage on any larger scope than a single game, so it was not possible to react on opponent's behavior when shooting, or on different ship placement strategies.

Here is the resulting sourcecode:

using System;
using System.Collections.Generic;
using SoftwareArchitects.Battleships;

namespace Battleships
{

  [Player(Name = "The Privateer")]
  public class ThePrivateer : Player
  {
    private class ShipPositionOption
    {
      private int free;
      private bool done;
      private Direction dir;
      private Coordinates nextCoord;

      public ShipPositionOption(Direction posDir)
      {
        dir = posDir;
        free = 0;
        done = false;
        nextCoord = null;
      }

      public void Reset()
      {
        free = 0;
        done = false;
        nextCoord = null;
      }

      public void MarkInvalid()
      {
        free = 0;
        done = true;
        nextCoord = null;
      }

      public Coordinates NextCoord
      {
        get { return nextCoord; }
        set { nextCoord = value; }
      }

      public int Free
      {
        get { return free; }
        set { free = value; }
      }

      public bool Done
      {
        get { return done; }
        set { done = value; }
      }

      public Direction Dir
      {
        get { return dir; }
      }

    }

    private class Direction
    {
      private Orientation orient;
      private int dX;
      private int dY;

      public Direction(Orientation or, int x, int y)
      {
        orient = or;
        dX = x;
        dY = y;
      }

      public Orientation Orient
      {
        get { return orient; }
      }

      public int DX
      {
        get { return dX; }
      }

      public int DY
      {
        get { return dY; }
      }
    }

    private class SinkTryResult
    {
      private Direction dir;
      private Coordinates sinkCoord;

      public SinkTryResult(Coordinates sinkCoordParam, Direction dirParam)
      {
        sinkCoord = sinkCoordParam;
        dir = dirParam;
      }

      public Coordinates SinkCoord
      {
        get { return sinkCoord; }
        set { sinkCoord = value; }
      }

      public Direction Dir
      {
        get { return dir; }
        set { dir = value; }
      }
    }

    private enum Orientation : int
    {
      EAST = 0,
      WEST = 1,
      NORTH = 2,
      SOUTH = 3
    }

    private enum Mode { ScanMode, SinkMode };

    private static readonly IDictionary<Orientation, Direction> DIRECTIONS = new Dictionary<Orientation, Direction>();
    private const int FIELD_DIM_X = 10;
    private const int FIELD_DIM_Y = 10;

    private const int EAST_IDX = (int)Orientation.EAST;
    private const int WEST_IDX = (int)Orientation.WEST;
    private const int SOUTH_IDX = (int)Orientation.SOUTH;
    private const int NORTH_IDX = (int)Orientation.NORTH;

    private Random rnd = new Random();
    private Mode mode = Mode.ScanMode;
    private Coordinates sinkCoord = null;
    private bool[,] impossibleCoords = new bool[10, 10];

    private int seekedShipSize = 5;
    private int hitCount = 0;

    private int[] sinksRequired = new int[] { 0, 0, 1, 2, 1, 1 };

    static ThePrivateer()
    {
      DIRECTIONS[Orientation.EAST] = new Direction(Orientation.EAST, 1, 0);
      DIRECTIONS[Orientation.WEST] = new Direction(Orientation.WEST, -1, 0);
      DIRECTIONS[Orientation.SOUTH] = new Direction(Orientation.SOUTH, 0, 1);
      DIRECTIONS[Orientation.NORTH] = new Direction(Orientation.NORTH, 0, -1);
    }

    public ThePrivateer()
    {
    }

    public override void Move(PlayingField playingField)
    {
      if (mode == Mode.ScanMode)
      {
        Coordinates coord = GetNextScanCoord(playingField);
        if (playingField.Fire(coord.X, coord.Y) == State.HitShip)
        {
          sinkCoord = coord;
          mode = Mode.SinkMode;
          hitCount = 1;
        }
      }
      else if (mode == Mode.SinkMode)
      {
        SinkTryResult sinkTry = GetNextSinkTry(playingField);

        State res = playingField.Fire(sinkTry.SinkCoord.X, sinkTry.SinkCoord.Y);

        if (res == State.HitShip || res == State.SunkShip)
        {
          sinkCoord = sinkTry.SinkCoord;
          hitCount++;

          if (res == State.SunkShip)
          {

            sinksRequired[hitCount] = sinksRequired[hitCount] - 1;

            int sunkX = sinkCoord.X;
            int sunkY = sinkCoord.Y;

            for (int i = 0; i < hitCount; i++)
            {
              SetImpossibleCoord(sunkX - 1, sunkY - 1);
              SetImpossibleCoord(sunkX - 1, sunkY);
              SetImpossibleCoord(sunkX - 1, sunkY + 1);
              SetImpossibleCoord(sunkX, sunkY - 1);
              SetImpossibleCoord(sunkX, sunkY);
              SetImpossibleCoord(sunkX, sunkY + 1);
              SetImpossibleCoord(sunkX + 1, sunkY - 1);
              SetImpossibleCoord(sunkX + 1, sunkY);
              SetImpossibleCoord(sunkX + 1, sunkY + 1);

              sunkX = sunkX - sinkTry.Dir.DX;
              sunkY = sunkY - sinkTry.Dir.DY;
            }

            while (seekedShipSize > 0 && sinksRequired[seekedShipSize] == 0)
            {
              seekedShipSize--;
            }

            hitCount = 0;
            sinkCoord = null;
            mode = Mode.ScanMode;
          }
        }
      }
    }

    private ShipPositionOption[] CreateShipPositionOptions()
    {
      ShipPositionOption[] options = new ShipPositionOption[4];
      options[EAST_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.EAST]);
      options[WEST_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.WEST]);
      options[SOUTH_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.SOUTH]);
      options[NORTH_IDX] = new ShipPositionOption(DIRECTIONS[Orientation.NORTH]);
      return options;
    }

    private Coordinates GetNextScanCoord(PlayingField playingField)
    {
      ShipPositionOption[] options = CreateShipPositionOptions();
      Coordinates bestCoord = null;
      int bestCnt = 0;
      int bestNeighborFact = 0;
      bool bestMatching = false;

      for (int x = 0; x < FIELD_DIM_X; x++)
      {
        for (int y = 0; y < FIELD_DIM_Y; y++)
        {
          if (IsUnknown(playingField, x, y))
          {
            int cnt = 0;
            int neighborFact = 0;

            for (int shipSize = 0; shipSize < sinksRequired.Length; shipSize++)
            {
              if (sinksRequired[shipSize] > 0)
              {
                for (int optIdx = 0; optIdx < options.Length; optIdx++)
                {
                  ShipPositionOption option = options[optIdx];
                  option.Reset();
                  for (int d = 1; d < shipSize && !option.Done; d++)
                  {
                    if (IsUnknown(playingField, x + d * option.Dir.DX, y + d * option.Dir.DY))
                    {
                      option.Free = option.Free + 1;
                    }
                    else
                    {
                      option.Done = true;
                    }

                  }

                }
                int cntHor = Math.Max(0, options[EAST_IDX].Free + options[WEST_IDX].Free + 2 - shipSize);
                int cntVer = Math.Max(0, options[SOUTH_IDX].Free + options[NORTH_IDX].Free + 2 - shipSize);
                cnt += cntHor + cntVer;

              }

            }

            foreach (Direction dir1 in DIRECTIONS.Values)
            {
              int x1 = x + dir1.DX;
              int y1 = y + dir1.DY;
              if (IsUnknown(playingField, x1, y1))
              {
                foreach (Direction dir2 in DIRECTIONS.Values)
                {
                  int x2 = x1 + dir2.DX;
                  int y2 = y1 + dir2.DY;
                  if (x2 != x || y2 != y)
                  {
                    if (IsWaterOrImpossible(playingField, x2, y2))
                    {
                      neighborFact++;
                    }
                  }
                }
              }
            }

            bool matching = MatchesScanPattern(x, y);
            if (cnt > bestCnt || (cnt == bestCnt && (neighborFact > bestNeighborFact || (neighborFact == bestNeighborFact && ((!bestMatching && matching) || (bestMatching == matching && rnd.Next(2) == 1))))))
            {
              bestCnt = cnt;
              bestNeighborFact = neighborFact;
              bestMatching = matching;
              bestCoord = new Coordinates(x, y);
            }
          }
        }
      }
      return bestCoord;
    }

    private SinkTryResult GetNextSinkTry(PlayingField playingField)
    {
      ShipPositionOption[] options = CreateShipPositionOptions();

      for (int i = 1; i < seekedShipSize && (!options[EAST_IDX].Done || !options[WEST_IDX].Done || !options[SOUTH_IDX].Done || !options[NORTH_IDX].Done); i++)
      {
        for (int optIdx = 0; optIdx < options.Length; optIdx++)
        {
          ShipPositionOption option = options[optIdx];
          if (!option.Done)
          {
            Coordinates nextCoord = new Coordinates(sinkCoord.X + i * option.Dir.DX, sinkCoord.Y + i * option.Dir.DY);
            if (!IsValidCoord(nextCoord) || impossibleCoords[nextCoord.X, nextCoord.Y])
            {
              option.Done = true;
            }
            else
            {
              State state = playingField.GetState(nextCoord.X, nextCoord.Y);
              if (state == State.Unknown)
              {
                if (option.NextCoord == null)
                {
                  option.NextCoord = nextCoord;
                }
                option.Free = option.Free + 1;
              }
              else if (state == State.HitShip)
              {
                if (option.Dir.Orient == Orientation.EAST || option.Dir.Orient == Orientation.WEST)
                {
                  options[SOUTH_IDX].MarkInvalid();
                  options[NORTH_IDX].MarkInvalid();
                }
                else
                {
                  options[EAST_IDX].MarkInvalid();
                  options[WEST_IDX].MarkInvalid();
                }
              }
              else
              {
                option.Done = true;
              }
            }
          }
        }
      }

      ShipPositionOption bestOpt;
      ShipPositionOption option1;
      ShipPositionOption option2;

      int horFree = options[EAST_IDX].Free + options[WEST_IDX].Free;
      int verFree = options[SOUTH_IDX].Free + options[NORTH_IDX].Free;
      int minHorFree = Math.Min(options[EAST_IDX].Free, options[WEST_IDX].Free);
      int minVerFree = Math.Min(options[SOUTH_IDX].Free, options[NORTH_IDX].Free);

      if (horFree > verFree || (horFree == verFree && (minHorFree > minVerFree || (minHorFree == minVerFree && rnd.Next(2) == 1))))
      {
        option1 = options[EAST_IDX];
        option2 = options[WEST_IDX];
      }
      else
      {
        option1 = options[SOUTH_IDX];
        option2 = options[NORTH_IDX];
      }

      if (option1.Free > option2.Free)
      {
        bestOpt = option1;
      }
      else if (option2.Free > option1.Free)
      {
        bestOpt = option2;
      }
      else
      {
        bestOpt = rnd.Next(2) == 1 ? option1 : option2;
      }

      return new SinkTryResult(bestOpt.NextCoord, bestOpt.Dir);
    }

    private bool IsUnknown(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && !impossibleCoords[x, y] && playingField.GetState(x, y) == State.Unknown;
    }

    private bool IsWater(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && playingField.GetState(x, y) == State.Water;
    }

    private bool IsWaterOrImpossible(PlayingField playingField, int x, int y)
    {
      return IsValidCoord(x, y) && (impossibleCoords[x, y] || playingField.GetState(x, y) == State.Water);
    }

    private bool MatchesScanPattern(Coordinates coord)
    {
      return coord != null && MatchesScanPattern(coord.X, coord.Y);
    }

    private bool MatchesScanPattern(int x, int y)
    {
      return (x + y) % 2 == 0;
    }

    private bool IsValidCoord(Coordinates coord)
    {
      return IsValidCoord(coord.X, coord.Y);
    }

    private bool IsValidCoord(int x, int y)
    {
      return x >= 0 && x < FIELD_DIM_X && y >= 0 && y < FIELD_DIM_Y;
    }

    private void SetImpossibleCoord(int x, int y)
    {
      if (IsValidCoord(x, y))
      {
        impossibleCoords[x, y] = true;
      }
    }

  }
}

Previous Postings: