001 ///////////////////////////////////////////////////////////////////////////////
002 // Copyright (c) 2006, Frank S. Nestel, All Rights Reserved.
003 //
004 // This library is free software; you can redistribute it and/or
005 // modify it under the terms of the GNU Lesser General Public
006 // License as published by the Free Software Foundation; either
007 // version 2.1 of the License, or (at your option) any later version.
008 //
009 // This library is distributed in the hope that it will be useful,
010 // but WITHOUT ANY WARRANTY; without even the implied warranty of
011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012 // GNU General Public License for more details.
013 //
014 // You should have received a copy of the GNU Lesser General Public
015 // License along with this program; if not, write to the Free Software
016 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017 ///////////////////////////////////////////////////////////////////////////////
018
019 package de.spieleck.app.turn.pairing;
020
021 import java.util.Arrays;
022 import java.util.Random;
023 import java.util.HashMap;
024 import java.util.Iterator;
025
026 import org.apache.log4j.Logger;
027
028 import de.spieleck.app.turn.Game;
029 import de.spieleck.app.turn.Player;
030 import de.spieleck.app.turn.SplittingMode;
031 import de.spieleck.app.turn.PlayerRegistry;
032 import de.spieleck.app.turn.splitting.BaseSplitter;
033
034 /**
035 * A pairing mode which considers mixing players and placing close ranked players together.
036 *
037 * <p><a href="$URL: https://svn.sourceforge.net/svnroot/jtourney/src/de/spieleck/app/turn/pairing/MixingPairing.java $">$URL: https://svn.sourceforge.net/svnroot/jtourney/src/de/spieleck/app/turn/pairing/MixingPairing.java $</a></p>
038 *
039 * @author Frank S. Nestel
040 * @author $Author: nestefan $
041 * @version $Revision: 2 $ $Date: 2006-03-20 14:33:27 +0100 (Mo, 20 Mrz 2006) $ $Author: nestefan $
042 */
043 public class MixingPairing
044 extends BasePairing
045 {
046 private final static Logger L = Logger.getLogger(MixingPairing.class);
047
048 private HashMap<Player,WrappedPlayer> ref = new HashMap<Player,WrappedPlayer>();
049
050 public Game[] pairing(int round, PlayerRegistry pRegistry, SplittingMode sm)
051 {
052 Player[] standing = pRegistry.getActivePlayers();
053 Arrays.sort(standing);
054 int n = standing.length;
055 WrappedPlayer[] wps = new WrappedPlayer[n];
056 for(int i = 0; i < n; i++)
057 {
058 wps[i] = new WrappedPlayer(standing[i], i);
059 ref.put(standing[i], wps[i]);
060 }
061 Arrays.sort(wps);
062 for(int i = 0; i < wps.length; i++) L.debug(" "+i+". "+wps[i].p+" "+wps[i].differentOpponents+" "+wps[i].opponents+" "+wps[i].rank);
063 int[] splitting = sm.split(n);
064 int[] counts = BaseSplitter.transposeSplit(splitting);
065 //
066 // Put the small numbers on the end!
067 for(int i = 0; 2*i < counts.length; i++)
068 {
069 int h = counts[i];
070 counts[i] = counts[counts.length - 1 - i];
071 counts[counts.length - 1 - i] = h;
072 }
073 for(int i = 0; i < counts.length; i++) L.debug(" c["+i+"]="+counts[i]);
074 //
075 // locate players with too few opponents
076 GameImpl[] res = new GameImpl[counts.length];
077 for(int i = 0; i < res.length; i++)
078 res[i] = new GameImpl(i);
079 // Find players with below average different opponents
080 int m = standing.length / 2;
081 int limit = m;
082 while ( limit > 0
083 && wps[limit].differentOpponents == wps[m].differentOpponents )
084 limit--;
085 // First seat those unlucky ones
086 for(int i = 0; i <= limit; i++)
087 bestFit(counts, res, wps[i]);
088 L.debug("pairing: limit="+limit);
089 // Rearange remaining games to small games first!
090 int start = 0;
091 while ( start < counts.length && res[start].size() > 0 ) start++;
092 Arrays.sort(counts, start, counts.length);
093 // Now seat by a "hardest" first strategy
094 for(int i = wps.length - 1; i > limit; i--)
095 bestFit(counts, res, wps[i]);
096 return res;
097 }
098
099 protected void bestFit(int[] counts, GameImpl[] res, WrappedPlayer py)
100 {
101 int iOpt = 0;
102 double distOpt = Double.MAX_VALUE;
103 for(int i = 0; i < counts.length; i++)
104 {
105 if ( res[i].size() < counts[i] )
106 {
107 double dist = dist(py, res[i]);
108 if ( dist < distOpt
109 || ( dist == distOpt && res[i].size() > res[iOpt].size() )
110 )
111 {
112 distOpt = dist;
113 iOpt = i;
114 }
115 }
116 }
117 L.debug(res[iOpt]+" + "+py+" d="+distOpt);
118 res[iOpt].add(py.p);
119 }
120
121 protected double dist(WrappedPlayer py, GameImpl game)
122 {
123 Player p = py.p;
124 Iterator<Player> players = game.players();
125 if ( ! players.hasNext() )
126 {
127 return 0.5;
128 }
129 int deltaRank = 0;
130 int common = 0;
131 int count = 1;
132 while ( players.hasNext() )
133 {
134 Player p2 = players.next();
135 int pa = p.getPlayedAgainst(p2);
136 common += (1 << (2 * pa));
137 int dr = Math.abs(py.rank - ref.get(p).rank);
138 if ( dr > deltaRank )
139 deltaRank += dr;
140 count++;
141 }
142 double fak = 1.0 + 2.0 * deltaRank / ref.size();
143 return fak * common / Math.sqrt(count);
144 }
145
146 public String toString()
147 {
148 return "MixingPairing";
149 }
150
151 private static class WrappedPlayer
152 implements Comparable
153 {
154 Player p;
155 int differentOpponents = 0;
156 int opponents = 0;
157 int rank;
158
159 public WrappedPlayer(Player p, int rank)
160 {
161 this.p = p;
162 this.rank = rank;
163 Player[] opps = p.getRegistry().getPlayers();
164 for(int i = 0; i < opps.length; i++)
165 {
166 int c = p.getPlayedAgainst(opps[i]);
167 if ( c > 0 )
168 {
169 differentOpponents++;
170 opponents += c;
171 }
172 }
173 }
174
175 public int compareTo(Object o)
176 {
177 if ( !(o instanceof WrappedPlayer) )
178 {
179 return -1;
180 }
181 int h;
182 WrappedPlayer p2 = (WrappedPlayer) o;
183 h = differentOpponents - p2.differentOpponents;
184 if ( h != 0 )
185 return h;
186 h = opponents - p2.opponents;
187 if ( h != 0 )
188 return h;
189 return rank - p2.rank;
190 }
191
192 public String toString()
193 {
194 return p+":"+rank+":"+differentOpponents+":"+opponents;
195 }
196 }
197 }