Skip to content

Instantly share code, notes, and snippets.

@ymakino
Last active June 1, 2023 05:17
Show Gist options
  • Save ymakino/1ad8fdeb73fb199a72c3e36a120696f6 to your computer and use it in GitHub Desktop.
Save ymakino/1ad8fdeb73fb199a72c3e36a120696f6 to your computer and use it in GitHub Desktop.
An implementation of Reversi written in JavaScript.
#!/usr/bin/env node
function println() {
print(...arguments);
process.stdout.write("\n");
}
function print() {
for (d of arguments) {
process.stdout.write(d.toString());
}
}
class Board {
constructor(init){
this.black = '*';
this.white = 'o';
this.empty = ' ';
this.cells = [];
for (let i=0; i<8; i++) {
let line = [];
for (let j=0; j<8; j++) {
line.push(this.empty);
}
this.cells.push(line);
}
this.setCell(3, 3, this.white);
this.setCell(4, 4, this.white);
this.setCell(3, 4, this.black);
this.setCell(4, 3, this.black);
this.history = [];
this.boardHistory = [];
if (init) {
this.boardHistory.push(this.clone());
}
}
isInside(x, y) {
return 0 <= x && x < 8 && 0 <= y && y < 8;
}
setCell(x, y, c) {
this.cells[x][y] = c;
}
getCell(x, y) {
return this.cells[x][y];
}
isCell(x, y, c) {
return this.isInside(x, y) && this.getCell(x, y) == c;
}
isBlack(x, y) {
return this.isCell(x, y, this.black);
}
isWhite(x, y) {
return this.isCell(x, y, this.white);
}
isEmpty(x, y) {
return this.isInside(x, y) && this.getCell(x, y) == this.empty;
}
countCell(c) {
let count = 0;
for (let line of this.cells) {
for (let cell of line) {
if (cell == c) {
count++;
}
}
}
return count;
}
countBlack() {
return this.countCell(this.black);
}
countWhite() {
return this.countCell(this.white);
}
canTurnOver(x, y, dx, dy, selfColor, otherColor) {
if (dx == 0 && dy == 0) {
return false;
}
let xx = x + dx;
let yy = y + dy;
if (!this.isCell(xx, yy, otherColor)) {
return false;
}
for (;;) {
xx += dx;
yy += dy;
if (!this.isInside(xx, yy)) {
return false;
}
if (this.isCell(xx, yy, selfColor)) {
return true;
}
if (!this.isCell(xx, yy, otherColor)) {
return false;
}
}
}
turnOver(x, y, dx, dy) {
let selfColor;
let otherColor;
if (dx == 0 && dy == 0) {
return 0;
}
if (this.isBlack(x, y)) {
selfColor = this.black;
otherColor = this.white;
} else if (this.isWhite(x, y)) {
selfColor = this.white;
otherColor = this.black;
} else {
return 0;
}
let count = 0;
for (let xx = x+dx, yy = y+dy; this.isCell(xx, yy, otherColor); xx += dx, yy += dy) {
this.setCell(xx, yy, selfColor);
count++;
}
return count;
}
isFinished() {
return !(this.existsCandidatesBlack() || this.existsCandidatesWhite());
}
existsCandidates(selfColor, otherColor) {
return this.getCandidates(selfColor, otherColor).length != 0;
}
existsCandidatesBlack() {
return this.existsCandidates(this.black, this.white);
}
existsCandidatesWhite() {
return this.existsCandidates(this.white, this.black);
}
getCandidates(selfColor, otherColor) {
let places = [];
for (let y = 0; y < 8; y++) {
for (let x = 0; x < 8; x++) {
if (this.canPut(x, y, selfColor, otherColor)) {
places.push([x, y]);
}
}
}
return places;
}
getCandidatesBlack() {
return this.getCandidates(this.black, this.white);
}
getCandidatesWhite() {
return this.getCandidates(this.white, this.black);
}
canPut(x, y, selfColor, otherColor) {
if (!this.isEmpty(x, y)) {
return false;
}
for (let dx of [-1, 0, 1]) {
for (let dy of [-1, 0, 1]) {
if (this.canTurnOver(x, y, dx, dy, selfColor, otherColor)) {
return true;
}
}
}
return false;
}
canPutBlack(x, y) {
return this.canPut(x, y, this.black, this.white);
}
canPutWhite(x, y) {
return this.canPut(x, y, this.white, this.black);
}
put(x, y, selfColor, otherColor) {
if (!this.isEmpty(x, y)) {
return false;
}
this.setCell(x, y, selfColor);
for (let dx of [-1, 0, 1]) {
for (let dy of [-1, 0, 1]) {
if (this.canTurnOver(x, y, dx, dy, selfColor, otherColor)) {
this.turnOver(x, y, dx, dy);
}
}
}
this.history.push([x, y, selfColor]);
this.boardHistory.push(this.clone());
return true;
}
putBlack(x, y) {
return this.put(x, y, this.black, this.white);
}
putWhite(x, y) {
return this.put(x, y, this.white, this.black);
}
printBoard() {
println(' 0 1 2 3 4 5 6 7 ');
for (let y=0; y<8; y++) {
println(' +-+-+-+-+-+-+-+-+');
print(y.toString());
for (let x=0; x<8; x++) {
print('|', this.getCell(x, y));
}
println('|');
}
println(' +-+-+-+-+-+-+-+-+');
}
clone() {
let newBoard = new Board();
for (let y=0; y<8; y++) {
for (let x=0; x<8; x++) {
newBoard.setCell(x, y, this.getCell(x, y));
}
}
return newBoard;
}
getHistory() {
return this.history;
}
getBoardHistory() {
return this.boardHistory;
}
}
const StateInit = 0;
const StateBlackTurn = 1;
const StateWhiteTurn = 2;
const StateBlackJudge = 3;
const StateWhiteJudge = 4;
const StateBlackWin = 5;
const StateWhiteWin = 6;
const StateDrawGame = 7;
const StateExit = 8;
const StateError = 9;
const EventStart = 0;
const EventStop = 1;
const EventPut = 2;
const EventBlackTurn = 3;
const EventWhiteTurn = 4;
const EventBlackAgain = 5;
const EventWhiteAgain = 6;
const EventBlackSkip = 7;
const EventWhiteSkip = 8;
const EventBlackWin = 9;
const EventWhiteWin = 10;
const EventDrawGame = 11;
const EventExit = 12;
let stateNames = [];
stateNames[StateInit] = "Init";
stateNames[StateBlackTurn] = "BlackTurn";
stateNames[StateWhiteTurn] = "WhiteTurn";
stateNames[StateBlackJudge] = "BlackJudge";
stateNames[StateWhiteJudge] = "WhiteJudge";
stateNames[StateBlackWin] = "BlackWin";
stateNames[StateWhiteWin] = "WhiteWin";
stateNames[StateDrawGame] = "DrawGame";
stateNames[StateExit] = "Exit";
stateNames[StateError] = "Error";
let eventNames = [];
eventNames[EventStart] = "Start";
eventNames[EventStop] = "Stop";
eventNames[EventPut] = "Put";
eventNames[EventBlackTurn] = "BlackTurn";
eventNames[EventWhiteTurn] = "WhiteTurn";
eventNames[EventBlackAgain] = "BlackAgain";
eventNames[EventWhiteAgain] = "WhiteAgain";
eventNames[EventBlackSkip] = "BlackSkip";
eventNames[EventWhiteSkip] = "WhiteSkip";
eventNames[EventBlackWin] = "BlackWin";
eventNames[EventWhiteWin] = "WhiteWin";
eventNames[EventDrawGame] = "DrawGame";
eventNames[EventExit] = "Exit";
function getEventName(ev) {
if (ev[1]) {
return eventNames[ev[0]] + "(" + ev[1][0] + "," + ev[1][1] + ")";
} else {
return eventNames[ev[0]];
}
}
let Transitions = [];
Transitions[StateInit] = [];
Transitions[StateBlackTurn] = [];
Transitions[StateWhiteTurn] = [];
Transitions[StateBlackJudge] = [];
Transitions[StateWhiteJudge] = [];
Transitions[StateBlackWin] = [];
Transitions[StateWhiteWin] = [];
Transitions[StateDrawGame] = [];
Transitions[StateExit] = [];
Transitions[StateError] = [];
Transitions[StateInit][EventStart] = StateBlackTurn;
Transitions[StateInit][EventStop] = StateInit;
Transitions[StateInit][EventPut] = StateError;
Transitions[StateInit][EventBlackTurn] = StateError;
Transitions[StateInit][EventWhiteTurn] = StateError;
Transitions[StateInit][EventBlackAgain] = StateError;
Transitions[StateInit][EventWhiteAgain] = StateError;
Transitions[StateInit][EventBlackSkip] = StateError;
Transitions[StateInit][EventWhiteSkip] = StateError;
Transitions[StateInit][EventBlackWin] = StateError;
Transitions[StateInit][EventWhiteWin] = StateError;
Transitions[StateInit][EventDrawGame] = StateError;
Transitions[StateInit][EventExit] = StateExit;
Transitions[StateBlackTurn][EventStart] = StateError;
Transitions[StateBlackTurn][EventStop] = StateInit;
Transitions[StateBlackTurn][EventPut] = StateBlackJudge;
Transitions[StateBlackTurn][EventBlackTurn] = StateError;
Transitions[StateBlackTurn][EventWhiteTurn] = StateError;
Transitions[StateBlackTurn][EventBlackAgain] = StateError;
Transitions[StateBlackTurn][EventWhiteAgain] = StateError;
Transitions[StateBlackTurn][EventBlackSkip] = StateError;
Transitions[StateBlackTurn][EventWhiteSkip] = StateError;
Transitions[StateBlackTurn][EventBlackWin] = StateError;
Transitions[StateBlackTurn][EventWhiteWin] = StateError;
Transitions[StateBlackTurn][EventDrawGame] = StateError;
Transitions[StateBlackTurn][EventExit] = StateExit;
Transitions[StateWhiteTurn][EventStart] = StateError;
Transitions[StateWhiteTurn][EventStop] = StateInit;
Transitions[StateWhiteTurn][EventPut] = StateWhiteJudge;
Transitions[StateWhiteTurn][EventBlackTurn] = StateError;
Transitions[StateWhiteTurn][EventWhiteTurn] = StateError;
Transitions[StateWhiteTurn][EventBlackAgain] = StateError;
Transitions[StateWhiteTurn][EventWhiteAgain] = StateError;
Transitions[StateWhiteTurn][EventBlackSkip] = StateError;
Transitions[StateWhiteTurn][EventWhiteSkip] = StateError;
Transitions[StateWhiteTurn][EventBlackWin] = StateError;
Transitions[StateWhiteTurn][EventWhiteWin] = StateError;
Transitions[StateWhiteTurn][EventDrawGame] = StateError;
Transitions[StateWhiteTurn][EventExit] = StateExit;
Transitions[StateBlackJudge][EventStart] = StateError;
Transitions[StateBlackJudge][EventStop] = StateInit;
Transitions[StateBlackJudge][EventPut] = StateError;
Transitions[StateBlackJudge][EventBlackTurn] = StateError;
Transitions[StateBlackJudge][EventWhiteTurn] = StateWhiteTurn;
Transitions[StateBlackJudge][EventBlackAgain] = StateBlackTurn;
Transitions[StateBlackJudge][EventWhiteAgain] = StateError;
Transitions[StateBlackJudge][EventBlackSkip] = StateError;
Transitions[StateBlackJudge][EventWhiteSkip] = StateBlackTurn;
Transitions[StateBlackJudge][EventBlackWin] = StateBlackWin;
Transitions[StateBlackJudge][EventWhiteWin] = StateWhiteWin;
Transitions[StateBlackJudge][EventDrawGame] = StateDrawGame;
Transitions[StateBlackJudge][EventExit] = StateExit;
Transitions[StateWhiteJudge][EventStart] = StateError;
Transitions[StateWhiteJudge][EventStop] = StateInit;
Transitions[StateWhiteJudge][EventPut] = StateError;
Transitions[StateWhiteJudge][EventBlackTurn] = StateBlackTurn;
Transitions[StateWhiteJudge][EventWhiteTurn] = StateError;
Transitions[StateWhiteJudge][EventBlackAgain] = StateError;
Transitions[StateWhiteJudge][EventWhiteAgain] = StateWhiteTurn;
Transitions[StateWhiteJudge][EventBlackSkip] = StateWhiteTurn;
Transitions[StateWhiteJudge][EventWhiteSkip] = StateError;
Transitions[StateWhiteJudge][EventBlackWin] = StateBlackWin;
Transitions[StateWhiteJudge][EventWhiteWin] = StateWhiteWin;
Transitions[StateWhiteJudge][EventDrawGame] = StateDrawGame;
Transitions[StateWhiteJudge][EventExit] = StateExit;
Transitions[StateBlackWin][EventStart] = StateError;
Transitions[StateBlackWin][EventStop] = StateInit;
Transitions[StateBlackWin][EventPut] = StateError;
Transitions[StateBlackWin][EventBlackTurn] = StateError;
Transitions[StateBlackWin][EventWhiteTurn] = StateError;
Transitions[StateBlackWin][EventBlackAgain] = StateError;
Transitions[StateBlackWin][EventWhiteAgain] = StateError;
Transitions[StateBlackWin][EventBlackSkip] = StateError;
Transitions[StateBlackWin][EventWhiteSkip] = StateError;
Transitions[StateBlackWin][EventBlackWin] = StateError;
Transitions[StateBlackWin][EventWhiteWin] = StateError;
Transitions[StateBlackWin][EventDrawGame] = StateError;
Transitions[StateBlackWin][EventExit] = StateExit;
Transitions[StateWhiteWin][EventStart] = StateError;
Transitions[StateWhiteWin][EventStop] = StateInit;
Transitions[StateWhiteWin][EventPut] = StateError;
Transitions[StateWhiteWin][EventBlackTurn] = StateError;
Transitions[StateWhiteWin][EventWhiteTurn] = StateError;
Transitions[StateWhiteWin][EventBlackAgain] = StateError;
Transitions[StateWhiteWin][EventWhiteAgain] = StateError;
Transitions[StateWhiteWin][EventBlackSkip] = StateError;
Transitions[StateWhiteWin][EventWhiteSkip] = StateError;
Transitions[StateWhiteWin][EventBlackWin] = StateError;
Transitions[StateWhiteWin][EventWhiteWin] = StateError;
Transitions[StateWhiteWin][EventDrawGame] = StateError;
Transitions[StateWhiteWin][EventExit] = StateExit;
Transitions[StateDrawGame][EventStart] = StateError;
Transitions[StateDrawGame][EventStop] = StateInit;
Transitions[StateDrawGame][EventPut] = StateError;
Transitions[StateDrawGame][EventBlackTurn] = StateError;
Transitions[StateDrawGame][EventWhiteTurn] = StateError;
Transitions[StateDrawGame][EventBlackAgain] = StateError;
Transitions[StateDrawGame][EventWhiteAgain] = StateError;
Transitions[StateDrawGame][EventBlackSkip] = StateError;
Transitions[StateDrawGame][EventWhiteSkip] = StateError;
Transitions[StateDrawGame][EventBlackWin] = StateError;
Transitions[StateDrawGame][EventWhiteWin] = StateError;
Transitions[StateDrawGame][EventDrawGame] = StateError;
Transitions[StateDrawGame][EventExit] = StateExit;
Transitions[StateError][EventStart] = StateError;
Transitions[StateError][EventStop] = StateInit;
Transitions[StateError][EventPut] = StateError;
Transitions[StateError][EventBlackTurn] = StateError;
Transitions[StateError][EventWhiteTurn] = StateError;
Transitions[StateError][EventBlackAgain] = StateError;
Transitions[StateError][EventWhiteAgain] = StateError;
Transitions[StateError][EventBlackSkip] = StateError;
Transitions[StateError][EventWhiteSkip] = StateError;
Transitions[StateError][EventBlackWin] = StateError;
Transitions[StateError][EventWhiteWin] = StateError;
Transitions[StateError][EventDrawGame] = StateError;
Transitions[StateError][EventExit] = StateExit;
Transitions[StateExit][EventStart] = StateExit;
Transitions[StateExit][EventStop] = StateExit;
Transitions[StateExit][EventPut] = StateExit;
Transitions[StateExit][EventBlackTurn] = StateExit;
Transitions[StateExit][EventWhiteTurn] = StateExit;
Transitions[StateExit][EventBlackAgain] = StateExit;
Transitions[StateExit][EventWhiteAgain] = StateExit;
Transitions[StateExit][EventBlackSkip] = StateExit;
Transitions[StateExit][EventWhiteSkip] = StateExit;
Transitions[StateExit][EventBlackWin] = StateExit;
Transitions[StateExit][EventWhiteWin] = StateExit;
Transitions[StateExit][EventDrawGame] = StateExit;
Transitions[StateExit][EventExit] = StateExit;
let EnterFuncs = [];
let state;
let events = [];
let board;
function sendEvent(ev, value) {
events.push([ev, value]);
}
function getEvent() {
return events.shift();
}
function processEvents() {
for (let ev = getEvent(); ev != undefined; ev = getEvent()) {
let prevState = state;
state = Transitions[state][ev[0]];
println("State: " + stateNames[prevState] + " --[" + getEventName(ev) + "]--> " + stateNames[state]);
EnterFuncs[state](ev[0], ev[1]);
}
}
EnterFuncs[StateInit] = function(ev, value) {
board = new Board(true);
};
function findNextPut(selfColor, otherColor) {
let count = board.countCell(selfColor);
let nextPut = null;
for (let curPut of board.getCandidates(selfColor, otherColor)) {
let b = board.clone();
b.put(curPut[0], curPut[1], selfColor, otherColor);
if (b.countCell(selfColor) > count) {
count = b.countCell(selfColor);
nextPut = curPut;
}
}
return nextPut;
}
EnterFuncs[StateBlackTurn] = function(ev, value) {
board.printBoard();
println("Black turn: ");
// sendEvent(EventPut, findNextPut(board.black, board.white));
};
EnterFuncs[StateWhiteTurn] = function(ev, value) {
board.printBoard();
println("White turn: ");
// sendEvent(EventPut, findNextPut(board.white, board.black));
};
EnterFuncs[StateBlackJudge] = function(ev, value) {
if (ev != EventPut) {
return;
}
let x = value[0];
let y = value[1];
if (!board.canPutBlack(x, y)) {
sendEvent(EventBlackAgain);
return;
}
board.putBlack(x, y);
if (board.isFinished()) {
if (board.countBlack() > board.countWhite()) {
sendEvent(EventBlackWin);
} else if (board.countBlack() < board.countWhite()) {
sendEvent(EventWhiteWin);
} else {
sendEvent(EventDrawGame);
}
return;
}
if (board.existsCandidatesWhite()) {
sendEvent(EventWhiteTurn);
} else {
sendEvent(EventWhiteSkip);
}
};
EnterFuncs[StateWhiteJudge] = function(ev, value) {
if (ev != EventPut) {
return;
}
let x = value[0];
let y = value[1];
if (!board.canPutWhite(x, y)) {
sendEvent(EventWhiteAgain);
return;
}
board.putWhite(x, y);
if (board.isFinished()) {
if (board.countBlack() > board.countWhite()) {
sendEvent(EventBlackWin);
} else if (board.countBlack() < board.countWhite()) {
sendEvent(EventWhiteWin);
} else {
sendEvent(EventDrawGame);
}
return;
}
if (board.existsCandidatesBlack()) {
sendEvent(EventBlackTurn);
} else {
sendEvent(EventBlackSkip);
}
};
EnterFuncs[StateWhiteWin] = function(ev, value) {
board.printBoard();
println("White Win!");
println("Black: " + board.countBlack());
println("White: " + board.countWhite());
};
EnterFuncs[StateBlackWin] = function(ev, value) {
board.printBoard();
println("Black Win!");
println("Black: " + board.countBlack());
println("White: " + board.countWhite());
};
EnterFuncs[StateDrawGame] = function(ev, value) {
board.printBoard();
println("Draw Game!");
println("Black: " + board.countBlack());
println("White: " + board.countWhite());
};
EnterFuncs[StateExit] = function(ev, value) {
println("Exit");
process.exit(0);
};
EnterFuncs[StateError] = function(ev, value) {
println("Error");
};
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
function showCommands() {
console.log("Commands");
console.log(" help : Show help message");
console.log(" state : Show the current state");
console.log(" board : Show the current board");
console.log(" history : Show history of the current game");
console.log(" count : Show counts of black and white");
console.log(" moves : Show the candidate places of the current turn");
console.log(" start : Start new game");
console.log(" stop : Stop the current game");
console.log(" X Y : Place a piece at (X, Y) (0 <= X <= 7, 0 <= Y <= y)");
console.log(" exit : Exit");
}
rl.on('line', (line) => {
setTimeout(processEvents, 0);
line = line.trim();
if (line == '') {
board.printBoard();
return;
}
if (line == 'help') {
showCommands();
return;
}
if (line == 'state') {
console.log(stateNames[state]);
return;
}
if (line == 'board') {
board.printBoard();
return;
}
if (line == 'history') {
for (let b of board.getBoardHistory()) {
b.printBoard();
}
console.log(board.getHistory());
return;
}
if (line == 'count') {
console.log("Black: " + board.countBlack());
console.log("White: " + board.countWhite());
return;
}
if (line == 'moves') {
switch (state) {
case StateBlackTurn:
console.log(board.getCandidatesBlack());
return;
case StateWhiteTurn:
console.log(board.getCandidatesWhite());
return;
default:
console.log("no moves");
return;
}
}
if (line == 'start') {
sendEvent(EventStart);
return;
}
if (line == 'stop') {
sendEvent(EventStop);
return;
}
if (line == 'exit') {
sendEvent(EventExit);
return;
}
line = line.replace(/ +/g, ' ');
let words = line.split(' ');
if (words.length != 2) {
console.log("Invalid input: " + line);
return;
}
let x = parseInt(words[0]);
let y = parseInt(words[1]);
if (Number.isNaN(x) || Number.isNaN(y)) {
console.log("Invalid input: " + line);
return;
}
let input = [x,y];
sendEvent(EventPut, [x,y]);
});
function startStateMachine() {
state = StateInit;
EnterFuncs[StateInit]();
setTimeout(processEvents, 0);
}
startStateMachine();
showCommands();
/*
function find_board(count) {
startStateMachine();
sendEvent(EventStart);
processEvents();
while (state == StateBlackTurn || state == StateWhiteTurn) {
let places = [];
switch (state) {
case StateBlackTurn: places = board.getCandidatesBlack(); break;
case StateWhiteTurn: places = board.getCandidatesWhite(); break;
default: places = []; break;
}
if (places.length != 0) {
let index = Math.floor(Math.random() * places.length);
let chosen = places[index];
sendEvent(EventPut, chosen);
}
processEvents();
}
if (board.countBlack() + board.countWhite() <= (64 - count)) {
console.log(board.getHistory());
process.exit(0);
}
}
setInterval(find_board, 0, 1);
*/
/*
History for a Diamond:
[ 2, 3, '*' ]
[ 4, 2, 'o' ]
[ 5, 3, '*' ]
[ 2, 4, 'o' ]
[ 3, 5, '*' ]
[ 2, 2, 'o' ]
[ 1, 3, '*' ]
[ 3, 2, 'o' ]
[ 3, 1, '*' ]
sendEvent(EventStart);
sendEvent(EventPut, [2,3]); processEvents();
sendEvent(EventPut, [4,2]); processEvents();
sendEvent(EventPut, [5,3]); processEvents();
sendEvent(EventPut, [2,4]); processEvents();
sendEvent(EventPut, [3,5]); processEvents();
sendEvent(EventPut, [2,2]); processEvents();
sendEvent(EventPut, [1,3]); processEvents();
sendEvent(EventPut, [3,2]); processEvents();
sendEvent(EventPut, [3,1]); processEvents();
process.exit(0);
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment