Efficient method for combining multiple lists based on item weights

Question

Efficient method for combining multiple lists based on item weights

I am writing a chess engine, and I need an efficient way to merge several lists into a single list, ordered by the smallest value.

Each list is, in fact, a group of chess pieces that are already ordered in a perfect attack order. For example, I have a white queen on a2, a white bishop on b3, a white rook on f1, and a white rook on f2. Now say that I have a black pawn on f7, then all four white pieces converge on square f7 from two different discrete directions - in the northeast (queen and bishop) and in the north (rooks).

These two groups will be arranged as follows:

Group A) 1st-Bishop (b3); 2nd Queen (a2)
Group B) 1st rook (f2); 2nd - Rook (f1)

Now, using the point system below, I expect both lists to be combined into one list in the following order (lowest value to highest value): Bishop (b3), Rook (f2), Rook (f1) and finally Queen ( A2).

Queen = 900 points
Rook = 500 points
Bishop = 375 points
Knight = 350 points
Pawn = 100 points

Some codes:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SO_22015528
{
  public enum eRayDirection
  {
    North,
    NorthEast,
    East,
    SouthEast,
    South,
    SouthWest,
    West,
    NorthWest
  }

  public enum ePieceType
  {
    Empty = 0,
    Pawn = 1,
    Knight = 2,
    Bishop = 3,
    Rook = 4,
    Queen = 5,
    King = 6
  }

  public struct BoardPosition : IComparable<BoardPosition>
  {
    public int File;
    public int Rank;
    public int Square;

    public BoardPosition( int square )
    {
      Square = square;
      File = square % 7;
      Rank = 8 - ( square >> 3 );
    }

    public static Boolean operator >( BoardPosition b1, BoardPosition b2 )
    {
      return ( b1.Rank > b2.Rank ) || ( b1.Rank == b2.Rank && b1.File < b2.File );
    }

    public static Boolean operator <( BoardPosition b1, BoardPosition b2 )
    {
      return ( b1.Rank < b2.Rank ) || ( b1.Rank == b2.Rank && b1.File > b2.File );
    }

    public int CompareTo( BoardPosition obj )
    {
      if ( this < obj ) return 1;
      else if ( this > obj ) return -1;
      else return 0;
    }
  }

  public class ChessPiece
  {
    public int Value { get; set; }
    public ePieceType Type { get; set; }
    public int Square { get; set; }
    public BoardPosition XY
    {
      get
      {
        return new BoardPosition( this.Square );
      }
    }
    public ChessPiece( ePieceType type, int value, int square )
    {
      Value = value;
      Type = type;
      Square = square;
    }
  }

  public class Constraint
  {
    public ChessPiece Piece { get; set; }
    public eRayDirection Ray { get; set; }
    public Constraint( ChessPiece piece, eRayDirection ray )
    {
      Piece = piece;
      Ray = ray;
    }
    public override string ToString()
    {
      return String.Format( "{0} {1} {2}", Piece.Square, Piece.Type, Ray );
    }
  }

}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SO_22015528
{
  class Program
  {
    static void Main( string[] args )
    {
      // test code
      ChessPiece a2 = new ChessPiece( ePieceType.Queen, 900, 48 );
      ChessPiece b3 = new ChessPiece( ePieceType.Bishop, 375, 41 );
      ChessPiece f1 = new ChessPiece( ePieceType.Rook, 500, 61 );
      ChessPiece f2 = new ChessPiece( ePieceType.Rook, 500, 53 );

      // This just simulates pieces that attack on the f7 square.
      List<Constraint> f7 = new List<Constraint>();
      f7.Add( new Constraint( b3, eRayDirection.NorthEast ) );
      f7.Add( new Constraint( a2, eRayDirection.NorthEast ) );
      f7.Add( new Constraint( f1, eRayDirection.North ) );
      f7.Add( new Constraint( f2, eRayDirection.North ) );

      // Get all positive ray directions ( use to simplify LINQ orderby )
      List<eRayDirection> positiveRayDirections = new List<eRayDirection>();
      positiveRayDirections.Add( eRayDirection.North );
      positiveRayDirections.Add( eRayDirection.NorthEast );
      positiveRayDirections.Add( eRayDirection.NorthWest );
      positiveRayDirections.Add( eRayDirection.West );

      var groups = f7
        .GroupBy( g => g.Ray )
        .Select( a =>
        new
        {
          Key = a.Key,
          Results = positiveRayDirections.Contains( a.Key ) ? a.OrderBy( x => x.Piece.XY ).ToList() : a.OrderByDescending( x => x.Piece.XY ).ToList()
        } ).ToList();

              // The groups object returns two discrete groups here; 
              // NorthEast containing 2 entries (Bishop & Queen) and North 
              // also containing to entries (Rook x 2).
      List<Constraint> attackOrder = new List<Constraint>();

      List<Int32> groupIndicies = new List<Int32>( groups.Count() );
      for ( int n = 0; n < groups.Count(); n++ )
        groupIndicies.Add( 0 );

      while ( true )
      {
        Int32 value = Int32.MaxValue;
        Int32 groupIndex = -1;

        for ( int n = 0; n < groups.Count(); n++ )
        {
          var g = groups[ n ];
          int gIndex = groupIndicies[ n ];

          if ( gIndex < g.Results.Count && g.Results[ gIndex ].Piece.Value < value )
          {
            value = g.Results[ gIndex ].Piece.Value;
            groupIndex = n;
          }
        }

        if ( groupIndex < 0 )
          break;

        attackOrder.Add( groups[ groupIndex ].Results[ groupIndicies[ groupIndex ] ] );

        groupIndicies[ groupIndex ]++;

      }

              foreach ( var ao in attackOrder )
                  Console.WriteLine( ao.ToString() );

      Console.ReadKey();
    }
  }
}

I don't think the last bit is very efficient, and I would appreciate it if someone could find a much simpler way to do this.

+4

c # linq chess

Intrepid Feb 25 '14 at 13:22

source share

4 answers

, quicksort, , .

Order the lists individually.
Create the empty Final list.

do
{
   consider the first item in each of the sorted lists and find the highest ranking candidate.
   remove the item from its sorted list and add it to the final list.
} 
until all of the sorted lists are empty.

+1

Tormod 25 . '14 15:39

. SelectMany() groups OrderByDescending() Constraint.Piece.Value. . :

List<Constraint> attackOrder = groups.SelectMany(x => x.Results).OrderByDescending(x => x.Piece.Value).ToList();

, :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SO_22015528
{
  class Program
  {
    static void Main( string[] args )
    {
      // test code
      ChessPiece a2 = new ChessPiece( ePieceType.Queen, 900, 48 );
      ChessPiece b3 = new ChessPiece( ePieceType.Bishop, 375, 41 );
      ChessPiece f1 = new ChessPiece( ePieceType.Rook, 500, 61 );
      ChessPiece f2 = new ChessPiece( ePieceType.Rook, 500, 53 );

      // This just simulates pieces that attack on the f7 square.
      List<Constraint> f7 = new List<Constraint>();
      f7.Add( new Constraint( b3, eRayDirection.NorthEast ) );
      f7.Add( new Constraint( a2, eRayDirection.NorthEast ) );
      f7.Add( new Constraint( f1, eRayDirection.North ) );
      f7.Add( new Constraint( f2, eRayDirection.North ) );

      // Get all positive ray directions ( use to simplify LINQ orderby )
      List<eRayDirection> positiveRayDirections = new List<eRayDirection>();
      positiveRayDirections.Add( eRayDirection.North );
      positiveRayDirections.Add( eRayDirection.NorthEast );
      positiveRayDirections.Add( eRayDirection.NorthWest );
      positiveRayDirections.Add( eRayDirection.West );

      var groups = f7
        .GroupBy( g => g.Ray )
        .Select( a =>
        new
        {
          Key = a.Key,
          Results = positiveRayDirections.Contains( a.Key ) ? a.OrderBy( x => x.Piece.XY ).ToList() : a.OrderByDescending( x => x.Piece.XY ).ToList()
        } ).ToList();

              // The groups object returns two discrete groups here; 
              // NorthEast containing 2 entries (Bishop & Queen) and North 
              // also containing to entries (Rook x 2).
      List<Constraint> attackOrder = groups.SelectMany(x => x.Results).OrderByDescending(x => x.Piece.Value).ToList();

      foreach ( var ao in attackOrder )
          Console.WriteLine( ao.ToString() );

      Console.ReadKey();
    }
  }
}

+1

Wasif Hossain 25 . '14 17:34

, : . , .

/// <summary>
/// Merges the incoming sorted streams of items into a single sorted stream of items, using the provided comparison function
/// </summary>
public static IEnumerable<T> MergeMany<T>(Comparison<T> comparison, params IEnumerable<T>[] collections)
{
  var liveEnumerators = new PriorityQueue<IEnumerator<T>>((e1, e2) => comparison(e1.Current, e2.Current));

  // start each enumerator and add them to the queue, sorting by the current values.
  // Discard any enumerator that has no item
  foreach (var coll in collections)
  {
    var enumerator = coll.GetEnumerator();
    if (enumerator.MoveNext())
      liveEnumerators.Push(enumerator);
  }

  while (liveEnumerators.Any())
  {
    // pull an enumerator off the queue and yield its current item
    var enumerator = liveEnumerators.Pop();
    yield return enumerator.Current;

    // if it has more items, throw it back on the queue, sorting using its new current item.
    if (enumerator.MoveNext())
      liveEnumerators.Push(enumerator);
  }
}

, , . , , , . , , NorthEast, [, ] , [, ], , Merge d [, , , ]. , .

, PriorityQueue, .

+1

CSJ 25 . '14 19:52

Intrepid · Accepted Answer · 2014-03-06T12:21:09+0000

, LINQ . LINQ 12x.

Efficient method for combining multiple lists based on item weights

More articles: