// Horrible Agent Loosing At Kalah			     -*- mode: java; -*-

package info.kwarc.teaching.AI.Kalah.WS2021.agents;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;

import java.lang.management.ManagementFactory;
import java.lang.management.MemoryUsage;

import info.kwarc.teaching.AI.Kalah.Agents.Agent;
import info.kwarc.teaching.AI.Kalah.Board;
import info.kwarc.teaching.AI.Kalah.Game;
import info.kwarc.teaching.AI.Kalah.util.Converter;

public class Halak extends Agent {
    private static final byte	 ILLEGAL	= -1;
    private static final float   MEM_LIMIT	= 0.666f;
    private static final int	 HIST_DEPTH	= 1 << 6;

    // To decrease the lookup time during search, previous evaluations of states
    // are stored  in this "history" data  structure.  There are two  cases that
    // have to  be considered: 1.  if  I am at depth  N and there is  a previous
    // evaluations M, where M < N, I  could find a better result. So this result
    // isn't returned,  but instead used to  guide the search to  avoid anything
    // that is below whatever  was just found. 2. if I am ad  depth N, and there
    // is a previous evaluation M, where M >  N, then I can just return this, as
    // will at best find the same (or a worse) evaluation.  For this reason, the
    // data  structure has  to be  a two-dimensional  matrix of  sets, with  one
    // dimension  representing the  current search  depth N,  and the  other the
    // lookahead M. Each element of this  matrix is a function mapping states to
    // evaluations.
    //
    // In this program, this is implemented using a LinkedList for the depth, an
    // ArrayList for  the (bounded)  look-ahead, and a  HashMap for  each entry.
    // The depth is represented  using a linked list, to make  it easier to drop
    // the last results, that are not necessary  after a move has been made. The
    // lookahead doesn't have to grow, so a fixed-size array is enough.
    //
    //   -- phi, 08Jan21
    private List<List<Map<B, Float>>> history = new LinkedList<>();

    // local parameters
    final private int start = 2, step = 1;

    // shared local state
    private Side player;
    private Board board;
    private Random rand = new Random();
    private int size = -1, seeds = -1;
    private int maxdepth = 0;
    private volatile long last = -1;
    private volatile float load = 0;

    public String name() {
	return String.format("HALAK-%d", HIST_DEPTH);
    }

    public Iterable<String> students() {
	return Arrays.asList("Kaludercic, Philip <oj14ozun>",
			     "Tiras, Evren <at58izag>");
    }

    private enum Side {
	NORTH, SOUTH;

	Side other() { return this == Side.NORTH ? Side.SOUTH : Side.NORTH; }
    }

    private enum Mode {
	MIN, MAX;

	Mode other() { return this == Mode.MAX ? Mode.MIN : Mode.MAX; }
	Side side(Side side) { return this == Mode.MAX ? side : side.other(); }
    };

    private void cleanup(float rate) {
	int retry = 0;
	float usage = 0;

	do {
	    synchronized (history) {
		int size = history.size();
		for (int i = size - retry * step - 1;
		     i >= size - (retry-1) * step;
		     i--) {
		    for (int j = 0; j < size; j++)
			history.get(i).get(j).clear();
		    System.gc();
		}

		MemoryUsage mu = ManagementFactory
		    .getMemoryMXBean()
		    .getHeapMemoryUsage();
		usage = ((float) mu.getUsed()) / mu.getMax();

		retry++;
	    }
	} while (usage < rate);
    }

    private Float lookup(int depth, int lookahead, B b) {
	synchronized (history) {
	    List<Map<B, Float>> line = history.get(depth);
	    if (line != null
		&& (0 <= lookahead)
		&& (lookahead < line.size())) {
		Map<B, Float> map = line.get(lookahead);
		if (map != null) {
		    return map.get(b);
		}
	    }
	}

	return null;
    }

    private void remember(int depth, B b, float eval) {
	if (rand.nextFloat() < load)
	    return;

	synchronized (history) {
	    List<Map<B, Float>> line = history.get(depth);
	    int lookahead = maxdepth - depth;
	    if (line != null
		&& (0 <= lookahead)
		&& (lookahead < line.size())) {
		Map<B, Float> map = line.get(lookahead);
		if (map != null) {
		    map.put(b, eval);
		}
	    }
	}
    }

    class B {
	byte north, south;
	byte north_pits[];
	byte south_pits[];

	B(Board b) {
	    this.north = Converter.getMyStoreSeeds(b, true).byteValue();
	    this.south = Converter.getEnemyStoreSeeds(b, true).byteValue();

	    List<Integer> houses = Converter.getMyHouses(b, true);
	    north_pits = new byte[houses.size()];
	    for (int i = 0; i < size; ++i) {
		north_pits[i] = houses.get(i).byteValue();
	    }

	    houses = Converter.getEnemyHouses(b, true);
	    south_pits = new byte[houses.size()];
	    for (int i = 0; i < size; ++i) {
		south_pits[i] = houses.get(i).byteValue();
	    }
	}

	private B(byte north, byte south,
		  byte north_pits[], byte south_pits[]) {
	    this.north		= north;
	    this.south		= south;
	    this.north_pits	= north_pits;
	    this.south_pits	= south_pits;
	}

	private byte[] pits(Side side) {
	    return side == Side.NORTH ? this.north_pits : this.south_pits;
	}

	private boolean sow(byte pos, Side side) {
	    Side current = side;
	    byte[] pits = pits(current);

	    // NB.  Bytes  are signed  data types  in Java,  which might  not be
	    //      enough for  all situations.   Therefore all byte  values are
	    //      upgraded to  integers containing  the unsigned value  of the
	    //      byte representation.
	    int seeds = 0xFF & pits[pos];

	    // sowing the seeds
	    for (int i = 0; i < seeds; ++i) {
		if (++pos == size) {
		    if (current == side) {
			if (current == Side.NORTH) {
			    this.north++;
			} else {
			    this.south++;
			}
		    }
		    current = current.other();
		    pits = pits(current);
		    pos = 0;
		} else {
		    pits[pos]++;
		}
	    }

	    // stealing opponents stones
	    int last = pos - 1;
	    if (side == current && last >= 0 && pits(side)[last] == 1) {
		int from = size - pos - 1;
		int steal = 0xFF & pits(side.other())[from];
		if (steal > 0) {
		    if (side == Side.NORTH) {
			this.north += steal + 1;
		    } else {
			this.south += steal + 1;
		    }
		    pits(side.other())[from] = 0;
		    pits(side)[last] = 0;
		}
	    }

	    // collecting stones when game is over
	    boolean over = true;
	    pits = pits(side);
	    for (int i = 0; i < pits.length; ++i) {
		if ((0xFF & pits[i]) > 0) {
		    over = false;
		    break;
		}
	    }
	    if (over) {
		pits = pits(side.other());
		seeds = 0;
		for (int i = 0; i < pits.length; ++i) {
		    seeds += 0xFF & pits[i];
		    pits[i] = 0;
		}
		if (side == Side.NORTH) {
		    this.south += seeds;
		} else {
		    this.north += seeds;
		}
		return false;
	    }

	    // repeating a move
	    return pos == 0;
	}

	private boolean legal(byte pos, Side side) {
	    return (0xFF & pits(side)[pos]) > 0;
	}

	private boolean preferable(byte move1, byte move2, Side side) {
	    if (move1 == ILLEGAL) return false;
	    if (move2 == ILLEGAL) return true;

	    byte pits[] = pits(side);

	    boolean repeat1 = (((0xFF & pits[move1]) % (2 * (1 + size)))
			       == size);
	    boolean repeat2 = (((0xFF & pits[move2]) % (2 * (1 + size)))
			       == size);
	    boolean collect1 = (((move1 + (0xFF & pits[move1])) < size) &&
				(pits[(move1 + (0xFF & pits[move1]))] == 0));
	    boolean collect2 = (((move2 + (0xFF & pits[move2])) < size) &&
				(pits[(move2 + (0xFF & pits[move2]))] == 0));

	    if (repeat1 && !repeat2)	return true;
	    if (repeat2)		return false;
	    if (collect1 && !collect2)	return true;
	    if (collect1 && collect2) {
		int from1 = (0xFF & pits(side.other())[size - move1 - 1]);
		int from2 = (0xFF & pits(side.other())[size - move2 - 1]);
		return from1 > from2;
	    }

	    return move1 < move2;
	}

	private byte[] moves(Side side) {
	    byte[] moves = new byte[size];
	    for (byte i = 0; i < size; ++i)
		moves[i] = legal(i, side) ? i : ILLEGAL;

	    for (int i = 0, j; i < size; ++i) {
		byte m = moves[i];
		for (j = i - 1;
		     j >= 0 && preferable(m, moves[j], side);
		     j--) {
		    moves[j+1] = moves[j];
		}
		moves[j+1] = m;
	    }

	    return moves;
	}

	private boolean over() {
	    int north_stones = 0, south_stones = 0;
	    for (int i = 0; i < size; ++i) {
		north_stones += 0xFF & north_pits[i];
		south_stones += 0xFF & south_pits[i];
	    }
	    return
		north_stones == 0 ||
		south_stones == 0 ||
		north_stones > size * seeds ||
		south_stones > size * seeds;
	}

	private float eval() {
	    return player == Side.NORTH ?
		(0xFF & this.north) - (0xFF & this.south) :
		(0xFF & this.south) - (0xFF & this.north);
	}

	private float search(int depth, float alpha, float beta, Mode mode) {
	    if (depth >= maxdepth || over()) {
		return eval();
	    }

	    if (depth < HIST_DEPTH) {
		for (int lookahead = HIST_DEPTH-1; lookahead >= 0; lookahead--) {
		    Float prev = lookup(depth, lookahead, this);
		    if (prev != null) {
			if (lookahead > maxdepth - depth) {
			    return prev;
			} else {
			    if (mode == Mode.MAX) {
				alpha = alpha > prev ? alpha : prev;
			    } else {
				beta  = beta < prev  ? beta  : prev;
			    }
			    break;
			}
		    }
		}
	    }

	    float eval = mode == Mode.MAX ? -Float.MAX_VALUE : Float.MAX_VALUE;
	    byte moves[] = moves(mode.side(player));
	    for (byte i = 0; i < size; ++i) {
		byte move = moves[i];
		if (move == ILLEGAL) continue;

		B next = (B) clone();
		boolean repeat = next.sow(move, mode.side(player));
		float util = next.search(depth + 1, alpha, beta,
					 repeat ? mode : mode.other());

		if (mode == Mode.MAX) {
		    eval  = util > eval  ? util : eval;
		    alpha = eval > alpha ? eval : alpha;
		} else {
		    eval  = util < eval  ? util : eval;
		    beta  = eval < beta  ? eval : beta;
		}


		if (alpha >= beta) break;
	    }

	    if (depth < HIST_DEPTH)
		remember(depth, this, eval);
	    return eval;
	}

	int search() {
	    float eval = -Float.MAX_VALUE, alpha = -Float.MAX_VALUE;

	    byte choice = ILLEGAL;
	    byte moves[] = moves(player);
	    for (int i = 0; i < size; ++i) {
		if (moves[i] != ILLEGAL) {
		    choice = moves[i];
		    break;
		}
	    }
	    for (int i = 0; i < size; ++i) {
		byte move = moves[i];
		if (move == ILLEGAL) continue;

		B next = (B) clone();
		boolean repeat = next.sow(move, player);
		float util = next.search(1, alpha, Float.MAX_VALUE,
					 repeat ? Mode.MAX : Mode.MIN);

		eval = util > eval ? util : eval;
		if (eval > alpha) {
		    choice = move;
		    alpha = eval;
		}
	    }

	    return (int) choice + 1;
	}

	public int hashCode() {
	    int hash = (0xFF & this.north) * (0xFF & this.south)
		+ (0xFF & this.north);

	    for (int i = 0; i < size; i++) {
		hash += 0xFF & this.north_pits[i];
		hash += hash << 10;
		hash ^= hash >> 6;
		hash += 0xFF & this.south_pits[i];
		hash += hash << 10;
		hash ^= hash >> 6;
	    }

	    hash += hash << 3;
	    hash ^= hash >> 11;
	    hash += hash << 15;

	    return hash;
	}

	public boolean equals(Object o) {
	    B other;
	    try { other = (B) o; }
	    catch (ClassCastException cce) { return false; }

	    if (other.north != this.north) return false;
	    if (other.south != this.south) return false;

	    for (int i = 0; i < size; i++) {
		if (other.north_pits[i] != this.north_pits[i])
		    return false;
		if (other.south_pits[i] != this.south_pits[i])
		    return false;
	    }

	    return true;
	}

	public Object clone() {
	    return new B(this.north, this.south,
			 this.north_pits.clone(),
			 this.south_pits.clone());
	}
    }

    private class MemoryGnome implements Runnable {
	public void run() {
	    for (;;) {
		MemoryUsage mu = ManagementFactory
		    .getMemoryMXBean()
		    .getHeapMemoryUsage();
		load = ((float) mu.getUsed()) / mu.getMax();

		if (load > MEM_LIMIT) {
		    cleanup(MEM_LIMIT);
		}

		try { Thread.sleep(100); }
		catch (InterruptedException ie) { }
	    }
	}
    }

    public void init(Board board, boolean playerOne) {
	this.board	= board;
	this.player	= playerOne ? Side.NORTH : Side.SOUTH;
	this.size	= board.houses();
	this.seeds	= board.initSeeds();

	new Thread(new MemoryGnome()).start();
    }

    private static int counter = 0;
    private int id = counter++;

    public int move() {
	long current = last = Thread.currentThread().getId();
	boolean doCleanup = false;
	B b = new B(board);
	int choice = -1, lastdepth = 0;;

	try {
	    synchronized (history) {
		// remove the last cached min/max values
		if (history.size() > 1) history.remove(0);
		if (history.size() > 1) history.remove(0);

		// ensure that the transposition table is well formed
		while (history.size() <= HIST_DEPTH) {
		    List<Map<B, Float>> list = new ArrayList<>(HIST_DEPTH + 1);
		    for (int i = 0; i < HIST_DEPTH; i++)
			list.add(i, new HashMap<B, Float>());
		    history.add(list);
		}
	    }

	    for (maxdepth = start; ; lastdepth = maxdepth += step) {
		try {
		    choice = b.search();
		    if (current != last) return choice;
		    Converter.setTimeoutMove(this, choice);
		} catch (OutOfMemoryError oome) {
		    doCleanup = true;
		} catch (StackOverflowError soe) {
		    break;
		} finally {
		    if (doCleanup) {
			cleanup(MEM_LIMIT/2);
			return choice;
		    }
		}
	    }
	} catch (Exception e) {
	    e.printStackTrace();
	}
	// Uncomment for logging purposes:
	//
	// finally {
	//     System.err.printf("\n%s\n(%d) Choice: %d, Depth: %d, MU: %.2f%%\n",
	//		      board, id, choice, lastdepth, load * 100);
	// }
	return choice;
    }
}

// Local Variables:
// fill-column: 80
// tab-width: 8
// End: