Changeset 88

Timestamp:

Nov 16, 2014, 2:31:27 PM (10 years ago)

Author:

chronos

Message:

• Modified: Change attack probability calculation to use cache of precalculated values to speed up calculation dramatically.
• Added: Fallback as computer strategy element to withdraw border cells where enemy is stronger.
• Modified: Test of polygon canvas method modification.

Location:

trunk

Files:

• Forms/UFormMove.lfm (modified) (6 diffs)
• Forms/UFormMove.pas (modified) (1 diff)
• UGame.pas (modified) (12 diffs)

trunk/Forms/UFormMove.lfm

@@ -14 +14 @@
   object SpinEditOnce: TSpinEdit
     Left = 208
-    Height = 35
+    Height = 32
     Top = 40
     Width = 98
@@ -23 +23 @@
   object Label1: TLabel
     Left = 16
-    Height = 25
+    Height = 22
     Top = 40
-    Width = 54
+    Width = 46
     Caption = 'Once:'
     ParentColor = False
@@ -50 +50 @@
   object Label2: TLabel
     Left = 24
-    Height = 25
+    Height = 22
     Top = 136
-    Width = 100
+    Width = 87
     Caption = 'Every turn:'
     ParentColor = False
@@ -58 +58 @@
   object SpinEditRepeat: TSpinEdit
     Left = 208
-    Height = 35
+    Height = 32
     Top = 128
     Width = 98
@@ -131 +131 @@
   object Label3: TLabel
     Left = 16
-    Height = 25
+    Height = 22
     Top = 8
-    Width = 145
+    Width = 127
     Caption = 'Win probability:'
     ParentColor = False
@@ -139 +139 @@
   object LabelWinProbability: TLabel
     Left = 264
-    Height = 25
+    Height = 22
     Top = 8
     Width = 15

trunk/Forms/UFormMove.pas

@@ -78 +78 @@
   LabelWinProbability.Caption :=
     IntToStr(Round(Core.Game.AttackProbability(AttackCount + SpinEditOnce.Value,
-    DefendCount, 1) * 100)) + ' %';
+    DefendCount) * 100)) + ' %';
 end;
 

trunk/UGame.pas

@@ -111 +111 @@
   TCanvasEx = class(TCanvas)
     procedure TextOutEx(X,Y: Integer; const Text: string; MovePen: Boolean = True);
+    procedure PolygonEx(const Points: array of TPoint; Winding: Boolean);
   end;
 
@@ -278 +279 @@
     procedure IncreaseMoves;
     procedure Process;
+    procedure FallBack;
+    function AttackersCount(Cell: TCell): Integer;
   end;
 
@@ -343 +346 @@
     FRunning: Boolean;
     LoadedImageFileName: string;
+    ProbabilityMatrix: array of array of Single;
     procedure Attack(var AttackPower, DefendPower: Integer);
     procedure MoveAll(Player: TPlayer);
@@ -371 +375 @@
     FileName: string;
     FogOfWar: Boolean;
-    function AttackProbability(AttackCount, DefendCount, Depth: Integer): Double;
+    function AttackProbability(AttackCount, DefendCount: Integer): Double;
     procedure LoadConfig(Config: TXmlConfig; Path: string);
     procedure SaveConfig(Config: TXmlConfig; Path: string);
@@ -703 +707 @@
 end;
 
+procedure TCanvasEx.PolygonEx(const Points: array of TPoint; Winding: Boolean);
+begin
+  //Changing;
+  //RequiredState([csHandleValid, csBrushValid, csPenValid]);
+  LCLIntf.Polygon(Handle, @Points[0], Length(Points), Winding);
+  //Changed;
+end;
+
+
 { TCells }
 
@@ -1232 +1245 @@
       Points[I] := View.CellToCanvasPos(Cell.Polygon[I]);
     Brush.Style := bsSolid;
-    Polygon(Points, False, 0, Length(Points));
+    //Polygon(Points, False, 0, Length(Points));
+    TCanvasEx(Canvas).PolygonEx(Points, False);
+    //MoveTo(Points[0].X, Points[0].Y);
+    //LineTo(Points[1].X, Points[1].Y);
 
     // Show cell text
@@ -1789 +1805 @@
 
   // Sort descending to attack cells with higher power first
-  // Higher power enemy cells grow faster and is more dangerous
+  // Higher power enemy cells can grow faster and is more dangerous
   TargetCells.Sort(CellCompareDescending);
 
@@ -1828 +1844 @@
   NewTargetCells: TCells;
   Cells2: TCells;
+  MovedPower: Integer;
 begin
   // We need to move available power to borders to be available for attacks
@@ -1882 +1899 @@
               Inc(CanAttack);
             end;
-            if CanAttack = 0 then
-              Game.SetMove(TCell(Neighbors[I]), TCell(TargetCells[C]), TCell(Neighbors[I]).GetAvialPower, False);
+            if CanAttack = 0 then begin
+              MovedPower := TCell(Neighbors[I]).GetAvialPower;
+              if (TCell(TargetCells[C]).GetAvialPower + TCell(TargetCells[C]).GetAttackPower + MovedPower) > Game.Map.MaxPower then
+                MovedPower := Game.Map.MaxPower - TCell(TargetCells[C]).GetAvialPower - TCell(TargetCells[C]).GetAttackPower;
+              Game.SetMove(TCell(Neighbors[I]), TCell(TargetCells[C]), MovedPower, False);
+            end;
           end;
           TCell(Neighbors[I]).Mark := True;
@@ -1920 +1941 @@
   InnerMoves;
   IncreaseMoves;
+  //FallBack;
   CellProcessDirection := not CellProcessDirection;
+end;
+
+procedure TComputer.FallBack;
+var
+  C: Integer;
+  I: Integer;
+  AllCells: TCells;
+  BorderCells: TCells;
+  EnemyPower: Integer;
+begin
+  BorderCells := TCells.Create;
+  BorderCells.OwnsObjects := False;
+  AllCells := Game.Map.Cells;
+
+  // Get list of border cells
+  for C := 0 to AllCells.Count - 1 do
+  with TCell(AllCells[C]) do begin
+    if (Terrain <> ttVoid) and (Player = Game.CurrentPlayer)  then begin
+      if AttackersCount(TCell(AllCells[C])) > 0 then
+        BorderCells.Add(AllCells[C]);
+    end;
+  end;
+
+  // Move all units back to inner area from weak border cells
+  for C := 0 to BorderCells.Count - 1 do
+  with TCell(BorderCells[C]) do begin
+    // Calculate enemy power
+    // TODO: Do not sum different enemy power to one value
+    EnemyPower := 0;
+    for I := 0 to Neighbors.Count - 1 do
+    if (TCell(Neighbors[I]).Player <> Game.CurrentPlayer) and (TCell(Neighbors[I]).Player <> nil) then begin
+      Inc(EnemyPower, TCell(Neighbors[I]).Power);
+    end;
+    if EnemyPower > (GetAvialPower + GetAttackPower) then begin
+      // Fallback
+      for I := MovesTo.Count - 1 downto 0 do
+        TUnitMove(MovesTo[I]).Free;
+      for I := 0 to Neighbors.Count - 1 do
+      if (TCell(Neighbors[I]).Player = Game.CurrentPlayer) and (AttackersCount(TCell(Neighbors[I])) = 0) then begin
+
+        Game.SetMove(TCell(BorderCells[C]), TCell(Neighbors[I]), GetAvialPower, False);
+        Break;
+      end;
+    end;
+  end;
+
+  BorderCells.Free;
+end;
+
+function TComputer.AttackersCount(Cell: TCell): Integer;
+var
+  I: Integer;
+begin
+  Result := 0;
+  for I := 0 to Cell.Neighbors.Count - 1 do
+  if (TCell(Cell.Neighbors[I]).Player <> Game.CurrentPlayer) and
+    (TCell(Cell.Neighbors[I]).Player <> nil) then begin
+      Inc(Result);
+  end;
 end;
 
@@ -2055 +2136 @@
 end;
 
-function TGame.AttackProbability(AttackCount, DefendCount, Depth: Integer): Double;
+function TGame.AttackProbability(AttackCount, DefendCount: Integer): Double;
 var
   OA, OD: Integer;
+  Len: Integer;
+  I: Integer;
 begin
   if AttackCount = 0 then begin
     Result := 0;
     Exit;
+  end;
+  if DefendCount = 0 then begin
+    Result := 1;
+    Exit;
+  end;
+
+  // Enlarge probability cache table on demand
+  if Length(ProbabilityMatrix) < AttackCount then begin
+    SetLength(ProbabilityMatrix, AttackCount);
+  end;
+  if Length(ProbabilityMatrix[AttackCount - 1]) < DefendCount then begin
+    Len := Length(ProbabilityMatrix[AttackCount - 1]);
+    SetLength(ProbabilityMatrix[AttackCount - 1], DefendCount);
+    for I := Len to Length(ProbabilityMatrix[AttackCount - 1]) - 1 do
+      ProbabilityMatrix[AttackCount - 1][I] := -1;
+  end;
+
+  if ProbabilityMatrix[AttackCount - 1, DefendCount - 1] <> -1 then begin
+    // Use cached value
+    Result := ProbabilityMatrix[AttackCount - 1, DefendCount - 1];
+    Exit;
   end else Result := 1;
-  if DefendCount = 0 then Exit;
-  // TODO: Limiting depth is not solving problem with probability of high near
-  // numbers like 96 vs. 92. Complexity of calculation should be simplified
-  // in different way
-  if Depth > 10 then Exit;
 
   OA := Min(AttackCount, 3);
@@ -2073 +2172 @@
 
   if (OA = 1) and (OD = 1) then
-    Result := 0.4167 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
-      0.5833 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
+    Result := 0.4167 * AttackProbability(AttackCount, DefendCount - 1) +
+      0.5833 * AttackProbability(AttackCount - 1, DefendCount)
   else if (OA = 2) and (OD = 1) then
-    Result := 0.5787 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
-      0.4213 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
+    Result := 0.5787 * AttackProbability(AttackCount, DefendCount - 1) +
+      0.4213 * AttackProbability(AttackCount - 1, DefendCount)
   else if (OA = 3) and (OD = 1) then
-    Result := 0.6597 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
-      0.3403 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
+    Result := 0.6597 * AttackProbability(AttackCount, DefendCount - 1) +
+      0.3403 * AttackProbability(AttackCount - 1, DefendCount)
   else if (OA = 1) and (OD = 2) then
-    Result := 0.2546 * AttackProbability(AttackCount, DefendCount - 1, Depth + 1) +
-      0.7454 * AttackProbability(AttackCount - 1, DefendCount, Depth + 1)
+    Result := 0.2546 * AttackProbability(AttackCount, DefendCount - 1) +
+      0.7454 * AttackProbability(AttackCount - 1, DefendCount)
   else if (OA = 2) and (OD = 2) then
-    Result := 0.2276 * AttackProbability(AttackCount, DefendCount - 2, Depth + 1) +
-      0.4483 * AttackProbability(AttackCount - 2, DefendCount, Depth + 1) +
-      0.3241 * AttackProbability(AttackCount - 1, DefendCount - 1, Depth + 1)
+    Result := 0.2276 * AttackProbability(AttackCount, DefendCount - 2) +
+      0.4483 * AttackProbability(AttackCount - 2, DefendCount) +
+      0.3241 * AttackProbability(AttackCount - 1, DefendCount - 1)
   else if (OA = 3) and (OD = 2) then
-    Result := 0.3717 * AttackProbability(AttackCount, DefendCount - 2, Depth + 1) +
-      0.2926 * AttackProbability(AttackCount - 2, DefendCount, Depth + 1) +
-      0.3358 * AttackProbability(AttackCount - 1, DefendCount - 1, Depth + 1);
+    Result := 0.3717 * AttackProbability(AttackCount, DefendCount - 2) +
+      0.2926 * AttackProbability(AttackCount - 2, DefendCount) +
+      0.3358 * AttackProbability(AttackCount - 1, DefendCount - 1);
+  ProbabilityMatrix[AttackCount - 1, DefendCount - 1] := Result;
 end;