Select X with Max(F(X))
I'm trying to write some AI for a game of check开发者_如何学Cers. 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;
}
}
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)));
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.
float max = validMoves.Max(m => BoardScore(opp, board.Clone().ApplyMove(m)));
var bestMove = validMoves
.Where(m => BoardScore(opp, board.Clone().ApplyMove(m)) == max)
.First();
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;
精彩评论