327 lines
10 KiB
Go
327 lines
10 KiB
Go
package main
|
||
|
||
import "errors"
|
||
|
||
// ПРИМЕЧАНИЕ О ПРАВИЛАХ: реализованы базовые правила Го — свободы
|
||
// групп камней, взятие групп без свобод, запрет самоубийственного
|
||
// хода (кроме случая, когда ход сам берёт вражеские камни и тем
|
||
// самым получает свободу), простое правило ко (нельзя немедленно
|
||
// воссоздать позицию, существовавшую до хода соперника). Подсчёт
|
||
// очков — по КИТАЙСКИМ (площадным) правилам: очки = количество
|
||
// своих камней на доске + количество пустых точек, граничащих
|
||
// ИСКЛЮЧИТЕЛЬНО с этим цветом (нейтральные точки, граничащие с
|
||
// обоими цветами, не засчитываются никому). Белые получают коми
|
||
// (компенсацию за то, что чёрные ходят первыми) — 7.5 очка на
|
||
// любом размере доски (в реальности коми иногда варьируется в
|
||
// зависимости от размера доски и разновидности правил — здесь для
|
||
// простоты используется одно фиксированное значение).
|
||
//
|
||
// СУЩЕСТВЕННОЕ УПРОЩЕНИЕ: фаза "удаления мёртвых камней" перед
|
||
// подсчётом очков НЕ реализована. После двух пасов подряд партия
|
||
// сразу же оценивается по камням, буквально оставшимся на доске —
|
||
// если камень технически окружён, но не взят взаправду, он
|
||
// засчитывается как живой своему цвету. Это значит, что для
|
||
// корректного счёта игроки должны реально ВЗЯТЬ мёртвые камни
|
||
// соперника до двух пасов, а не полагаться на то, что они "и так
|
||
// мертвы". Тройное повторение позиции (супер-ко) не реализовано —
|
||
// только простое ко (одна запрещённая точка на один ход вперёд).
|
||
|
||
// GoColor — цвет камня. GoEmpty используется как значение пустой
|
||
// точки на доске.
|
||
type GoColor int
|
||
|
||
const (
|
||
GoEmpty GoColor = iota
|
||
GoBlack
|
||
GoWhite
|
||
)
|
||
|
||
func (c GoColor) Opponent() GoColor {
|
||
switch c {
|
||
case GoBlack:
|
||
return GoWhite
|
||
case GoWhite:
|
||
return GoBlack
|
||
}
|
||
return GoEmpty
|
||
}
|
||
|
||
// GoPos — координаты точки пересечения (0-based, row/col).
|
||
type GoPos struct {
|
||
Row, Col int
|
||
}
|
||
|
||
// GoKomi — компенсация очков белым за то, что чёрные ходят первыми.
|
||
const GoKomi = 7.5
|
||
|
||
var (
|
||
ErrGoOutOfBounds = errors.New("точка вне пределов доски")
|
||
ErrGoOccupied = errors.New("точка уже занята")
|
||
ErrGoSuicide = errors.New("этот ход самоубийственный — так ходить нельзя")
|
||
ErrGoKoViolation = errors.New("этот ход запрещён правилом ко")
|
||
ErrGoGameOver = errors.New("партия уже завершена")
|
||
)
|
||
|
||
// GoResult — итог завершившейся партии.
|
||
type GoResult struct {
|
||
BlackScore float64
|
||
WhiteScore float64
|
||
Winner GoColor
|
||
}
|
||
|
||
// GoGameState — полное состояние партии в Го.
|
||
type GoGameState struct {
|
||
Size int
|
||
Board [][]GoColor // Board[row][col]
|
||
Turn GoColor
|
||
|
||
Passes int // подряд идущих пасов (0, 1 или 2 — на 2 партия завершается)
|
||
|
||
CapturedByBlack int // сколько камней взяли чёрные (для отображения, не влияет на площадной счёт)
|
||
CapturedByWhite int
|
||
|
||
prevBoardBeforeOpponentMove [][]GoColor // снимок доски до хода соперника — для правила ко
|
||
|
||
Result *GoResult
|
||
}
|
||
|
||
// NewGoGame создаёт новую пустую партию на доске size x size (обычно
|
||
// 9, 13 или 19). Первый ход — за чёрными.
|
||
func NewGoGame(size int) *GoGameState {
|
||
board := make([][]GoColor, size)
|
||
for r := range board {
|
||
board[r] = make([]GoColor, size)
|
||
}
|
||
return &GoGameState{Size: size, Board: board, Turn: GoBlack}
|
||
}
|
||
|
||
func (g *GoGameState) inBounds(p GoPos) bool {
|
||
return p.Row >= 0 && p.Row < g.Size && p.Col >= 0 && p.Col < g.Size
|
||
}
|
||
|
||
func goNeighbors(p GoPos) [4]GoPos {
|
||
return [4]GoPos{{p.Row - 1, p.Col}, {p.Row + 1, p.Col}, {p.Row, p.Col - 1}, {p.Row, p.Col + 1}}
|
||
}
|
||
|
||
func cloneGoBoard(b [][]GoColor) [][]GoColor {
|
||
clone := make([][]GoColor, len(b))
|
||
for i, row := range b {
|
||
clone[i] = append([]GoColor{}, row...)
|
||
}
|
||
return clone
|
||
}
|
||
|
||
func boardsEqual(a, b [][]GoColor) bool {
|
||
if a == nil || b == nil {
|
||
return a == nil && b == nil
|
||
}
|
||
if len(a) != len(b) {
|
||
return false
|
||
}
|
||
for i := range a {
|
||
if len(a[i]) != len(b[i]) {
|
||
return false
|
||
}
|
||
for j := range a[i] {
|
||
if a[i][j] != b[i][j] {
|
||
return false
|
||
}
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
|
||
// groupAndLiberties возвращает все точки связной группы одного
|
||
// цвета, содержащей pos, и число различных пустых точек-свобод,
|
||
// граничащих с этой группой.
|
||
func (g *GoGameState) groupAndLiberties(pos GoPos) ([]GoPos, int) {
|
||
color := g.Board[pos.Row][pos.Col]
|
||
visited := map[GoPos]bool{pos: true}
|
||
liberties := map[GoPos]bool{}
|
||
queue := []GoPos{pos}
|
||
group := []GoPos{pos}
|
||
|
||
for len(queue) > 0 {
|
||
cur := queue[0]
|
||
queue = queue[1:]
|
||
for _, n := range goNeighbors(cur) {
|
||
if !g.inBounds(n) {
|
||
continue
|
||
}
|
||
switch g.Board[n.Row][n.Col] {
|
||
case GoEmpty:
|
||
liberties[n] = true
|
||
case color:
|
||
if !visited[n] {
|
||
visited[n] = true
|
||
group = append(group, n)
|
||
queue = append(queue, n)
|
||
}
|
||
}
|
||
}
|
||
}
|
||
return group, len(liberties)
|
||
}
|
||
|
||
// removeGroup убирает с доски все камни группы (взятие).
|
||
func (g *GoGameState) removeGroup(group []GoPos) {
|
||
for _, p := range group {
|
||
g.Board[p.Row][p.Col] = GoEmpty
|
||
}
|
||
}
|
||
|
||
// Play делает ход текущего игрока в точку pos.
|
||
func (g *GoGameState) Play(pos GoPos) error {
|
||
if g.Result != nil {
|
||
return ErrGoGameOver
|
||
}
|
||
if !g.inBounds(pos) {
|
||
return ErrGoOutOfBounds
|
||
}
|
||
if g.Board[pos.Row][pos.Col] != GoEmpty {
|
||
return ErrGoOccupied
|
||
}
|
||
|
||
color := g.Turn
|
||
boardBeforeThisMove := cloneGoBoard(g.Board)
|
||
|
||
g.Board[pos.Row][pos.Col] = color
|
||
captured := 0
|
||
for _, n := range goNeighbors(pos) {
|
||
if !g.inBounds(n) || g.Board[n.Row][n.Col] != color.Opponent() {
|
||
continue
|
||
}
|
||
group, libs := g.groupAndLiberties(n)
|
||
if libs == 0 {
|
||
g.removeGroup(group)
|
||
captured += len(group)
|
||
}
|
||
}
|
||
|
||
_, ownLiberties := g.groupAndLiberties(pos)
|
||
if ownLiberties == 0 {
|
||
g.Board = boardBeforeThisMove // откат: самоубийственный ход
|
||
return ErrGoSuicide
|
||
}
|
||
|
||
if boardsEqual(g.Board, g.prevBoardBeforeOpponentMove) {
|
||
g.Board = boardBeforeThisMove // откат: нарушение правила ко
|
||
return ErrGoKoViolation
|
||
}
|
||
|
||
if color == GoBlack {
|
||
g.CapturedByBlack += captured
|
||
} else {
|
||
g.CapturedByWhite += captured
|
||
}
|
||
|
||
g.prevBoardBeforeOpponentMove = boardBeforeThisMove
|
||
g.Passes = 0
|
||
g.Turn = color.Opponent()
|
||
return nil
|
||
}
|
||
|
||
// Pass — текущий игрок пасует. Два паса подряд завершают партию.
|
||
func (g *GoGameState) Pass() error {
|
||
if g.Result != nil {
|
||
return ErrGoGameOver
|
||
}
|
||
g.Passes++
|
||
g.prevBoardBeforeOpponentMove = cloneGoBoard(g.Board)
|
||
g.Turn = g.Turn.Opponent()
|
||
if g.Passes >= 2 {
|
||
g.finishGame()
|
||
}
|
||
return nil
|
||
}
|
||
|
||
// IsLegal проверяет, допустим ли ход в pos для текущего игрока, не
|
||
// изменяя реальное состояние партии (использует пробный ход на
|
||
// копии доски).
|
||
func (g *GoGameState) IsLegal(pos GoPos) bool {
|
||
if g.Result != nil || !g.inBounds(pos) || g.Board[pos.Row][pos.Col] != GoEmpty {
|
||
return false
|
||
}
|
||
sim := &GoGameState{
|
||
Size: g.Size,
|
||
Board: cloneGoBoard(g.Board),
|
||
Turn: g.Turn,
|
||
prevBoardBeforeOpponentMove: g.prevBoardBeforeOpponentMove,
|
||
}
|
||
return sim.Play(pos) == nil
|
||
}
|
||
|
||
// finishGame считает итоговый счёт по площадным (китайским) правилам
|
||
// и определяет победителя.
|
||
func (g *GoGameState) finishGame() {
|
||
blackScore, whiteScore := 0, 0
|
||
for r := 0; r < g.Size; r++ {
|
||
for c := 0; c < g.Size; c++ {
|
||
switch g.Board[r][c] {
|
||
case GoBlack:
|
||
blackScore++
|
||
case GoWhite:
|
||
whiteScore++
|
||
}
|
||
}
|
||
}
|
||
|
||
visited := make([][]bool, g.Size)
|
||
for i := range visited {
|
||
visited[i] = make([]bool, g.Size)
|
||
}
|
||
for r := 0; r < g.Size; r++ {
|
||
for c := 0; c < g.Size; c++ {
|
||
if visited[r][c] || g.Board[r][c] != GoEmpty {
|
||
continue
|
||
}
|
||
region, touchesBlack, touchesWhite := g.floodEmptyRegion(GoPos{r, c}, visited)
|
||
switch {
|
||
case touchesBlack && !touchesWhite:
|
||
blackScore += len(region)
|
||
case touchesWhite && !touchesBlack:
|
||
whiteScore += len(region)
|
||
}
|
||
}
|
||
}
|
||
|
||
result := &GoResult{BlackScore: float64(blackScore), WhiteScore: float64(whiteScore) + GoKomi}
|
||
if result.BlackScore > result.WhiteScore {
|
||
result.Winner = GoBlack
|
||
} else {
|
||
result.Winner = GoWhite
|
||
}
|
||
g.Result = result
|
||
}
|
||
|
||
// floodEmptyRegion обходит связную область пустых точек, начиная с
|
||
// start, и определяет, граничит ли она с чёрными и/или белыми
|
||
// камнями.
|
||
func (g *GoGameState) floodEmptyRegion(start GoPos, visited [][]bool) (region []GoPos, touchesBlack, touchesWhite bool) {
|
||
queue := []GoPos{start}
|
||
visited[start.Row][start.Col] = true
|
||
region = append(region, start)
|
||
|
||
for len(queue) > 0 {
|
||
cur := queue[0]
|
||
queue = queue[1:]
|
||
for _, n := range goNeighbors(cur) {
|
||
if !g.inBounds(n) {
|
||
continue
|
||
}
|
||
switch g.Board[n.Row][n.Col] {
|
||
case GoEmpty:
|
||
if !visited[n.Row][n.Col] {
|
||
visited[n.Row][n.Col] = true
|
||
region = append(region, n)
|
||
queue = append(queue, n)
|
||
}
|
||
case GoBlack:
|
||
touchesBlack = true
|
||
case GoWhite:
|
||
touchesWhite = true
|
||
}
|
||
}
|
||
}
|
||
return region, touchesBlack, touchesWhite
|
||
}
|