Something went wrong. Try again.
A bot for https://go.sky.boo that lets you play Go against TypeSafe's Jev.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665use std::collections::HashSet;
/// Go board. Cells are `u8` (0=empty, 1=black, 2=white) for compact/// storage and fast flood-fill — the domain-level `Color` enum lives in/// `crate::Color` and converts via `Color::as_u8` / `Color::from_u8`.#[derive(Clone, Debug)]pub struct Board { pub size: usize, pub cells: Vec<Vec<u8>>, pub ko_point: Option<(usize, usize)>,}
impl Board { pub fn new(size: usize) -> Self { Self { size, cells: vec![vec![0u8; size]; size], ko_point: None, } }
pub fn color_name(color: u8) -> &'static str { match color { 1 => "black", 2 => "white", _ => "unknown", } }
pub fn opponent(color: u8) -> u8 { match color { 1 => 2, 2 => 1, _ => 0, } }
fn neighbors(&self, x: usize, y: usize) -> Vec<(usize, usize)> { let mut n = Vec::with_capacity(4); if x > 0 { n.push((x - 1, y)); } if x + 1 < self.size { n.push((x + 1, y)); } if y > 0 { n.push((x, y - 1)); } if y + 1 < self.size { n.push((x, y + 1)); } n }
/// Flood-fill to find all stones in the group at (x, y). pub fn group_at(&self, x: usize, y: usize) -> HashSet<(usize, usize)> { let color = self.cells[y][x]; if color == 0 { return HashSet::new(); } let mut group = HashSet::new(); let mut stack = vec![(x, y)]; group.insert((x, y)); while let Some((cx, cy)) = stack.pop() { for (nx, ny) in self.neighbors(cx, cy) { if self.cells[ny][nx] == color && group.insert((nx, ny)) { stack.push((nx, ny)); } } } group }
/// Count liberties (empty orthogonal neighbors) of a group. pub fn liberties(&self, group: &HashSet<(usize, usize)>) -> usize { let mut libs = HashSet::new(); for &(x, y) in group { for (nx, ny) in self.neighbors(x, y) { if self.cells[ny][nx] == 0 { libs.insert((nx, ny)); } } } libs.len() }
/// Count how many opponent stones would be captured by placing `color` at (x, y), /// without mutating the board. pub fn would_capture(&self, x: usize, y: usize, color: u8) -> usize { if x >= self.size || y >= self.size || self.cells[y][x] != 0 { return 0; } let opp = Self::opponent(color); let mut total = 0; for (nx, ny) in self.neighbors(x, y) { if self.cells[ny][nx] == opp { let group = self.group_at(nx, ny); // Simulate: check if placing color at (x,y) would remove last liberty // A group's liberties minus the placement point let mut libs = self.liberties(&group); // If (x,y) is a liberty of this group, placing removes it if group.iter().any(|&(gx, gy)| { self.neighbors(gx, gy).iter().any(|&(nx2, ny2)| nx2 == x && ny2 == y) }) { libs = libs.saturating_sub(1); } if libs == 0 { total += group.len(); } } } total }
/// Place a stone and resolve captures. Returns the number of stones /// captured, or `None` if the cell is already occupied — untrusted /// replayed history (e.g. a duplicate on-chain move record) can violate /// this, unlike a placement this process already validated itself. pub fn try_apply_move(&mut self, x: usize, y: usize, color: u8) -> Option<usize> { if self.cells[y][x] != 0 { return None; } assert!(color == 1 || color == 2, "Invalid color {}", color);
Some(self.apply_move_unchecked(x, y, color)) }
/// Place a stone and resolve captures. Returns the number of stones captured. /// Panics if the cell is already occupied — callers must pre-validate /// (e.g. against `valid_placements`); use `try_apply_move` for untrusted input. pub fn apply_move(&mut self, x: usize, y: usize, color: u8) -> usize { assert!(self.cells[y][x] == 0, "Cell ({},{}) not empty", x, y); assert!(color == 1 || color == 2, "Invalid color {}", color);
self.apply_move_unchecked(x, y, color) }
fn apply_move_unchecked(&mut self, x: usize, y: usize, color: u8) -> usize {
self.cells[y][x] = color; let opp = Self::opponent(color);
// Capture all adjacent opponent groups with 0 liberties let mut captured_total = 0; let mut captured_stones = HashSet::new(); for (nx, ny) in self.neighbors(x, y) { if self.cells[ny][nx] == opp { let group = self.group_at(nx, ny); if self.liberties(&group) == 0 { captured_total += group.len(); captured_stones.extend(group); } } }
for &(cx, cy) in &captured_stones { self.cells[cy][cx] = 0; }
// Ko detection: exactly 1 stone captured and placed stone has exactly 1 liberty if captured_total == 1 { let placed_group = self.group_at(x, y); if self.liberties(&placed_group) == 1 { self.ko_point = captured_stones.into_iter().next(); } else { self.ko_point = None; } } else { self.ko_point = None; }
captured_total }
/// All valid placements for `color`, excluding ko point and suicide. pub fn valid_placements(&self, color: u8) -> Vec<(usize, usize)> { let opp = Self::opponent(color); let mut placements = Vec::new();
for y in 0..self.size { for x in 0..self.size { if self.cells[y][x] != 0 { continue; }
// Ko check if self.ko_point == Some((x, y)) { continue; }
// Suicide check: simulate placing and see if the placed group has liberties // (after capturing any opponent groups) let mut has_liberty = false; let mut would_capture_any = false;
// Check if any adjacent empty cell exists (immediate liberty) for (nx, ny) in self.neighbors(x, y) { if self.cells[ny][nx] == 0 { has_liberty = true; break; } }
if !has_liberty { // Check if placing would capture opponent groups for (nx, ny) in self.neighbors(x, y) { if self.cells[ny][nx] == opp { let group = self.group_at(nx, ny); let group_libs = self.liberties(&group); // This group currently has some liberties; (x,y) is one of them // After placing, if group_libs == 1, the group is captured if group_libs == 1 { would_capture_any = true; break; } } } }
if has_liberty || would_capture_any { placements.push((x, y)); } } }
placements }
/// Empty-region territory per color: flood-fill each empty region; a /// region touching only one color counts fully for that color, a /// region touching both (dame) or neither counts for neither. pub fn territory(&self) -> (usize, usize) { let mut visited = vec![vec![false; self.size]; self.size]; let mut black = 0; let mut white = 0;
for y in 0..self.size { for x in 0..self.size { if visited[y][x] || self.cells[y][x] != 0 { continue; } let mut region_size = 0; let mut stack = vec![(x, y)]; visited[y][x] = true; let mut touches_black = false; let mut touches_white = false;
while let Some((cx, cy)) = stack.pop() { region_size += 1; for (nx, ny) in self.neighbors(cx, cy) { match self.cells[ny][nx] { 1 => touches_black = true, 2 => touches_white = true, 0 if !visited[ny][nx] => { visited[ny][nx] = true; stack.push((nx, ny)); } _ => {} } } }
if touches_black && !touches_white { black += region_size; } else if touches_white && !touches_black { white += region_size; } } }
(black, white) }
/// Chinese-style area score: stones on the board plus surrounded /// territory. Used to settle a game after two consecutive passes — /// no dead-stone marking, every stone on the board counts as alive. pub fn area_score(&self) -> (usize, usize) { let (mut black, mut white) = self.territory(); for row in &self.cells { for &c in row { match c { 1 => black += 1, 2 => white += 1, _ => {} } } } (black, white) }}
#[cfg(test)]mod tests { use super::*;
#[test] fn test_empty_board_valid_placements() { let board = Board::new(9); let placements = board.valid_placements(1); assert_eq!(placements.len(), 81); }
#[test] fn test_territory_simple_regions() { // 3x3 board, black owns column 0, white owns column 2, column 1 empty: // B . W // B . W // B . W // Column 1's empty region touches both colors — dame, counts for neither. let mut board = Board::new(3); for y in 0..3 { board.cells[y][0] = 1; board.cells[y][2] = 2; } let (black, white) = board.territory(); assert_eq!((black, white), (0, 0), "column between two colors is dame, not territory"); }
#[test] fn test_territory_surrounded_region() { // 3x3 board, black stones in a plus shape around the center. Every // empty cell (4 corners + center) has only black neighbors — each // is its own isolated single-point region, all black territory. let mut board = Board::new(3); board.cells[0][1] = 1; board.cells[1][0] = 1; board.cells[1][2] = 1; board.cells[2][1] = 1; let (black, white) = board.territory(); assert_eq!((black, white), (5, 0)); }
#[test] fn test_area_score_counts_stones_plus_territory() { // Black stone plus one black-only territory point; empty board otherwise. let mut board = Board::new(3); board.cells[0][0] = 1; board.cells[0][1] = 1; // (0,2)/(1,0..2)/(2,*) all empty and touch only black in this tiny corner // setup except the far corner, which touches neither color. let (black_area, white_area) = board.area_score(); let stones = 2; // the two black stones placed above assert!(black_area >= stones, "area score must include the stones themselves"); assert_eq!(white_area, 0, "no white stones or white-only territory exist"); }
#[test] fn test_group_at_single_stone() { let mut board = Board::new(9); board.cells[4][4] = 1; let group = board.group_at(4, 4); assert_eq!(group.len(), 1); assert!(group.contains(&(4, 4))); }
#[test] fn test_liberties_corner() { let mut board = Board::new(9); board.cells[0][0] = 1; let group = board.group_at(0, 0); assert_eq!(board.liberties(&group), 2); }
#[test] fn test_liberties_center() { let mut board = Board::new(9); board.cells[4][4] = 1; let group = board.group_at(4, 4); assert_eq!(board.liberties(&group), 4); }
#[test] fn test_capture() { // White at (1,1), three black neighbors, last black at (2,1) captures // cells[y][x]: cells[1][1]=white, cells[0][1], cells[1][0], cells[1][2]=black // . B . (y=0: cells[0][1]=1) // B W B . (y=1: cells[1][0]=1, cells[1][1]=2, cells[1][2]=1 — but (1,2) not set) // . . . // Wait — cells[1][2] is (x=2,y=1). Let me be explicit: // White at (x=1,y=1). Neighbors: (0,1),(2,1),(1,0),(1,2) // Set 3 black, leave (2,1) empty for placement. let mut board = Board::new(9); board.cells[1][1] = 2; // white at (x=1, y=1) board.cells[1][0] = 1; // black at (x=0, y=1) board.cells[0][1] = 1; // black at (x=1, y=0) board.cells[2][1] = 1; // black at (x=1, y=2) // Place black at (x=2, y=1) to complete surround and capture let caps = board.apply_move(2, 1, 1); assert_eq!(caps, 1); assert_eq!(board.cells[1][1], 0); // captured }
#[test] fn test_ko_detection() { // Ko scenario: // . B W . // B . B W // . B W . let mut board = Board::new(9); board.cells[0][1] = 1; board.cells[0][2] = 2; board.cells[1][0] = 1; board.cells[1][2] = 1; board.cells[1][3] = 2; board.cells[2][1] = 1; board.cells[2][2] = 2; // White captures at (1,1) board.cells[1][1] = 0; // Black was at (1,1)? No, let me redo // Let's use a simpler ko: // . B W . // B W . W // . B W . // Black plays at (2,1) capturing white at (1,1) let mut board = Board::new(9); board.cells[0][1] = 1; // (1,0) board.cells[0][2] = 2; // (2,0) board.cells[1][0] = 1; // (0,1) board.cells[1][1] = 2; // (1,1) - white to be captured board.cells[1][3] = 2; // (3,1) board.cells[2][1] = 1; // (1,2) board.cells[2][2] = 2; // (2,2)
let caps = board.apply_move(2, 1, 1); // black captures at (2,1) assert_eq!(caps, 1); assert!(board.ko_point.is_some()); assert_eq!(board.ko_point.unwrap(), (1, 1)); }
#[test] fn test_suicide_prevented() { let mut board = Board::new(9); // Surround (4,4) with black, leave no liberties board.cells[3][4] = 1; board.cells[5][4] = 1; board.cells[4][3] = 1; board.cells[4][5] = 1; // White cannot play at (4,4) - suicide let placements = board.valid_placements(2); assert!(!placements.contains(&(4, 4))); }
#[test] fn test_would_capture() { // White at (x=1,y=1) with 3 black neighbors, one liberty at (x=2,y=1) // cells[1][1]=2, cells[1][0]=1, cells[0][1]=1, cells[2][1]=1 // Playing (x=2, y=1) = cells[1][2] as black should capture let mut board = Board::new(9); board.cells[1][1] = 2; // white at (x=1, y=1) board.cells[1][0] = 1; // black at (x=0, y=1) board.cells[0][1] = 1; // black at (x=1, y=0) board.cells[2][1] = 1; // black at (x=1, y=2) // (x=2, y=1) = cells[1][2] is empty — that's the liberty assert_eq!(board.would_capture(2, 1, 1), 1); }}
#[cfg(test)]mod proptests { use super::*; use proptest::prelude::*;
/// Generate a sequence of move indices (index into valid_placements at each step). /// Using 5×5 board for fast exploration — small enough to reach interesting /// states (captures, ko, suicide scenarios) in few moves. fn move_indices(max_moves: usize) -> impl Strategy<Value = Vec<usize>> { prop::collection::vec(0..max_moves, 0..max_moves) }
/// Apply a sequence of moves to a board, alternating black/white. /// Returns the final board and all intermediate states for invariant checking. fn play_sequence(indices: &[usize], board_size: usize) -> Vec<(Board, u8, usize, usize)> { let mut board = Board::new(board_size); let mut states = Vec::new(); let mut color: u8 = 1; // black starts
for &idx in indices { let valid = board.valid_placements(color); if valid.is_empty() { break; } let move_idx = idx % valid.len(); let (x, y) = valid[move_idx];
let predicted_caps = board.would_capture(x, y, color); let actual_caps = board.apply_move(x, y, color); states.push((board.clone(), color, x, y));
// Invariant: would_capture prediction matches apply_move result assert_eq!( predicted_caps, actual_caps, "would_capture({},{},{}) predicted {} but apply_move returned {}", x, y, color, predicted_caps, actual_caps );
color = if color == 1 { 2 } else { 1 }; }
states }
proptest! { #[test] fn all_cells_valid(indices in move_indices(80)) { let states = play_sequence(&indices, 5); for (board, _, _, _) in &states { for y in 0..board.size { for x in 0..board.size { assert!( board.cells[y][x] <= 2, "Invalid cell value {} at ({},{})", board.cells[y][x], x, y ); } } } }
#[test] fn placed_stone_exists(indices in move_indices(80)) { let states = play_sequence(&indices, 5); for (board, color, x, y) in &states { assert_eq!( board.cells[*y][*x], *color, "Stone at ({},{}) should be {} but is {}", x, y, Board::color_name(*color), board.cells[*y][*x] ); } }
#[test] fn valid_placements_are_actually_valid(indices in move_indices(80)) { let mut board = Board::new(5); let mut color: u8 = 1;
for &idx in &indices { let valid = board.valid_placements(color); if valid.is_empty() { break; }
// Every valid placement must: be empty, not be ko, and not be suicide for &(vx, vy) in &valid { assert_eq!(board.cells[vy][vx], 0, "valid_placements includes occupied cell ({},{})", vx, vy); assert!(board.ko_point != Some((vx, vy)), "valid_placements includes ko point ({},{})", vx, vy); }
let move_idx = idx % valid.len(); let (x, y) = valid[move_idx]; board.apply_move(x, y, color); color = if color == 1 { 2 } else { 1 }; } }
#[test] fn ko_prevents_immediate_recapture(indices in move_indices(80)) { let mut board = Board::new(5); let mut color: u8 = 1;
for &idx in &indices { let valid = board.valid_placements(color); if valid.is_empty() { break; }
// If ko is set, that point must not be in valid_placements if let Some(ko) = board.ko_point { assert!( !valid.contains(&ko), "Ko point ({},{}) appeared in valid_placements", ko.0, ko.1 ); }
let move_idx = idx % valid.len(); let (x, y) = valid[move_idx]; board.apply_move(x, y, color); color = if color == 1 { 2 } else { 1 }; } }
#[test] fn suicide_not_in_valid_placements(indices in move_indices(80)) { let mut board = Board::new(5); let mut color: u8 = 1;
for &idx in &indices { let valid = board.valid_placements(color); if valid.is_empty() { break; }
// For each valid placement, after playing it the placed group // must have > 0 liberties (i.e. it's not suicide) for &(vx, vy) in &valid { let mut test_board = board.clone(); test_board.apply_move(vx, vy, color); let group = test_board.group_at(vx, vy); let libs = test_board.liberties(&group); assert!( libs > 0, "Suicide: ({},{}) as {} has 0 liberties after placement", vx, vy, Board::color_name(color) ); }
let move_idx = idx % valid.len(); let (x, y) = valid[move_idx]; board.apply_move(x, y, color); color = if color == 1 { 2 } else { 1 }; } }
#[test] fn captured_stones_removed(indices in move_indices(80)) { let states = play_sequence(&indices, 5); // After each move, verify captured opponent stones are gone for (i, (board, _color, _x, _y)) in states.iter().enumerate() { let total: usize = (0..board.size) .flat_map(|y| (0..board.size).map(move |x| (x, y))) .filter(|&(x, y)| board.cells[y][x] != 0) .count();
assert!( total <= board.size * board.size, "Too many stones on board at step {}: {}", i, total ); } }
#[test] fn liberties_consistent_with_groups(indices in move_indices(80)) { let states = play_sequence(&indices, 5); for (board, _, _, _) in &states { let mut visited = vec![vec![false; board.size]; board.size]; for y in 0..board.size { for x in 0..board.size { if visited[y][x] || board.cells[y][x] == 0 { continue; } let group = board.group_at(x, y); let libs = board.liberties(&group);
// All stones in group must be same color for &(gx, gy) in &group { assert_eq!( board.cells[gy][gx], board.cells[y][x], "Group at ({},{}) contains mixed colors", gx, gy ); visited[gy][gx] = true; }
// Liberties must be empty cells let mut lib_set = HashSet::new(); for &(gx, gy) in &group { for (nx, ny) in board.neighbors(gx, gy) { if board.cells[ny][nx] == 0 { lib_set.insert((nx, ny)); } } } assert_eq!( libs, lib_set.len(), "Liberty count mismatch for group at ({},{})", x, y ); } } } } }}