Select X with Max(F(X))

Question

I'm trying to write some AI for a game of checkers. I want to select the move with the highest board score.

Need something like this:

var bestMove = from m in validMoves
                where BoardScore(opp, board.Clone().ApplyMove(m)) is max
                select m

Except I can't figure out the "is max" part. Would prefer it returns a single item rather than an enumerable too.

---

Basically, the equivalent of this:

Move bestMove = null;
float highestScore = float.MinValue;
foreach (var move in validMoves)
{
    float score = BoardScore(opp, board.Clone().ApplyMove(move));
    if (score > highestScore)
    {
        highestScore = score;
        bestMove = move;
    }
}

Answer 1

var scores = from m in validMoves
                select BoardScore(opp, board.Clone().ApplyMove(m));
var bestMove = scores.Max();

EDIT:

I should have read more closely. You can do:

var descendingMoves = validMoves.OrderByDescending(m=>BoardScore(opp, board.Clone().ApplyMove(m)));
var bestMove = descendingMoves.First();

But this is O(n log n). I found a blog post with discussion on this issue. It proposes a Max extension function that returns the maximum original value, rather than the transformed one. Unfortunately, I don't know of a way to do this in LINQ.

Answer 2

You're going to want to look at Enumerable.Max(TSource) Method (IEnumerable(TSource), Func(TSource, Single)). i.e.:

var bestMove = validMoves.Max((m)=>BoardScore(opp, board.Clone().ApplyMove(m)));

If the scores are expensive to compute, you might compute all scores up-front, pairing them with their corresponding move, but I doubt this will be necessary. Example:

var scores = from m in validMoves
             select new {Move=m, Score=BoardScore(opp, board.Clone().ApplyMove(m))};
var bestMove = scores.Max(s=>s.Score).Move;

Answer 3

Don't you basically already have this figured out? If you write your own extension method you can implement this functionality in typical LINQ fashion:

public static T MaxFrom<T, TValue>(this IEnumerable<T> source, Func<T, TValue> selector, IComparer<TValue> comparer)
{
    T itemWithMax = default(T);
    TValue max = default(TValue);

    using (var e = source.GetEnumerator())
    {
        if (e.MoveNext())
        {
            itemWithMax = e.Current;
            max = selector(itemWithMax);
        }

        while (e.MoveNext())
        {
            T item = e.Current;
            TValue value = selector(item);
            if (comparer.Compare(value, max) > 0)
            {
                itemWithMax = item;
                max = value;
            }
        }
    }

    return itemWithMax;
}

public static T MaxFrom<T, TValue>(this IEnumerable<T> source, Func<T, TValue> selector)
{
    return source.MaxFrom(selector, Comparer<TValue>.Default);
}

This way you could just do:

var bestMove = validMoves
    .MaxFrom(m => BoardScore(opp, board.Clone().ApplyMove(m)));

Answer 4

    float max = validMoves.Max(m => BoardScore(opp, board.Clone().ApplyMove(m)));
    var bestMove = validMoves
          .Where(m => BoardScore(opp, board.Clone().ApplyMove(m)) == max)
          .First();