449 lines
17 KiB
C#
449 lines
17 KiB
C#
using System;
|
||
using System.Collections.Generic;
|
||
using System.Linq;
|
||
using System.Text;
|
||
using UnityEngine;
|
||
|
||
public class Solver
|
||
{
|
||
// -------- Параметры/пресет --------
|
||
private static int ROWS = 6;
|
||
private static int COLS = 7;
|
||
|
||
private static readonly int[] MoveOrder = new[] { 3, 4, 2, 5, 1, 6, 0 }; // центр → края
|
||
private static readonly int[] CenterWeights = new[] { 3, 4, 5, 7, 5, 4, 3 }; // «полуцентр» тоже ценим
|
||
|
||
private static System.Random rand = new System.Random();
|
||
|
||
// текущие фигуры бота и оппонента — задаём при вызове FindBestMove
|
||
private static CellState BotPiece;
|
||
private static CellState HumanPiece;
|
||
|
||
private static int DEPTH = 8;
|
||
private static int WIN_SCORE = 1_000_000;
|
||
private static int TWO_IN_ROW = 100;
|
||
private static int THREE_IN_ROW = 500;
|
||
private static int CENTER_COLUMN_BONUS = 20;
|
||
private static int BLOCK_OPPONENT_BONUS = 5_000;
|
||
|
||
private static float RANDOM_MOVE_RATE = 0f;
|
||
private static float MISTAKE_RATE = 0f;
|
||
private static float TEMPERATURE = 0f;
|
||
private static float SCORE_NOISE_SIGMA = 0f;
|
||
private static int TOP_K = 1;
|
||
private static float AVOID_LOSS_BAN_PROB = 1.0f; // 0..1 — с какой вероятностью мы ВООБЩЕ отсекаем ходы, ведущие к немедленному проигрышу
|
||
private static int IMMEDIATE_LOSS_PENALTY = 10000; // штраф, если такой ход всё же в корзине (мягко отталкивает)
|
||
|
||
|
||
public static void SetPreset(DifficultyPreset preset)
|
||
{
|
||
//Debug.Log(preset.name);
|
||
if (preset == null) return;
|
||
DEPTH = preset.Depth;
|
||
WIN_SCORE = preset.WinBonus;
|
||
TWO_IN_ROW = preset.RowOfTwoBonus;
|
||
THREE_IN_ROW = preset.RowOfThree;
|
||
CENTER_COLUMN_BONUS = preset.CenterBonus;
|
||
BLOCK_OPPONENT_BONUS = preset.BlockBonus;
|
||
|
||
RANDOM_MOVE_RATE = preset.RandomMoveRate;
|
||
MISTAKE_RATE = preset.MistakeRate;
|
||
TEMPERATURE = preset.Temperature;
|
||
SCORE_NOISE_SIGMA = preset.ScoreNoiseSigma;
|
||
TOP_K = Mathf.Max(1, preset.TopK);
|
||
AVOID_LOSS_BAN_PROB = Mathf.Clamp01(preset.AvoidLossBanProb);
|
||
IMMEDIATE_LOSS_PENALTY = preset.IMMEDIATE_LOSS_PENALTY;
|
||
|
||
//Debug.Log($"[Solver] Preset: {preset.Description}");
|
||
}
|
||
|
||
// -------- Публичный API --------
|
||
public static int FindBestMove(CellState[,] board, CellState currentPlayer)
|
||
{
|
||
ROWS = board.GetLength(0);
|
||
COLS = board.GetLength(1);
|
||
|
||
// сохраняем, за кого сейчас считаем
|
||
BotPiece = currentPlayer;
|
||
HumanPiece = (currentPlayer == CellState.Player1) ? CellState.Player2 : CellState.Player1;
|
||
|
||
var root = EvaluateRootMoves(board, DEPTH);
|
||
|
||
// дальше код остаётся тот же
|
||
if (AVOID_LOSS_BAN_PROB > 0f)
|
||
root.RemoveAll(m => LeadsToImmediateLoss(board, m.col) && rand.NextDouble() < AVOID_LOSS_BAN_PROB);
|
||
|
||
if (root.Count == 0)
|
||
root = EvaluateRootMoves(board, Math.Max(1, DEPTH - 1));
|
||
|
||
List<(int col, double score)> noisy = new(root.Count);
|
||
foreach (var (col, score) in root)
|
||
{
|
||
double val = score;
|
||
|
||
if (IMMEDIATE_LOSS_PENALTY > 0 && LeadsToImmediateLoss(board, col))
|
||
val -= IMMEDIATE_LOSS_PENALTY;
|
||
|
||
if (SCORE_NOISE_SIGMA > 0f)
|
||
val += NextGaussian(0, SCORE_NOISE_SIGMA);
|
||
|
||
noisy.Add((col, val));
|
||
}
|
||
|
||
noisy.Sort((a, b) => b.score.CompareTo(a.score));
|
||
var candidates = noisy.Take(Mathf.Min(TOP_K, noisy.Count)).ToList();
|
||
|
||
if (rand.NextDouble() < MISTAKE_RATE && candidates.Count > 1)
|
||
for (int i = 1; i < candidates.Count; i++)
|
||
if (!(AVOID_LOSS_BAN_PROB >= 1f && LeadsToImmediateLoss(board, candidates[i].col)))
|
||
return candidates[i].col;
|
||
|
||
if (TEMPERATURE > 0f && candidates.Count > 1)
|
||
return SampleSoftmax(candidates, TEMPERATURE);
|
||
|
||
return candidates[0].col;
|
||
}
|
||
|
||
// -------- Корневые ходы --------
|
||
private static List<(int col, int score)> EvaluateRootMoves(CellState[,] board, int depth)
|
||
{
|
||
var result = new List<(int col, int score)>();
|
||
var valid = GetValidLocations(board);
|
||
if (valid.Count == 0) return result;
|
||
|
||
foreach (int col in MoveOrder)
|
||
{
|
||
if (!valid.Contains(col)) continue;
|
||
int row = GetNextOpenRow(board, col);
|
||
if (row < 0) continue;
|
||
|
||
// применяем ход бота
|
||
board[row, col] = BotPiece;
|
||
|
||
// если сразу победа — отлично
|
||
if (WinningMoveAt(board, row, col, BotPiece))
|
||
{
|
||
board[row, col] = CellState.Empty;
|
||
result.Add((col, WIN_SCORE * depth));
|
||
continue;
|
||
}
|
||
|
||
int score = Minimax(board, depth - 1, int.MinValue, int.MaxValue, false, row, col, BotPiece).score;
|
||
|
||
board[row, col] = CellState.Empty;
|
||
result.Add((col, score));
|
||
}
|
||
return result;
|
||
}
|
||
|
||
private static bool LeadsToImmediateLoss(CellState[,] board, int botCol)
|
||
{
|
||
int row = GetNextOpenRow(board, botCol);
|
||
if (row < 0) return false;
|
||
|
||
// бот сделал ход
|
||
board[row, botCol] = BotPiece;
|
||
|
||
// если этот ход уже выигрывает нам игру — не считаем его "ведущим к проигрышу",
|
||
// соперник просто не получит ход
|
||
if (WinningMoveAt(board, row, botCol, BotPiece))
|
||
{
|
||
board[row, botCol] = CellState.Empty;
|
||
return false;
|
||
}
|
||
|
||
// может ли оппонент выиграть в 1 ход?
|
||
bool res = HasImmediateWin(board, HumanPiece);
|
||
|
||
// откат
|
||
board[row, botCol] = CellState.Empty;
|
||
return res;
|
||
}
|
||
|
||
/*private static bool LeadsToImmediateLoss(CellState[,] board, int botCol)
|
||
{
|
||
int row = GetNextOpenRow(board, botCol);
|
||
if (row < 0) return false;
|
||
|
||
// бот сделал ход
|
||
board[row, botCol] = BOT;
|
||
|
||
// СНАЧАЛА проверяем, не выигрывает ли сам бот этим ходом
|
||
bool botWins = WinningMoveAt(board, row, botCol, BOT);
|
||
|
||
// может ли человек выиграть в 1 ход?
|
||
bool opponentWins = HasImmediateWin(board, HUMAN);
|
||
|
||
// откат
|
||
board[row, botCol] = CellState.Empty;
|
||
|
||
// Если бот выигрывает - это не проигрышная позиция
|
||
// Если бот не выигрывает, но противник может - это проигрышная позиция
|
||
return !botWins && opponentWins;
|
||
}*/
|
||
|
||
|
||
// -------- Минимакс --------
|
||
// maximizingPlayer == true → ход бота (BOT)
|
||
// maximizingPlayer == false → ход человека (HUMAN)
|
||
private static (int column, int score) Minimax(
|
||
CellState[,] board, int depth, int alpha, int beta,
|
||
bool maximizingPlayer, int lastRow, int lastCol, CellState lastPlayer)
|
||
{
|
||
if (lastRow >= 0 && WinningMoveAt(board, lastRow, lastCol, lastPlayer))
|
||
{
|
||
int s = (lastPlayer == BotPiece ? +WIN_SCORE : -WIN_SCORE) * Math.Max(1, depth);
|
||
return (-1, s);
|
||
}
|
||
|
||
var valid = GetValidLocations(board);
|
||
if (valid.Count == 0 || depth == 0)
|
||
return (-1, EvaluatePosition(board, BotPiece));
|
||
|
||
if (maximizingPlayer)
|
||
{
|
||
int best = int.MinValue;
|
||
int bestCol = valid[0];
|
||
|
||
foreach (int col in MoveOrder)
|
||
{
|
||
if (!valid.Contains(col)) continue;
|
||
int r = GetNextOpenRow(board, col);
|
||
if (r < 0) continue;
|
||
|
||
board[r, col] = BotPiece;
|
||
var child = Minimax(board, depth - 1, alpha, beta, false, r, col, BotPiece);
|
||
board[r, col] = CellState.Empty;
|
||
|
||
if (child.score > best) { best = child.score; bestCol = col; }
|
||
alpha = Math.Max(alpha, best);
|
||
if (alpha >= beta) break;
|
||
}
|
||
return (bestCol, best);
|
||
}
|
||
else
|
||
{
|
||
int best = int.MaxValue;
|
||
int bestCol = valid[0];
|
||
|
||
foreach (int col in MoveOrder)
|
||
{
|
||
if (!valid.Contains(col)) continue;
|
||
int r = GetNextOpenRow(board, col);
|
||
if (r < 0) continue;
|
||
|
||
board[r, col] = HumanPiece;
|
||
var child = Minimax(board, depth - 1, alpha, beta, true, r, col, HumanPiece);
|
||
board[r, col] = CellState.Empty;
|
||
|
||
if (child.score < best) { best = child.score; bestCol = col; }
|
||
beta = Math.Min(beta, best);
|
||
if (alpha >= beta) break;
|
||
}
|
||
return (bestCol, best);
|
||
}
|
||
}
|
||
|
||
// -------- Эвристика --------
|
||
private static int EvaluatePosition(CellState[,] board, CellState perspective /* всегда BOTpiece */)
|
||
{
|
||
int score = 0;
|
||
var opp = (perspective == CellState.Player1) ? CellState.Player2 : CellState.Player1;
|
||
|
||
// 1) Центр (весим 3-4-5-7-5-4-3), не масштабируем на DEPTH
|
||
for (int r = 0; r < ROWS; r++)
|
||
for (int c = 0; c < COLS; c++)
|
||
if (board[r, c] == perspective)
|
||
score += CENTER_COLUMN_BONUS * CenterWeights[c];
|
||
|
||
// 2) Потенциалы (гравитация учитывается)
|
||
score += CountPotentialLinesPlayable(board, perspective, 3) * THREE_IN_ROW;
|
||
score += CountPotentialLinesPlayable(board, perspective, 2) * TWO_IN_ROW;
|
||
|
||
// 3) Наказание за потенциалы оппонента
|
||
score -= CountPotentialLinesPlayable(board, opp, 3) * THREE_IN_ROW * 2;
|
||
score -= CountPotentialLinesPlayable(board, opp, 2) * TWO_IN_ROW;
|
||
|
||
// 4) Немедленная угроза оппонента → сильный штраф (чтобы бот приоритизировал блок)
|
||
if (HasImmediateWin(board, opp))
|
||
score -= BLOCK_OPPONENT_BONUS;
|
||
|
||
return score;
|
||
}
|
||
|
||
// Счёт «окон» длины 4, где pieceCount==length и остальные пусты, причём
|
||
// хотя бы одна из пустых клеток «играбельна» (подперта снизу или нижняя граница).
|
||
private static int CountPotentialLinesPlayable(CellState[,] b, CellState piece, int length)
|
||
{
|
||
int total = 0;
|
||
|
||
bool In(int r, int c) => r >= 0 && r < ROWS && c >= 0 && c < COLS;
|
||
bool PlayableEmpty(int r, int c) => r == ROWS - 1 || b[r + 1, c] != CellState.Empty;
|
||
|
||
int ScanDir(int dr, int dc)
|
||
{
|
||
int cnt = 0;
|
||
// стартовые точки так, чтобы окно из 4 влазило
|
||
for (int r0 = 0; r0 < ROWS; r0++)
|
||
{
|
||
for (int c0 = 0; c0 < COLS; c0++)
|
||
{
|
||
int r1 = r0 + dr * 3, c1 = c0 + dc * 3;
|
||
if (!In(r1, c1)) continue;
|
||
|
||
int p = 0, e = 0;
|
||
bool hasPlayableEmpty = false;
|
||
bool blocked = false;
|
||
|
||
for (int k = 0; k < 4; k++)
|
||
{
|
||
int rr = r0 + dr * k, cc = c0 + dc * k;
|
||
var v = b[rr, cc];
|
||
if (v == piece) p++;
|
||
else if (v == CellState.Empty)
|
||
{
|
||
e++;
|
||
if (PlayableEmpty(rr, cc)) hasPlayableEmpty = true;
|
||
}
|
||
else // оппонент
|
||
{
|
||
blocked = true;
|
||
break;
|
||
}
|
||
}
|
||
|
||
if (!blocked && p == length && e == 4 - length && (length == 4 || hasPlayableEmpty))
|
||
cnt++;
|
||
}
|
||
}
|
||
return cnt;
|
||
}
|
||
|
||
total += ScanDir(0, +1); // горизонтали
|
||
total += ScanDir(+1, 0); // вертикали
|
||
total += ScanDir(+1, +1); // диагональ "\"
|
||
total += ScanDir(-1, +1); // диагональ "/"
|
||
return total;
|
||
}
|
||
|
||
// -------- Хелперы по ходам/победам --------
|
||
private static List<int> GetValidLocations(CellState[,] board)
|
||
{
|
||
var res = new List<int>(COLS);
|
||
for (int c = 0; c < COLS; c++)
|
||
if (board[0, c] == CellState.Empty)
|
||
res.Add(c);
|
||
return res;
|
||
}
|
||
|
||
private static int GetNextOpenRow(CellState[,] board, int col)
|
||
{
|
||
for (int r = ROWS - 1; r >= 0; r--)
|
||
if (board[r, col] == CellState.Empty) return r;
|
||
return -1;
|
||
}
|
||
|
||
private static bool HasImmediateWin(CellState[,] board, CellState player)
|
||
{
|
||
var valid = GetValidLocations(board);
|
||
foreach (int c in valid)
|
||
{
|
||
int r = GetNextOpenRow(board, c);
|
||
if (r < 0) continue;
|
||
board[r, c] = player;
|
||
bool win = WinningMoveAt(board, r, c, player);
|
||
board[r, c] = CellState.Empty;
|
||
if (win) return true;
|
||
}
|
||
return false;
|
||
}
|
||
|
||
private static bool WinningMoveAt(CellState[,] b, int r, int c, CellState p)
|
||
{
|
||
bool In(int rr, int cc) => rr >= 0 && rr < ROWS && cc >= 0 && cc < COLS;
|
||
|
||
int CountDir(int dr, int dc)
|
||
{
|
||
int rr = r + dr, cc = c + dc, cnt = 0;
|
||
while (In(rr, cc) && b[rr, cc] == p) { cnt++; rr += dr; cc += dc; }
|
||
return cnt;
|
||
}
|
||
|
||
// — (горизонталь)
|
||
if (1 + CountDir(0, -1) + CountDir(0, +1) >= 4) return true;
|
||
// | (вертикаль)
|
||
if (1 + CountDir(-1, 0) + CountDir(+1, 0) >= 4) return true;
|
||
// \ (диагональ)
|
||
if (1 + CountDir(-1, -1) + CountDir(+1, +1) >= 4) return true;
|
||
// / (диагональ)
|
||
if (1 + CountDir(-1, +1) + CountDir(+1, -1) >= 4) return true;
|
||
|
||
return false;
|
||
}
|
||
|
||
// -------- Стохастика на корне --------
|
||
/// <summary>
|
||
/// При околонулевой температуре с великой вероятностью лучший по score
|
||
/// При температуре 1 вероятность по соотношению очков
|
||
/// При более высоких температурах вероятности равномерно разглаживаются
|
||
/// </summary>
|
||
private static int SampleSoftmax(List<(int col, double score)> items, float temperature)
|
||
{
|
||
//StringBuilder sb = new();
|
||
|
||
//находим максимум оценок
|
||
double max = items.Max(x => x.score);
|
||
|
||
|
||
//попытка нормализовать оценки
|
||
|
||
|
||
//Готовим накопители
|
||
double sum = 0;
|
||
double[] e = new double[items.Count];
|
||
|
||
//sb.Append("[Экспоненты]\n");
|
||
//Перебираем items (Считает экспоненты “нормализованных” логитов)
|
||
for (int i = 0; i < items.Count; i++)
|
||
{
|
||
//из кандидата вычитаем max, делим разность на температуру
|
||
double v = (items[i].score - max) / Math.Max(1e-6, (double)temperature);
|
||
|
||
//берем экспоненту от результата
|
||
double ev = Math.Exp(v);
|
||
|
||
//заносим преобразованные данне в накопители
|
||
|
||
//sb.Append($"{items[i]} -> {ev}\n");
|
||
e[i] = ev;//счета, возведенные в экспоненты
|
||
sum += ev;
|
||
}
|
||
//Debug.Log(sb.ToString());
|
||
|
||
|
||
//жеребьевка по накопленным весам
|
||
double
|
||
r = rand.NextDouble() * sum,
|
||
acc = 0;//сюда суммируются экспоненты очков (сумма весов)
|
||
|
||
for (int i = 0; i < items.Count; i++)
|
||
{
|
||
acc += e[i];
|
||
if (r <= acc)
|
||
{
|
||
//Debug.Log($"Выбранный вариант {items[i].col}");
|
||
return items[i].col;//выбор по ленте
|
||
}
|
||
}
|
||
return items[0].col; //на всякий случай возвращаем лучший
|
||
}
|
||
|
||
private static double NextGaussian(double mu, double sigma)
|
||
{
|
||
double u1 = 1.0 - rand.NextDouble();
|
||
double u2 = 1.0 - rand.NextDouble();
|
||
double z0 = Math.Sqrt(-2.0 * Math.Log(u1)) * Math.Cos(2.0 * Math.PI * u2);
|
||
return mu + sigma * z0;
|
||
}
|
||
}
|