summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2021-02-08 16:45:13 +0100
committerJérémy Zurcher <jeremy@asynk.ch>2021-02-08 16:45:13 +0100
commitc0ee179933876a9bc4c2ad984fa3b84633668620 (patch)
tree15fb5ad266ff5caca609802aaec511c973f164e7
parenta2169a1761148e8dd219f46d1b17ae356d45e18f (diff)
downloadcolonial-twilight-master.zip
colonial-twilight-master.tar.gz
-rw-r--r--lib/colonial_twilight/fln_bot.rb101
-rwxr-xr-xlib/colonial_twilight/march_solver.rb294
-rwxr-xr-xtest6
3 files changed, 302 insertions, 99 deletions
diff --git a/lib/colonial_twilight/fln_bot.rb b/lib/colonial_twilight/fln_bot.rb
index 1b8b6a3..9c2c9b1 100644
--- a/lib/colonial_twilight/fln_bot.rb
+++ b/lib/colonial_twilight/fln_bot.rb
@@ -10,7 +10,8 @@ module ColonialTwilight
def play possible_actions
@possible_actions = possible_actions
_init
- _start
+ # _start
+ march
end
private
@@ -285,12 +286,6 @@ module ColonialTwilight
rcs_max = (@board.fln_resources <= 8 ? @board.fln_resources : @board.fln_resources * 2 / 3)
stop_cond = -> { @expended_resources == rcs_max or not may_continue? }
- spaces = @board.search {|s| not s.fln_bases_0? and s.fln_underground == 0 }
- puts "spaces :: " + spaces.collect(){|s| s.is_a?(Symbol) ? s.to_s : s.name}.join(' :: ')
- spaces.each do |space|
- d = _paths(space, {:fln_underground=>1}) {|h| h[:fln_underground] > 0 }
- end
-
puts "FIXME : march is not implemented yet"
exit 1
@@ -338,15 +333,6 @@ module ColonialTwilight
return conducted_action
end
- def _paths dst, want
- ws = dst.adjacents.map {|s| @board.spaces[s].wilaya }.uniq! # adjacent Wilayas allowed
- spaces = @board.search{|s| s != dst and ws.include? s.wilaya } # corresponding spaces
- puts "DST : #{dst}\nWilayas : #{ws.inspect}\n" + spaces.collect{|s| s.name }.join(' :: ') if @debug
- paths, tree = build_paths dst, ws, spaces, want
- tree.sort{|(x,a),(y,b)| a[:d]<=>b[:d]}.each{|k,v| puts "\t#{v[:d]} #{v[:fln][:max]}:#{v[:fln][:ok]} #{k.name} :: #{v[:adjs].map{|s| s.name}.join(' - ')}" }
- paths.each{|p| puts p.collect{|s| s.name}.join ' -> '}
- end
-
##### RALLY OPERATION #####
def rally
# max 6 spaces unless ope_only => 1
@@ -634,89 +620,6 @@ module ColonialTwilight
( (to.support? or from.country?) and (flns + to.gov_cubes + (from.country? ? @board.border_zone_track : 0)) > 3 )
end
- def build_paths dst, ws, spaces, want
- tree = ([dst] + spaces).inject({}) do |h,s|
- # filter out adjacents : dst OR adjacent to dst OR same wilaya
- a = s.adjacents.map{|n| @board.spaces[n]}.select{|a| a == dst or (spaces.include?(a) and (s.wilaya == a.wilaya or s == dst))}
- h[s] = { :adjs=> a, :fln => can_march_from(s, want), :d => 0}
- h
- end
- q = [dst]
- while not q.empty?
- s = q.shift
- h = tree[s]
- d = h[:d] + 1
- h[:adjs].each do |a|
- next if a == dst
- p = tree[a][:d]
- if p == 0 or d < p
- tree[a][:d] = d
- q << a
- end
- end
- end
- # filter_out dst, ws, tree
- build_shortest_paths tree
- end
-
- def filter_out dst, ws, tree
- ws.each do |w|
- h = tree.select{|s,h| s != dst and s.wilaya == w}
- next if h.inject(false) {|b,(s,h)| b||h[:fln][:ok]}
- h.each {|s,v|
- tree.delete s
- tree[dst][:adjs].delete s
- }
- end
- end
-
- def build_shortest_paths tree
- paths = []
- def dfs s, tree, paths, path
- l = tree[s][:adjs].sort{|a,b| tree[a][:d] <=> tree[b][:d]}
- d = tree[l[0]][:d]
- if d == 0
- paths << (path << l[0])
- else
- l.each do |a|
- break if tree[a][:d] > d
- dfs a, tree, paths, path.clone << a
- end
- end
- end
- tree.select{|k,v| v[:fln][:ok]}.each{|k,v| dfs k, tree, paths, [k] }
- [paths, tree]
- end
-
- def can_march_from s, want, with={}
- u = s.fln_underground + (with[:fln_underground]||0)
- a = s.fln_active + (with[:fln_active]||0)
- d = 0
- if not s.fln_bases_0?
- # at bases, leave last underground FLN, leave 2 FLN
- if u > 0
- u -= 1
- d = 1
- else
- a = (a > 2 ? a - 2 : 0)
- end
- end
- if (s.fln_bases_0? and s.support?) or d == 1
- # march with underground FLN, that could be swaped with an active FLN
- d = ((a > 0 and u > 0) ? 1 : 0)
- if a > 0
- a -= 1
- elsif u > 0
- u -= 1
- end
- end
- # never trigger GOV Control on populated spaces
- max = [(not s.country? and not s.pop0? and not s.gov_control?) ? (s.fln - s.gov) : 666, u + a].min
- # does it satisfy want conditions
- ok = (u >= (want[:fln_underground]||0) and a >= (want[:fln_active]||0) and max >= (want[:fln]||1))
- { :fln_underground=>u, :fln_active=>a, :delta=>d, :max=>max, :ok=>ok }
- end
-
def last_campaign?
false # FIXME
end
diff --git a/lib/colonial_twilight/march_solver.rb b/lib/colonial_twilight/march_solver.rb
new file mode 100755
index 0000000..98f0b0f
--- /dev/null
+++ b/lib/colonial_twilight/march_solver.rb
@@ -0,0 +1,294 @@
+#! /usr/bin/env ruby
+# -*- coding: UTF-8 -*-
+
+module ColonialTwilight
+
+ class MarchSolver
+
+ def initialize board
+ @board = board
+ end
+
+ def solve dst_cond, src_cond, options={}
+ debug = options[:debug] || false
+ puts "SOLVE" if debug
+ dsts = @board.search &dst_cond
+ return nil if dsts.empty?
+ trees = {}
+ dsts.each do |dst|
+ # puts "\n*** DST : #{dst.name}" if debug
+ spaces = _collect_spaces dst # collect spaces that can reach the destination
+ nodes = _build_nodes dst, spaces, src_cond # compute adjacents, distance, availabilities
+ show_nodes nodes if debug
+ srcs = nodes.select{|k,v| v[:march][:can_source]} # select possible sources
+ # puts " SRCS" if debug
+ # srcs.each{|k,v| puts "\t#{k.name} : #{v[:d]} #{v[:march]}" } if debug
+ next if srcs.empty?
+ paths, links, nodes = _build_shortest_paths srcs, nodes
+ trees[dst] = {
+ :paths => paths,
+ :links => links,
+ :nodes => nodes,
+ }
+ end
+ show_trees trees if debug
+ moves = _select_moves trees
+ show_moves moves if debug
+ moves
+ end
+
+ private
+
+ def show_nodes nodes
+ puts " NODES :"
+ def s m
+ "#{m[:can_source] ? '*' : ' '} #{m[:max_out]} #{m[:fln_underground]}/#{m[:fln_active]} : #{m[:retain]}"
+ end
+ # nodes.each{|k,v| puts "\t#{k.name} : #{v[:d]}\t#{s v[:march]}" }
+ nodes.each{|k,v| printf "%20s : %d %s\n" % [k.name, v[:d], s(v[:march])] }
+ end
+
+ def show_trees trees
+ puts " TREES :"
+ trees.each do|k, v|
+ nodes = v[:nodes]
+ puts " DST : #{k.name} links:#{v[:links].length} nodes:#{nodes.length}"
+ # v[:paths].each do |path| puts "\t* " + path.collect{|s| "#{s.name}(#{nodes[s][:d]})"}.join(' => ') end
+ v[:paths].each do |path|
+ s = "\t* "
+ path.each_cons(2) do |f,t| s += "#{f.name}(#{nodes[f][:d]}) =(#{v[:links][f.name+'#'+t.name]})=> " end
+ s += path[-1].name
+ puts s
+ end
+ end
+ end
+
+ def show_moves moves
+ puts "\nMOVES :"
+ moves.each do |v|
+ puts "\t* #{v[:complete]} #{v[:weight]} #{v[:from]} => #{v[:to]}"
+ end
+ end
+
+ def _collect_spaces dst
+ ws = dst.adjacents.map {|s| @board.spaces[s].wilaya }.uniq! # adjacent Wilayas allowed
+ spaces = @board.search{|s| s != dst and ws.include? s.wilaya } # corresponding spaces
+ # puts "\nDST : #{dst}\nWilayas : #{ws.inspect}\nSpaces : " + spaces.collect{|s| s.name }.join(' :: ') if @debug
+ spaces
+ end
+
+ def _build_nodes dst, spaces, src_cond
+ nodes = ([dst] + spaces).inject({}) do |h,s|
+ # filter out adjacents : dst OR adjacent to dst OR same Wilaya
+ a = s.adjacents.map{|n| @board.spaces[n]}.select{|a| a == dst or (spaces.include?(a) and (s.wilaya == a.wilaya or s == dst))}
+ h[s] = { :adjs=> a, :march => _march_data(s, src_cond), :d => 0}
+ h
+ end
+ # bfs to compute distances
+ q = [dst]
+ while not q.empty?
+ s = q.shift
+ h = nodes[s]
+ d = h[:d] + 1
+ h[:adjs].each do |a|
+ next if a == dst
+ p = nodes[a][:d]
+ if p == 0 or d < p
+ nodes[a][:d] = d
+ q << a
+ end
+ end
+ end
+ nodes
+ end
+
+ def _march_data s, want, with={}
+ u = s.fln_underground + (with[:fln_underground]||0)
+ a = s.fln_active + (with[:fln_active]||0)
+ retain = 0
+ max_out = u + a
+ if not s.fln_bases_0? # at base ...
+ retain = [2 - max_out, 0].max # retain until 2
+ max_out = [max_out - 2, 0].max # leave 2 FLN
+ if u > 0
+ u -= 1 # must leave last FLN
+ else
+ a = [a - 2, 0].max # or 2 active FLN
+ end
+ elsif s.support? # at support ...
+ retain = 1 if max_out == 0 # retain until 1
+ max_out = [max_out - 1, 0].max # leave 1 FLN
+ end
+ # never trigger GOV Control on populated spaces
+ max_out = [s.fln - s.gov, max_out].min if (not s.country? and not s.pop0? and not s.gov_control?)
+ u = max_out if u > max_out
+ a = max_out if a > max_out
+ # does it satisfy want conditions
+ can_source = (u >= (want[:fln_underground]||0) and a >= (want[:fln_active]||0) and max_out >= (want[:march]||1))
+ { :can_source =>can_source, :max_out=>max_out, :fln_underground=>u, :fln_active=>a, :retain=>retain}
+ end
+
+ def _build_shortest_paths srcs, nodes
+ # dfs to compute shortest path
+ def _shortest_paths n, nodes, path, &block
+ return yield path if nodes[n][:d] == 0
+ l = nodes[n][:adjs].sort{|a,b| nodes[a][:d] <=> nodes[b][:d]}
+ d = nodes[l[0]][:d]
+ l.each do |a|
+ break if nodes[a][:d] > d
+ _shortest_paths a, nodes, path.clone << a, &block
+ end
+ end
+ marked = {} # mark nodes in paths, to be able to filter out other nodes
+ links = {} # weight links usage
+ paths = []
+ done = {}
+ srcs.each do |src, v|
+ done[src.name] ||= []
+ _shortest_paths(src, nodes, [src]) do |p|
+ # dst (node[:d]==0) reached
+ p.inject(nil) { |i,v|
+ marked[v] = true
+ if not i.nil?
+ k = "#{i.name}##{v.name}"
+ if not done[src.name].include? k
+ done[src.name] << k
+ links[k] = (links[k] ||= 0) + 1 # count links per different sources
+ end
+ end
+ v
+ }
+ paths << p
+ end
+ end
+ [paths.sort!{|a,b| a.length<=>b.length}, links, nodes.select{|k,v| marked.keys.include? k} ]
+ end
+
+ def _select_moves trees
+ # max # moves ?
+ # partial success ?
+ shortests = trees.inject([]){|a,(k,v)| a.concat v[:paths]}.sort{|a, b| a.length <=> b.length}
+ l = shortests[0].length
+ moves = shortests.select{|p| p.length == l}.map{|p|
+ l = "#{p[0].name}##{p[1].name}"
+ n = trees[p[-1]][:nodes]
+ from = n[p[0]][:march]
+ to = n[p[1]][:march]
+ b = (p[0].country? or p[1].country?) ? border_zone_track : 0
+ # puts from.inspect
+ # puts to.inspect
+ {
+ :from => p[0],
+ :to => p[1],
+ :complete => p.length == 2,
+ :weight => trees.inject(-1){|n,(k,v)| n += (v[:links].has_key?(l) ? 1 : 0) },
+ :block => to[:block]
+ }
+ }.sort{|a,b|
+ if a[:complete] == b[:complete]
+ b[:weight] <=> a[:weight]
+ else
+ a[:complete] ? -1 : 1
+ end
+ }
+ # FIXME if is complete or block > 1 move only one
+ # chose the one that is at least used in other trees
+ puts "FIXME"
+ moves.each do |v|
+ puts "\t**** #{v[:complete]} #{v[:weight]}/#{v[:block]} #{v[:from]} => #{v[:to]}"
+ end
+ to = moves[0][:to]
+ puts "\n$$$$ activate: #{to.name} $$$$"
+ # FIXME : how many ?
+ # : will activiate
+ # : move underground or active
+ moves.select{|m| m[:to] == to and m[:weight] > 0}
+ end
+
+ end
+
+end
+
+if $PROGRAM_NAME == __FILE__
+
+ require 'colonial_twilight/board'
+
+ @board = ColonialTwilight::Board.new
+ # @board.load :short
+
+ # @board.spaces_h['Tlemcen'].add :fln_underground, -1
+ # @board.spaces_h['Tlemcen'].add :fln_base, 1
+ # @board.spaces_h['Mascara'].add :fln_underground, 2
+ # @board.spaces_h['Mascara'].add :fln_active, 2
+ # @board.spaces_h['Saida'].add :fln_base
+ # @board.spaces_h['Saida'].add :fln_underground, 1
+ # @board.spaces_h['Saida'].add :fln_active, 2
+ # @board.spaces_h['Sidi Bel Abbes'].add :algerian_police, 1
+ # @board.spaces_h['Biskra'].add :fln_base, 1
+ # @board.spaces_h['Negrine'].add :fln_active, 1
+
+ # @debug = true
+ # @board.spaces_h['Bordj Bou Arreridj'].add :fln_base, 1
+ # @board.spaces_h['Batna'].add :fln_base, 1
+ # @board.spaces_h['Philippeville'].add :fln_underground, 1
+
+ # @board.spaces_h['Mecheria'].add :fln_underground, 2
+ # @board.spaces_h['Mascara'].add :fln_base, 1
+ # @board.spaces_h['Sidi Bel Abbes'].add :fln_base, 1
+ # @board.spaces_h['Tlemcen'].add :fln_underground, -1
+
+ # @board.spaces_h['Sidi Aissa'].add :fln_base, 1
+ # @board.spaces_h['Barika'].add :fln_base, 1
+ # @board.spaces_h['Oum El Bouaghi'].add :fln_base, 1
+ # @board.spaces_h['Barika'].add :fln_underground, -1
+ # @board.spaces_h['Tebessa'].add :fln_active, 1
+ # @board.spaces_h['Batna'].add :fln_underground, 1
+ # @board.spaces_h['Negrine'].add :fln_underground, 1
+ # @board.spaces_h['Setif'].add :fln_underground, -1
+
+ # march = ColonialTwilight::MarchSolver.new @board
+ # moves = march.solve Proc.new {|s| not s.fln_bases_0? and s.fln_underground == 0 }, {:fln_underground=>1}, true
+ # moves.each do |m|
+ # @board.spaces_h[m[:from].name].add :fln_underground, -1
+ # @board.spaces_h[m[:to].name].add :fln_underground, 1
+ # end
+ # moves = march.solve Proc.new {|s| not s.fln_bases_0? and s.fln_underground == 0 }, {:fln_underground=>1}, true
+ # moves.each do |m|
+ # @board.spaces_h[m[:from].name].add :fln_underground, -1
+ # @board.spaces_h[m[:to].name].add :fln_underground, 1
+ # end
+ # moves = march.solve Proc.new {|s| not s.fln_bases_0? and s.fln_underground == 0 }, {:fln_underground=>1}, true
+ # moves.each do |m|
+ # @board.spaces_h[m[:from].name].add :fln_underground, -1
+ # @board.spaces_h[m[:to].name].add :fln_underground, 1
+ # end
+
+ # @board.spaces_h['Orleansville'].add :fln_underground, -1
+ # @board.spaces_h['Mostaganem'].add :fln_base, 1
+ # @board.spaces_h['Sidi Aissa'].add :fln_underground, 1
+ # @board.spaces_h['Laghouat'].add :fln_underground, 1
+
+ @board.spaces_h['Ain Sefra'].add :fln_underground, 1
+ @board.spaces_h['Saida'].add :fln_underground, 1
+ @board.spaces_h['Tlemcen'].add :fln_underground, 1
+ # @board.spaces_h['Tlemcen'].add :fln_active, 3
+ # @board.spaces_h['Tlemcen'].add :fln_base, 1
+
+ @board.spaces_h['Mostaganem'].add :french_police, 1 # trirres GOV control if leaveing
+ @board.spaces_h['Orleansville'].add :fln_base, 2
+ @board.spaces_h['Orleansville'].add :french_police, 1
+
+ options = {
+ :debug => true,
+ :max_moves => 2,
+ :must_solve => true,
+ # what does dst need ?
+ }
+
+ march = ColonialTwilight::MarchSolver.new @board
+ moves = march.solve Proc.new {|s| not s.fln_bases_0? and s.fln_underground == 0 }, {:fln_underground=>1}, options
+ moves.each do |m|
+ @board.spaces_h[m[:from].name].add :fln_underground, -1
+ @board.spaces_h[m[:to].name].add :fln_underground, 1
+ end
+end
diff --git a/test b/test
new file mode 100755
index 0000000..be07cad
--- /dev/null
+++ b/test
@@ -0,0 +1,6 @@
+#! /bin/bash
+
+for f in colorized_string board march_solver
+do
+ ruby -Ilib ./lib/colonial_twilight/$f.rb
+done