CodinGame Amadeus contest

Amadeus.cs

//#undef DEBUG

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

class Player
{
	const double planetOwnScore = 100;
	const double planetWinByNeighborsScore = 80;
	const double voronoiScore = 8;
	const double sameTargetScore = 60;
	const double dangerScore = 5;

	static Random random = new Random ();

	static void Main (string[] args)
	{
		string[] inputs;
		inputs = Console.ReadLine ().Split (' ');
		int planetCount = int.Parse (inputs [0]);
		int edgeCount = int.Parse (inputs [1]);
		string init = string.Join (" ", inputs) + "\n";
		List<Node> nodes = Enumerable.Range (0, planetCount).Select (p => new Node (p)).ToList ();
		for (int i = 0; i < edgeCount; i++) {
			inputs = Console.ReadLine ().Split (' ');
			int planetA = int.Parse (inputs [0]);
			int planetB = int.Parse (inputs [1]);
			nodes [planetA].Neighbors.Add (nodes [planetB]);
			nodes [planetB].Neighbors.Add (nodes [planetA]);
			init += string.Join (" ", inputs) + "\n";
		}

		// game loop
		int turn = 0;
		Node articulationPoint = null;
		Node finalPoint = null;
		int[,] dist = Distances (nodes);

		while (true) {
			turn++;
			for (int i = 0; i < planetCount; i++) {
				Node n = nodes [i];
				n.Reset ();
				inputs = Console.ReadLine ().Split (' ');
				n.MyUnits = int.Parse (inputs [0]);
				n.MyTolerance = int.Parse (inputs [1]);
				n.EnemyUnits = int.Parse (inputs [2]);
				n.EnemyTolerance = int.Parse (inputs [3]);
				n.CanAssign = int.Parse (inputs [4]) > 0;
			}
			Console.Error.Write (init);
			foreach (Node n in nodes)
				Console.Error.WriteLine (n);

			if (turn == 1) {
				articulationPoint = FindArticulationPoint (nodes, out finalPoint);
				Node myBase = nodes.Find (n => n.MyUnits > 0);
				Node enemyBase = nodes.Find (n => n.EnemyUnits > 0);
				foreach (Node n in nodes) {
					if (dist [n.ID, myBase.ID] <= dist [n.ID, enemyBase.ID] || articulationPoint == null)
						n.ShallConquer = true;
				}
			}
			if (AttackArticulationPoint (articulationPoint, dist, nodes))
				continue;
			if (finalPoint != null && articulationPoint.Mine)
				articulationPoint = finalPoint;
			if (articulationPoint != null)
				Console.Error.WriteLine ("articulation Point: " + articulationPoint.ID);

			HashSet<Node> conquer = new HashSet<Node> (nodes.Where (n => n.ShallConquer));
			ReverseNodes (nodes);
			List<Node> opponent = Move (turn, dist, nodes, 10, new List<Node>(), false);

			ReverseNodes (nodes);
			foreach (Node n in nodes)
				n.ShallConquer = conquer.Contains (n);
			List<Node> action = Move (turn, dist, nodes, 30, opponent, false);

			foreach(Node n in action)
				Console.WriteLine (n.ID);
			if (action.Count == 6)
				continue;

			List<Node> spread = nodes.Where (n => n.MyUnits > 5 && n.EnemyUnits == 0 && n.Neighbors.Count > 4 && n.EnemyDist > 2).ToList ();
			if (spread.Count == 0)
				Console.WriteLine ("NONE");
			else
				Console.WriteLine (spread.OrderByDescending (s => s.Neighbors.Count).First ().ID);

			#if DEBUG
			break;
			#endif
		}
	}

	static void ReverseNodes(List<Node> nodes) {
		foreach (Node n in nodes) {
			int tmp = n.MyUnits;
			n.MyUnits = n.EnemyUnits;
			n.EnemyUnits = tmp;
			tmp = n.MyTolerance;
			n.MyTolerance = n.EnemyTolerance;
			n.EnemyTolerance = tmp;
			n.ShallConquer = true;
		}

		foreach (Node n in nodes) {
			n.CanAssign = n.MyTolerance > 0 && (
				n.MyUnits > 0 || n.Neighbors.Any (n2 => n2.MyUnits > n2.EnemyUnits)
			);
		}

		foreach (Node n in nodes)
			n.Save ();
	}

	static List<Node> Move(int turn, int[,] dist, List<Node> nodes, int maxTime, List<Node> opponentMoves, bool canSplit) {
		List<Node> candidates = nodes.Where (n => n.ShallConquer && n.CanAssign && 
			(n.MyUnits <= n.EnemyUnits || n.Neighbors.Any(n2 => n2.MyUnits < n2.EnemyUnits))).ToList ();
		List<Node> enemy = nodes.Where (n => n.EnemyUnits > 0).ToList ();
		if (candidates.Count == 0)
			candidates = nodes.Where (n => n.ShallConquer && n.CanAssign).ToList ();
		if (candidates.Count == 0)
			candidates = nodes.ToList ();

		int enemyDist = 0;
		if (nodes.Any(n => n.Mine)) nodes.Where(n => n.Mine).Min (c => enemy.Min (e => dist [e.ID, c.ID]));
		if (enemyDist > 3) {
			Node node = candidates.OrderByDescending (n => n.Neighbors.Count (n2 => n2.MyUnits <= n2.EnemyUnits)).First ();
			return Enumerable.Range (0, 6).Select (n => node).ToList ();
		}
		enemyDist = candidates.Min (c => enemy.Min (e => dist [e.ID, c.ID]));
		foreach (Node n in opponentMoves)
			n.EnemyUnits++;

		//turn = nodes.Count - 4;
		if (turn + 5 < nodes.Count)
			candidates = candidates.Where (c => enemy.Min (e => dist [e.ID, c.ID]) <= enemyDist+1).ToList ();
		Console.Error.WriteLine ("cand = " + string.Join (" ", candidates.Select (c => c.ID)));

		Stopwatch sw = Stopwatch.StartNew ();
		List<Node> action = new List<Node> ();
		List<Node> scoreRelevance = candidates.SelectMany (c => c.Neighbors).Union (candidates).Distinct ().OrderBy(n => n.ID).ToList ();
		double bestScore = double.MinValue;
		int counter = 0;
		while (sw.ElapsedMilliseconds < maxTime) {
			counter++;
			List<Node> place = new List<Node> ();
			place.Add (candidates [random.Next (candidates.Count)]);
			while (place.Count < 5) {
				if (random.Next (2) == 0)
					place.Add (candidates [random.Next (candidates.Count)]);
				else
					place.Add (place [random.Next (place.Count)]);
			}
			double tmp = Eval (nodes, place, scoreRelevance, canSplit && random.Next(5) == 0);
			if (tmp > bestScore) {
				bestScore = tmp;
				action = place;
			}
		}
		return action;
	}

	static double Eval(List<Node> nodes, List<Node> place, List<Node> toScore, bool split) {
		foreach (Node n in place)
			n.MyUnits++;

		if (split) {
			List<Node> toSplit = new List<Node> ();
			foreach (Node n in nodes) {
				if (n.MyUnits >= 5)
					toSplit.Add (n);
			}
			if (toSplit.Count > 0) {
				Node s = toSplit [random.Next (toSplit.Count)];
				s.MyUnits -= 5;
				foreach (Node n in s.Neighbors)
					n.MyUnits++;
				place.Add (s);
			}
		}

		//foreach(Node n in nodes) n.UpdateOwner ();
		//foreach(Node n in nodes) n.KillIsolated ();

		double score = 0;
		foreach (Node n in toScore) {
			int diff = n.MyUnits - n.EnemyUnits;
			int laterScore = n.Score ();
			if (diff > 1 || diff == 1 && laterScore >= 0)
				score += planetOwnScore;
			if (diff < -1 || diff == -1 && laterScore <= 0)
				score -= planetOwnScore;

			if (n.MyUnits > 0 && Math.Sign (laterScore) > Math.Sign (diff))
				score += planetWinByNeighborsScore;
			if (n.EnemyUnits > 0 && Math.Sign (laterScore) < Math.Sign (diff))
				score -= planetWinByNeighborsScore;

			if (diff > 0 && laterScore > 0 && n.Endangered)
				score -= dangerScore;
		}

		Queue<Node> queue = new Queue<Node>();
		foreach(Node n in nodes) {
			n.Visited = false;
			if (n.MyUnits > n.EnemyUnits) {
				queue.Enqueue (n);
				n.Visited = true;
				n.MyDist = 0;
			}
		}
		while (queue.Count > 0) {
			Node q = queue.Dequeue ();
			foreach (Node n in q.Neighbors) {
				if (n.Visited)
					continue;
				n.MyDist = q.MyDist + 1;
				n.Visited = true;
				queue.Enqueue (n);
			}
		}

		foreach(Node n in nodes) {
			n.Visited = false;
			if (n.MyUnits < n.EnemyUnits) {
				queue.Enqueue (n);
				n.Visited = true;
				n.EnemyDist = 0;
			}
		}
		while (queue.Count > 0) {
			Node q = queue.Dequeue ();
			foreach (Node n in q.Neighbors) {
				if (n.Visited)
					continue;
				n.EnemyDist = q.EnemyDist + 1;
				n.Visited = true;
				queue.Enqueue (n);
			}
		}

		foreach (Node n in nodes) {
			if (n.MyDist < n.EnemyDist)
				score += voronoiScore;
			if (n.MyDist > n.EnemyDist)
				score -= voronoiScore;
		}

		score -= sameTargetScore * place.Distinct ().Count (); // don't place all on different planets

		foreach (Node n in place)
			n.Restore ();
		return score;
		// advantage of planets i own (if it affects sign(neighbor score)), disadvantage at opponent planets (cap at delta=5)
		// voronoi
		// tolerance
	}

	static bool AttackArticulationPoint (Node artPoint, int[,] dist, List<Node> nodes)
	{
		if (artPoint == null)
			return false;
		if (artPoint.MyTolerance == 0) {
			if (artPoint.MyUnits > artPoint.EnemyUnits)
				return false; 
			foreach (Node n in artPoint.Neighbors) {
				if (n.CanAssign || n.MyUnits > 5) {
					Node target = n;
					if (!n.CanAssign && nodes.Any(node => node.CanAssign)) {
						target = nodes.Where (node => node.CanAssign).OrderByDescending (node => dist[node.ID, artPoint.ID]).First ();
					}
					for (int i = 0; i < 5; i++) {
						Console.WriteLine (target.ID);
					}
					Console.WriteLine (n.ID);
					return true;
				}
			}
			foreach (Node n in artPoint.Neighbors.Where(n => n.Mine).SelectMany(a => a.Neighbors).Distinct()) {
				if (n.CanAssign) {
					for (int i = 0; i < 6; i++) {
						Console.WriteLine (n.ID);
					}
					return true;
				}
			}
			return false;
		}
		Node closest = nodes.Where (n => n.Mine).OrderBy (n => dist [n.ID, artPoint.ID]).First ();
		int myDist = dist [closest.ID, artPoint.ID];
		Node enemyClosest = nodes.Where (n => n.Enemy).OrderBy (n => dist [n.ID, artPoint.ID]).First ();
		int enemyDist = dist [enemyClosest.ID, artPoint.ID];
		Node next = closest.Neighbors.FirstOrDefault (n => dist [n.ID, artPoint.ID] < myDist);
		Console.Error.WriteLine ("dist: " + myDist);
		if (myDist == 0 && enemyDist > 1) return false;
		if (artPoint.MyUnits > artPoint.EnemyUnits + 5)
			return false;
		if (myDist > 2) {
			for (int i = 0; i < 6; i++) {
				Console.WriteLine (next.ID);
			}
		} else if (myDist == 2) {
			for (int i = 0; i < 5; i++) {
				Console.WriteLine (next.ID);
			}
			Console.WriteLine (closest.ID);
		} else if (myDist == 1) {
			for (int i = 0; i < 5; i++) {
				Console.WriteLine (next.ID);
			}
			Console.WriteLine (closest.MyUnits <= 5 ? "NONE" : closest.ID.ToString());
		} else {
			for (int i = 0; i < 4; i++) {
				Console.WriteLine (artPoint.ID);
			}
			if (artPoint.Mine &&
				artPoint.Neighbors.Count (n => n.Mine) <= artPoint.Neighbors.Count (n => n.Enemy) && 
				artPoint.Neighbors.Any (n => n.MyUnits == 0 && n.MyTolerance > 0 && n.EnemyUnits == 0)) {
				Node neighbor = artPoint.Neighbors.First (n => n.MyUnits == 0 && n.MyTolerance > 0 && n.EnemyUnits == 0);
				Console.WriteLine (neighbor.ID);
			}
			else Console.WriteLine (artPoint.ID);

			Node split = nodes.FirstOrDefault (n => dist [n.ID, artPoint.ID] == 2 && n.MyUnits >= 5 && !n.Neighbors.Any (n2 => n2.EnemyUnits > 0));
			Console.WriteLine (split == null ? "NONE" : split.ID.ToString());
		}
		return true;
	}

	static Node FindArticulationPoint (List<Node> nodes, out Node finalPoint)
	{
		finalPoint = null;
		bool majority = false;
		Node myBase = nodes.Find (n => n.MyUnits > 0);
		Node enemyBase = nodes.Find (n => n.EnemyUnits > 0);
		int[,] dist = Distances (nodes);
		Node result = null;
		int unreachable = 4;
		foreach (Node n in nodes) {
			if (dist [n.ID, myBase.ID] != dist [n.ID, enemyBase.ID])
				continue;
			foreach (Node n2 in n.Neighbors)
				n2.Neighbors.Remove (n);
			int[,] tmpDist = Distances (nodes);
			int tmpUnreachable = nodes.Count(node => tmpDist[node.ID, myBase.ID] > nodes.Count);
			if (!majority && tmpUnreachable > unreachable) {
				unreachable = tmpUnreachable;
				result = n;
			}
			if (tmpUnreachable > unreachable) {
				unreachable = tmpUnreachable;
				finalPoint = n;
			}
			if (2 * tmpUnreachable > nodes.Count) {
				if (!majority || tmpUnreachable < unreachable) {
					majority = true;
					unreachable = tmpUnreachable;
					finalPoint = n;
				}
			}
			foreach (Node n2 in n.Neighbors)
				n2.Neighbors.Add (n);
		}
		return result;
	}

	static int[,] Distances (List<Node> nodes)
	{
		int n = nodes.Count;
		int[,] dist = new int[n, n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dist [i, j] = (int)1e9;
			}
		}
		foreach (Node nod in nodes) {
			dist [nod.ID, nod.ID] = 0;
			foreach (Node nod2 in nod.Neighbors) {
				dist [nod.ID, nod2.ID] = 1;
			}
		}

		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (dist [i, j] > dist [i, k] + dist [k, j])
						dist [i, j] = dist [i, k] + dist [k, j];
				}
			}
		}
		return dist;
	}

	class Node
	{
		public int ID;
		public List<Node> Neighbors = new List<Node> ();
		public bool CanAssign;
		public int MyUnits;
		public int EnemyUnits;
		public bool Visited;
		public int MyDist;
		public int EnemyDist;
		public int MyTolerance;
		public int EnemyTolerance;
		public bool Mine => MyUnits > EnemyUnits;
		public bool Enemy => MyUnits < EnemyUnits;
		public bool ShallConquer;

		private int _myUnits;
		private int _enemyUnits;
		private int _myTolerance;
		private int _enemyTolerance;
		private int _dominationVal;

		public void Save() {
			_myUnits = MyUnits;
			_enemyUnits = EnemyUnits;
			_myTolerance = MyTolerance;
			_enemyTolerance = EnemyTolerance;
			_dominationVal = EnemyUnits + 1 - MyUnits;
			if (EnemyTolerance > 0 && (EnemyUnits > 0 || Neighbors.Any (n => n.Enemy)))
				_dominationVal += 5;
		}

		public bool Endangered => MyUnits < _dominationVal;

		public void Restore() {
			MyUnits = _myUnits;
			EnemyUnits = _enemyUnits;
			MyTolerance = _myTolerance;
			EnemyTolerance = _enemyTolerance;
		}

		public int Score() {
			int result = 0;
			foreach (Node n in Neighbors) {
				if (n.Mine)
					result++;
				if (n.Enemy)
					result--;
			}
			return result;
		}

		public Node (int id)
		{
			this.ID = id;
		}

		public void Reset ()
		{
			EnemyDist = -1;
		}

		private bool[] Owner;
		public void UpdateOwner ()
		{
			Owner = new bool[] { MyUnits > EnemyUnits, MyUnits < EnemyUnits };
		}

		public void KillIsolated ()
		{
			int neighborSum = 0;
			foreach (Node n in Neighbors) {
				if (n.Owner [0])
					neighborSum++;
				else if (n.Owner [1])
					neighborSum--;
			}
			if (EnemyUnits > 0 && neighborSum > 0)
				EnemyUnits--;
			if (MyUnits > 0 && neighborSum < 0)
				MyUnits--;
		}

		public override string ToString ()
		{
			return string.Join (" ", new [] {
				MyUnits,
				MyTolerance,
				EnemyUnits,
				EnemyTolerance,
				CanAssign ? 1 : 0
			}) + " (" + ID + ")";
		}
	}
}

Referee.cs

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace Amadeus
{
	class Referee
	{
		public static void Main (string[] args)
		{
			List<string> maps = new List<string> ();
			foreach (FileInfo fi in new DirectoryInfo("./replays/Amadeus/cleaned").GetFiles()) { // list of about 250 real maps that I downloaded
				maps.Add (File.ReadAllText (fi.FullName));
			}

			int seed = -1;
			while (true) {
				string[] lineParts = Console.ReadLine ().Split ();
				if (lineParts [0] == "###Seed")
					seed = int.Parse (lineParts [1]);
				else if (lineParts [0] == "###Start") {
					Board board = new Board (maps, seed);

					while (board.Play ()) {
						board.Tick ();
					}
					board.DeclareWinner ();
				}
			}

		}
	}

	class Board
	{
		private string init = "";
		public List<Node> nodes = new List<Node> ();

		public Board (List<string> maps, int seed)
		{
			Random random = new Random ();
			if (seed >= 0)
				random = new Random (seed);
			string map = maps [random.Next (maps.Count)];
			string[] lines = map.Split ('\n');
			int nodeCount = int.Parse (lines [0]);
			int links = int.Parse (lines [1]);
			init += nodeCount + " " + links + "\n";
			for (int i = 0; i < nodeCount; i++) {
				nodes.Add (new Node (i));
			}
			for (int i = 0; i < links; i++) {
				int[] nums = lines [2 + i].Split (' ').Select (int.Parse).ToArray ();
				nodes [nums [0]].Neighbors.Add (nodes [nums [1]]);
				nodes [nums [1]].Neighbors.Add (nodes [nums [0]]);
				init += nums [0] + " " + nums [1] + "\n";
			}
			int start1 = int.Parse (lines [2 + links]);
			int start2 = int.Parse (lines [3 + links]);
			nodes [start1].Units [0] += 5;
			nodes [start1].Tolerance [0] = 4;
			nodes [start2].Units [1] += 5;
			nodes [start2].Tolerance [1] = 4;
		}

		private int round = 0;

		public void Tick ()
		{
			// user input
			List<List<string>> actions = new List<List<string>> ();
			for (int player = 0; player < 2; player++) {
				string state = "";
				if (round == 0) {
					state = init;
				}
				foreach (Node n in nodes)
					state += n.Print (player) + "\n";

				Console.WriteLine ("###Input " + player);
				Console.Write (state);
				Console.WriteLine ("###Output " + player + " 6");

				actions.Add (new List<string> ());
				for (int a = 0; a < 6; a++) {
					actions [player].Add (Console.ReadLine ());
				}
			}

			// place units
			for (int player = 0; player < 2; player++) {
				HashSet<int> toleranceReduced = new HashSet<int> ();
				for (int i = 0; i < 5; i++) {
					int n = int.Parse (actions [player] [i]);
					nodes [n].Units [player]++;
					if (!toleranceReduced.Contains (n)) {
						toleranceReduced.Add (n);
						nodes [n].Tolerance [player]--;
					}
				}
				if (actions [player] [5] != "NONE") {
					int n = int.Parse (actions [player] [5]);
					nodes [n].Units [player] -= 5;
					foreach (Node neighbor in nodes[n].Neighbors)
						neighbor.Units [player]++;
				}
			}

			// isolation deaths
			nodes.ForEach (n => n.UpdateOwner ());
			nodes.ForEach (n => n.KillIsolated ());

			round++;
		}

		public bool Play ()
		{
			return round < nodes.Count;
		}

		public void DeclareWinner ()
		{
			int p1 = nodes.Count (n => n.Units [0] > n.Units [1]);
			int p2 = nodes.Count (n => n.Units [0] < n.Units [1]);
			if (p1 < p2)
				Console.WriteLine ("###End 0 1");
			if (p1 == p2)
				Console.WriteLine ("###End 01");
			if (p1 > p2)
				Console.WriteLine ("###End 1 0");
		}
	}

	class Node
	{
		public int ID;
		public int[] Units = new int[2];
		public int[] Tolerance = new int[]{ 5, 5 };
		public bool[] Owner;
		public List<Node> Neighbors = new List<Node> ();

		public Node (int id)
		{
			this.ID = id;
		}

		public void UpdateOwner ()
		{
			Owner = new bool[] { Units [0] > Units [1], Units [0] < Units [1] };
		}

		public void KillIsolated ()
		{
			int neighborSum = 0;
			foreach (Node n in Neighbors) {
				if (n.Owner [0])
					neighborSum++;
				else if (n.Owner [1])
					neighborSum--;
			}
			if (Units [1] > 0 && neighborSum > 0)
				Units [1]--;
			if (Units [0] > 0 && neighborSum < 0)
				Units [0]--;
		}

		public string Print (int player)
		{
			int opponent = 1 - player;
			int canAssign = 0;
			if (Tolerance [player] > 0 && (Units [player] > 0 || Neighbors.Any (n => n.Units [player] > n.Units [opponent])))
				canAssign = 1;
			return string.Join (" ", new [] {
				Units [player],
				Tolerance [player],
				Units [opponent],
				Tolerance [opponent],
				canAssign
			});
		}
	}
}