diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
index d94ed4e..54b239e 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
@@ -341,7 +341,7 @@ namespace Banshee.Collection.Database
 #region Get random methods
 
         private static RandomBy [] randoms = new RandomBy [] {
-            new RandomByTrack (), new RandomByArtist (), new RandomByAlbum (), new RandomByRating ()
+            new RandomByTrack (), new RandomByArtist (), new RandomByAlbum (), new RandomByRating (), new RandomByScore()
         };
 
         private DateTime random_began_at = DateTime.MinValue;
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByRating.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByRating.cs
index 0688372..35180c2 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByRating.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByRating.cs
@@ -31,129 +31,45 @@
 //
 
 using System;
-using System.Linq;
 
-using Hyena;
-using Hyena.Data;
-using Hyena.Data.Sqlite;
-
-using Banshee.ServiceStack;
 using Banshee.PlaybackController;
 
 namespace Banshee.Collection.Database
 {
-    public class RandomByRating : RandomBy
+    public class RandomByRating : RandomBySlot
     {
-        private static Random random = new Random ();
-
         private static string track_condition = String.Format ("AND (CoreTracks.Rating = ? OR (? = 3 AND CoreTracks.Rating = 0)) {0} ORDER BY RANDOM()", RANDOM_CONDITION);
-        private HyenaSqliteCommand query;
-        private int rating;
 
         public RandomByRating () : base (PlaybackShuffleMode.Rating)
         {
         }
 
-        protected override void OnModelAndCacheUpdated ()
-        {
-            query = null;
-        }
-
-        public override void Reset ()
-        {
-            rating = 0;
-        }
-
-        public override bool IsReady { get { return rating != 0; } }
-
-        public override bool Next (DateTime after)
-        {
-            Reset ();
-
-            // Default rating for unrated songs.
-            const int unrated_rating = 3;
-            // counts[x] = number of tracks rated x + 1.
-            int[] counts = new int[5];
-            // Get the distribution of ratings for tracks that haven't been played since stamp.
-            using (var reader = ServiceManager.DbConnection.Query (Query, after, after)) {
-                while (reader.Read ()) {
-                    int r = Convert.ToInt32 (reader[0]);
-                    int count = Convert.ToInt32 (reader[1]);
-
-                    if (r < 1 || r > 5) {
-                        r = unrated_rating;
-                    }
-
-                    counts[r - 1] += count;
-                }
-            }
-
-            if (counts.Sum () == 0) {
-                rating = 0;
-                return false;
-            }
-
-            // We will use powers of phi as weights. Such weights result in songs rated R
-            // played as often as songs rated R-1 and R-2 combined.
-            const double phi = 1.618033989;
-
-            // If you change the weights make sure ALL of them are strictly positive.
-            var weights = Enumerable.Range (0, 5).Select (i => Math.Pow (phi, i)).ToArray ();
-
-            // Apply weights to the counts.
-            var weighted_counts = counts.Select ((c, i) => c * weights[i]);
-
-            // Normalise the counts.
-            var weighted_total = weighted_counts.Sum ();
-            weighted_counts = weighted_counts.Select (c => c / weighted_total);
-
-            // Now that we have our counts, get a weighted random rating.
-            double random_value = random.NextDouble ();
-            int current_rating = 0;
-            foreach (var weighted_count in weighted_counts) {
-                current_rating++;
-                random_value -= weighted_count;
-                if (random_value <= 0.0) {
-                    break;
-                }
-            }
-
-            rating = current_rating;
-            return IsReady;
-        }
-
         public override TrackInfo GetTrack (DateTime after)
         {
-            var track = !IsReady ? null : Cache.GetSingle (track_condition, rating, rating, after, after);
+            var track = !IsReady ? null : Cache.GetSingle (track_condition, slot + 1, slot + 1, after, after);
             Reset ();
             return track;
         }
 
-        private HyenaSqliteCommand Query {
+        protected override int Slots {
+            get { return 5; }
+        }
+
+        protected override string QuerySql {
             get {
-                if (query == null) {
-                    query = new HyenaSqliteCommand (String.Format (@"
-                        SELECT
-                            CoreTracks.Rating, COUNT(*)
-                        FROM
-                            CoreTracks, CoreCache {0}
-                        WHERE
-                            {1}
-                            CoreCache.ModelID = {2} AND
-                            CoreTracks.LastStreamError = 0 AND
-                            (CoreTracks.LastPlayedStamp < ? OR CoreTracks.LastPlayedStamp IS NULL) AND
-                            (CoreTracks.LastSkippedStamp < ? OR CoreTracks.LastSkippedStamp IS NULL)
-                            {3}
-                        GROUP BY CoreTracks.Rating",
-                        Model.JoinFragment,
-                        Model.CachesJoinTableEntries
-                            ? String.Format ("CoreCache.ItemID = {0}.{1} AND", Model.JoinTable, Model.JoinPrimaryKey)
-                            : "CoreCache.ItemId = CoreTracks.TrackID AND",
-                        Model.CacheId,
-                        Model.ConditionFragment
-                    ));
-                }
-                return query;
+                return @"
+                    SELECT
+                        (CoreTracks.Rating - 1) AS Slot, COUNT(*)
+                    FROM
+                        CoreTracks, CoreCache {0}
+                    WHERE
+                        {1}
+                        CoreCache.ModelID = {2} AND
+                        CoreTracks.LastStreamError = 0 AND
+                        (CoreTracks.LastPlayedStamp < ? OR CoreTracks.LastPlayedStamp IS NULL) AND
+                        (CoreTracks.LastSkippedStamp < ? OR CoreTracks.LastSkippedStamp IS NULL)
+                        {3}
+                    GROUP BY Slot";
             }
         }
     }
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByScore.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByScore.cs
new file mode 100644
index 0000000..81f34de
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomByScore.cs
@@ -0,0 +1,76 @@
+//
+// RandomByScore.cs
+//
+// Author:
+//   Alexander Kojevnikov <alexander@kojevnikov.com>
+//
+// Copyright (C) 2009 Alexander Kojevnikov
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+using System;
+
+using Banshee.PlaybackController;
+
+namespace Banshee.Collection.Database
+{
+    public class RandomByScore : RandomBySlot
+    {
+        private static string track_condition = String.Format ("AND (CoreTracks.Score BETWEEN ? AND ? OR (? = 50 AND CoreTracks.Score = 0)) {0} ORDER BY RANDOM()", RANDOM_CONDITION);
+
+        public RandomByScore () : base (PlaybackShuffleMode.Score)
+        {
+        }
+
+        public override TrackInfo GetTrack (DateTime after)
+        {
+            int min = slot * 100 / Slots + 1;
+            int max = (slot + 1) * 100 / Slots;
+
+            var track = !IsReady ? null : Cache.GetSingle (track_condition, min, max, max, after, after);
+            Reset ();
+            return track;
+        }
+
+        protected override int Slots {
+            get { return 20; }
+        }
+
+        protected override string QuerySql {
+            get {
+                // NOTE: SQLite wrongly assumes that (-1)/5 == 0, the CASE WHEN works around this.
+                return @"
+                    SELECT
+                        CASE WHEN IFNULL(CoreTracks.Score, 0) = 0 THEN -1 ELSE (CoreTracks.Score - 1) * 20 / 100 END AS Slot, COUNT(*)
+                    FROM
+                        CoreTracks, CoreCache {0}
+                    WHERE
+                        {1}
+                        CoreCache.ModelID = {2} AND
+                        CoreTracks.LastStreamError = 0 AND
+                        (CoreTracks.LastPlayedStamp < ? OR CoreTracks.LastPlayedStamp IS NULL) AND
+                        (CoreTracks.LastSkippedStamp < ? OR CoreTracks.LastSkippedStamp IS NULL)
+                        {3}
+                    GROUP BY Slot";
+            }
+        }
+    }
+}
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/RandomBySlot.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomBySlot.cs
new file mode 100644
index 0000000..348a726
--- /dev/null
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/RandomBySlot.cs
@@ -0,0 +1,143 @@
+//
+// RandomBySlot.cs
+//
+// Authors:
+//   Elena Grassi <grassi.e@gmail.com>
+//   Alexander Kojevnikov <alexander@kojevnikov.com>
+//   Gabriel Burt <gburt@novell.com>
+//
+// Copyright (C) 2008 Elena Grassi
+// Copyright (C) 2009 Alexander Kojevnikov
+// Copyright (C) 2009 Novell, Inc.
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+//
+
+using System;
+using System.Linq;
+
+using Hyena;
+using Hyena.Data;
+using Hyena.Data.Sqlite;
+
+using Banshee.ServiceStack;
+using Banshee.PlaybackController;
+
+namespace Banshee.Collection.Database
+{
+    public abstract class RandomBySlot : RandomBy
+    {
+        private static Random random = new Random ();
+
+        private HyenaSqliteCommand query;
+        protected int slot;
+
+        public RandomBySlot (PlaybackShuffleMode mode) : base (mode)
+        {
+        }
+
+        protected override void OnModelAndCacheUpdated ()
+        {
+            query = null;
+        }
+
+        public override void Reset ()
+        {
+            slot = -1;
+        }
+
+        public override bool IsReady { get { return slot != -1; } }
+
+        public override bool Next (DateTime after)
+        {
+            Reset ();
+
+            // counts[x] = number of tracks in slot x.
+            int[] counts = new int[Slots];
+            int default_slot = (Slots - 1) / 2;
+
+            // Get the distribution for tracks that haven't been played since stamp.
+            using (var reader = ServiceManager.DbConnection.Query (Query, after, after)) {
+                while (reader.Read ()) {
+                    int s = Convert.ToInt32 (reader[0]);
+                    int count = Convert.ToInt32 (reader[1]);
+
+                    if (s < 0 || s >= Slots) {
+                        s = default_slot;
+                    }
+
+                    counts[s] += count;
+                }
+            }
+
+            if (counts.Sum () == 0) {
+                slot = -1;
+                return false;
+            }
+
+            // We will use powers of phi as weights. Such weights result in songs rated R played as often as songs
+            // rated R-1 and R-2 combined. The exponent is adjusted to the number of slots when it's different from 5.
+            const double phi = 1.618033989;
+
+            // If you change the weights make sure ALL of them are strictly positive.
+            var weights = Enumerable.Range (0, Slots).Select (i => Math.Pow (phi, i * 5 / (double) Slots)).ToArray ();
+
+            // Apply weights to the counts.
+            var weighted_counts = counts.Select ((c, i) => c * weights[i]);
+
+            // Normalise the counts.
+            var weighted_total = weighted_counts.Sum ();
+            weighted_counts = weighted_counts.Select (c => c / weighted_total);
+
+            // Now that we have our counts, get the slot a weighted random track belongs to.
+            double random_value = random.NextDouble ();
+            int current_slot = -1;
+            foreach (var weighted_count in weighted_counts) {
+                current_slot++;
+                random_value -= weighted_count;
+                if (random_value <= 0.0) {
+                    break;
+                }
+            }
+
+            slot = current_slot;
+            return IsReady;
+        }
+
+        private HyenaSqliteCommand Query {
+            get {
+                if (query == null) {
+                    query = new HyenaSqliteCommand (String.Format (QuerySql,
+                        Model.JoinFragment,
+                        Model.CachesJoinTableEntries
+                            ? String.Format ("CoreCache.ItemID = {0}.{1} AND", Model.JoinTable, Model.JoinPrimaryKey)
+                            : "CoreCache.ItemId = CoreTracks.TrackID AND",
+                        Model.CacheId,
+                        Model.ConditionFragment
+                    ));
+                }
+                return query;
+            }
+        }
+
+        protected abstract int Slots { get; }
+        protected abstract string QuerySql { get; }
+    }
+}
diff --git a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
index 1cd3493..8903ce4 100644
--- a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
+++ b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
@@ -36,7 +36,8 @@ namespace Banshee.PlaybackController
         Song,
         Artist,
         Album,
-        Rating
+        Rating,
+        Score
     }
 
     public class ShuffleModeChangedEventArgs : EventArgs
diff --git a/src/Core/Banshee.Services/Banshee.Services.csproj b/src/Core/Banshee.Services/Banshee.Services.csproj
index 3dbc078..d6a5ccc 100644
--- a/src/Core/Banshee.Services/Banshee.Services.csproj
+++ b/src/Core/Banshee.Services/Banshee.Services.csproj
@@ -294,6 +294,8 @@
     <Compile Include="Banshee.ServiceStack\JobScheduler.cs" />
     <Compile Include="Banshee.PlatformServices\ScreensaverManager.cs" />
     <Compile Include="Banshee.PlatformServices\IScreensaverManager.cs" />
+    <Compile Include="Banshee.Collection.Database\RandomByScore.cs" />
+    <Compile Include="Banshee.Collection.Database\RandomBySlot.cs" />
   </ItemGroup>
   <ItemGroup>
     <EmbeddedResource Include="Banshee.Services.addin.xml" />
diff --git a/src/Core/Banshee.Services/Makefile.am b/src/Core/Banshee.Services/Makefile.am
index dbb4f1b..c36d426 100644
--- a/src/Core/Banshee.Services/Makefile.am
+++ b/src/Core/Banshee.Services/Makefile.am
@@ -26,6 +26,8 @@ SOURCES =  \
 	Banshee.Collection.Database/RandomByAlbum.cs \
 	Banshee.Collection.Database/RandomByArtist.cs \
 	Banshee.Collection.Database/RandomByRating.cs \
+	Banshee.Collection.Database/RandomByScore.cs \
+	Banshee.Collection.Database/RandomBySlot.cs \
 	Banshee.Collection.Database/RandomByTrack.cs \
 	Banshee.Collection.Database/Tests/DatabaseAlbumInfoTests.cs \
 	Banshee.Collection.Database/Tests/DatabaseArtistInfoTests.cs \
diff --git a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
index 1702682..4dc07b7 100644
--- a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
+++ b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
@@ -101,6 +101,11 @@ namespace Banshee.Gui
                     Catalog.GetString ("Shuffle by _Rating"), null,
                     Catalog.GetString ("Play songs randomly, prefer higher rated songs"),
                     (int)PlaybackShuffleMode.Rating),
+
+                new RadioActionEntry ("ShuffleScoreAction", null,
+                    Catalog.GetString ("Shuffle by S_core"), null,
+                    Catalog.GetString ("Play songs randomly, prefer higher scored songs"),
+                    (int)PlaybackShuffleMode.Score)
             }, 0, OnActionChanged);
                 
             this["ShuffleOffAction"].IconName = "media-skip-forward";
@@ -108,6 +113,7 @@ namespace Banshee.Gui
             this["ShuffleArtistAction"].IconName = "media-playlist-shuffle";
             this["ShuffleAlbumAction"].IconName = "media-playlist-shuffle";
             this["ShuffleRatingAction"].IconName = "media-playlist-shuffle";
+            this["ShuffleScoreAction"].IconName = "media-playlist-shuffle";
 
             ServiceManager.PlaybackController.ShuffleModeChanged += OnShuffleModeChanged;
             ServiceManager.PlaybackController.SourceChanged += OnPlaybackSourceChanged;
@@ -205,6 +211,7 @@ namespace Banshee.Gui
             yield return (RadioAction)this["ShuffleArtistAction"];
             yield return (RadioAction)this["ShuffleAlbumAction"];
             yield return (RadioAction)this["ShuffleRatingAction"];
+            yield return (RadioAction)this["ShuffleScoreAction"];
         }
 
         IEnumerator IEnumerable.GetEnumerator ()
@@ -227,7 +234,7 @@ namespace Banshee.Gui
             "playback", "shuffle_mode",
             "off",
             "Shuffle playback",
-            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album, shuffle_rating)"
+            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album, shuffle_rating, shuffle_score)"
         );
     }
 }
