"Strategic victory in a board game - employing an advanced search algorithm

Currently seeking an efficient algorithm to detect a "win" situation in a gomoku (five-in-a-row) game played on a 19x19 board. A win occurs when a player successfully aligns five, and ONLY five, "stones" in a row (horizontally, diagonally, or vertically).

I have easy access to the following data:

  • Previously made moves ("stones") of both players are stored in a 2D array (which can also be represented as a JSON object) with variables "B" and "W" to differentiate between players.
  • The "coordinates" of the next move (move.x, move.y).
  • The number of moves each player has made.

I am using JavaScript for this task, but any solution that avoids low-level operations like memory allocation and does not rely on higher-level array operations such as Python would be preferable.

I came across a similar question (Detect winning game in nought and crosses), but the solutions provided there are only suitable for small boards like 5x5.

Answer №1

Providing a straightforward solution without extensive loops (only presenting pseudocode, feel free to request further clarification):

If we assume the 2-dimensional array is structured as follows:

board = [
   [...],
   [...],
   [...],
   ...
];

In this arrangement, the inner arrays represent the horizontal rows of the board.

We can also assume that the array comprises of "b", "w", and "x", denoting black pieces, white pieces, and empty squares, respectively.

My approach involves somewhat of a divide-and-conquer strategy, categorized into the three scenarios below. Although it may initially appear more intricate than utilizing nested loops, the underlying concept is straightforward, comprehensible, and ultimately simplistic to code.

Horizontal lines

To begin with, let's address identifying a win scenario only when the line is horizontal - which is the simplest case. Initially, concatenate a row into a single string using something like board[0].join(""). Proceed with this process for each row. This results in an array structure such as:

rows = [
   "bxwwwbx...",
   "xxxwbxx...",
   "wwbbbbx...",
   ...
]

Next, merge THIS array while inserting an "x" between elements to separate each row: rows.join("x").

Now you possess a comprehensive string representing your board, making it effortless to apply a regexp search for consecutive "w" or "b" characters precisely five units long:

superString.test(/(b{5,5})|(w{5,5})/)
. Upon receiving a true outcome, a win situation is detected. If not, proceed to vertical lines.

Vertical lines

To reuse the above code, establish a function testRows for this purpose. The procedure for testing vertical lines mirrors that of horizontal detection. However, it necessitates transposing the board so that rows are transformed into columns and vice versa. Subsequently, apply the identical testRows function. This transposition can be executed by duplicating values into a new 2-dimensional array or devising a simple getCol function and integrating it within testRows.

Diagonal lines

Similarly, we aim to reuse the 'testRows' function. A diagonal configuration like the one depicted:

b x x x x
x b x x x
x x b x x
x x x b x
x x x x b

Can be converted into a vertical setup as illustrated:

b x x x x
b x x x
b x x
b x
b

This transformation involves shifting row i by i positions. Following this alteration, transpose the matrix and resume testing for horizontals. Comparable adjustments need to occur for diagonals progressing in the opposite direction, where row i should shift by length - 1 - i positions, or in this context, 18 - i locations.

Functional javascript

On a supplementary note, my solution seamlessly aligns with functional programming, enabling a relatively straightforward implementation provided you have functional programming tools on hand, although they are not mandatory. I suggest considering the utilization of underscore.js, as basic functionalities such as map, reduce, and filter are frequently required across various game algorithms. For instance, the segment pertaining to testing horizontal lines could be condensed into a single line of javascript employing the map method:

_(board).map(function (row) {return row.join("")}).join("x").test(/(b{5,5})|(w{5,5})/);

Answer №2

Even though this question is quite dated, I feel compelled to share my solution as I recently delved into it and found a much more efficient method of solving the problem.

I've implemented a bit board, commonly used in board games and engines like chess engines, to represent the field due to its efficiency.

All necessary operations in this game can be performed with bitwise operations.

Since bits only have 2 states (0 and 1) while we require 3 states (player 1, player 2, or empty), we opt for using 2 separate boards, one for each player.

The large size of Gomoku's field (19x19) presents another challenge; no number type has enough bits to represent every cell. Instead, we use an array of numbers to represent each line, utilizing only the first least significant bits.

Vertical Rows

A simplified representation of player 1's board might look like:

000000
101100
001000
011000
000000

If we want to detect a sequence of 3 in a row, we examine the first 3 rows (0-2).

000000
001100
101000

By applying the & (AND) operator, we can determine if there is a '1' in every row.

var result = field[player][0] & field[player][1] & field[player][2];

In this example, the result would be 0 indicating no winner. Moving on to rows 1-3:

101100
001000
011000

Performing the AND operation yields 001000. The specific number isn't relevant; all that matters is whether it's zero or not (result != 0).

Horizontal Rows

We have successfully detected vertical rows. To identify horizontal rows, we create two additional boards—one per player—with inverted x and y axes. Applying the same check facilitates the detection of horizontal lines, expanding the array to include:

//[player][hORv][rows]
var field[2][2][19];

Diagonals :)

The most challenging aspect involves diagonal lines, but employing a simple trick allows us to apply the same logic. Consider the following board:

000000
010000
001000
000100
000000

Similarly to before, shifting the rows enables us to assess a win along the diagonals. Shifting the second row by one position left and the third row by two positions left:

var r0 = field[0][0][i];
var r1 = field[0][0][i+1] << 1;
var r2 = field[0][0][i+2] << 2;

This results in:

010000
010000
010000

Applying the AND operation at this point allows for win detection. Repeat the process for the opposite diagonal direction, this time shifting right (>>).

I hope this explanation proves beneficial to someone out there.

Answer №3

untested strategy for checking game board:

int startColumn = max(0, move.x-5), endColumn = min(width-1, move.x+5), startRow = max(0, move.y-5), endRow = min(width-1, move.y+5);    
// examining primary diagonal (top-left to bottom-right)
for (int x = startColumn, y = startRow; x <= endColumn && y <= endRow; x++, y++) {
    for (int count = 0; x <= endColumn && y <= endRow && stones[x][y] == lastPlayer; x++, y++, count++) {
        if (count >= 5) return true;
    }
}
// examining secondary diagonal
// ...
// examining horizontally
// ...
// examining vertically
// ...
return false;

an alternative approach without nested loops:

// examine the primary diagonal (top-left to bottom-right)
int count = 0, maxCount = 0;
for (int x = startColumn, y = startRow; x <= endColumn && y <= endRow; x++, y++) {
    if (count < 5) {
        count = stones[x][y] == lastPlayer ? count + 1 : 0;
    } else {
        return true;
    }
}

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Searching through an array of objects that contain nested child objects

I am currently trying to find a way to search through an Array that has nested Objects in order to find a specific value and then retrieve the object in which it is found to store it in a new array. This is the code snippet I am working with: var json = ...

Tips for effectively recycling the describe sections in mocha test cases

My app has different modes, each with its own loading times and configurations. One particular mode has a long loading period every time a page is opened which is causing some testing challenges. Currently, I have separate test files for each section of th ...

Implementing dynamic keys in a JSON data structure with Node.js

Specifically focused on utilizing Node.js ES6 capabilities. I am currently working on creating a JSON document for insertion into a MongoDB database. The keys for inserting the document will be derived from the input values provided. For instance, Here i ...

Obtain the unique identifier for every row in a table using jQuery

Apologies for not including any code, but I am seeking guidance on how to use an each() statement to display the ID of each TR element. $( document ).ready(function() { /* Will display each TR's ID from #theTable */ }); <script src="https:// ...

The TypeScript factory design pattern is throwing an error stating that the property does not

While working with TypeScript, I encountered an issue when trying to implement the factory pattern. Specifically, I am unable to access child functions that do not exist in the super class without encountering a compiler error. Here is the structure of my ...

What is causing the ng-show function to malfunction after building with phonegap?

My current javascript framework for my PhoneGap app is the Ionic Framework. I have a specific item on one of my pages that I want to make expandable and collapsible by clicking an anchor on the page. Here is what the code looks like: In the HTML file: & ...

The functionality of TypeScript's .entries() method is not available for the type 'DOMTokenList'

I'm currently working with a stack that includes Vue3, Vite, and TypeScript. I've encountered an issue related to DOMTokenList where I'm trying to utilize the .entries() method but TypeScript throws an error saying Property 'entries&apo ...

Whenever I attempt to generate a forecast utilizing a tensorflow.js model, I encounter the following error message: "Uncaught TypeError: Cannot read property 'length' of undefined."

I'm currently working on a project to build a website that utilizes a deep learning model for real-time sentiment analysis. However, I've encountered an issue when using the model.predict() function. It throws an error message: Uncaught TypeErro ...

Monitoring variables in different AngularJS controllers

I have a component named histogram demo which includes a distinct controller with a variable known as $scope.selectedElements. I aim to monitor this variable in the primary appCtrl controller. How can I achieve access to this variable without using $rootSc ...

Is there a way to retrieve data from a sealed JSON object using JavaScript?

The data is being fetched from the API and here is the response object: { "abc": [{ "xyz": "INFO 1", "pqr": "INFO 2" }, { "xyz": "INFO 3", "pqr": "INFO 4" } ] } We are lookin ...

Converting a nested tree array into a hierarchical CSV using PHP

I'm faced with a tree structure array of departments that I need to flatten into a CSV format, displaying the full path to each end department. Consider this example array: $arr = array("AA" => ["BB" => [], "CC" => ["DD" => [], "EE" => ...

Arranging squares in a circular formation with Three.js

I am facing an issue with aligning squares within a circular grid to its center. Despite the correct center point, the entire grid is consistently skewed to the right. The problem could be due to incorrect calculations for removing squares outside the cir ...

Capture the item selected from the dropdown using ng-model to retrieve the name instead of the

I need help getting the name/text/html of the selected option in a dropdown using angular.js, rather than just its value. Currently, I have this setup which retrieves the value: Here is my HTML code snippet <select class="SelectCar" ng-model="Selected ...

Is it possible to develop a web-based chat application using socket.io without the need for ssh access or having to keep the terminal

I have been using php to develop my website. Up until now, I have relied on setTimeout with ajax for updating chats simultaneously. However, when this method stopped working, I discovered socket.io. My goal is to implement private messaging, and while I ha ...

Import data into Bootstrap table from an external source

I am having trouble styling the table loaded from the table.html file onto the index page. Even after loading the table, the styles from bootstrap classes are not applied. What could be causing this issue? Importing bootstrap libraries directly into the ta ...

Automated Recommendation Selector

I'm searching for a JavaScript library that can provide the following functionalities: An auto-suggest dropdown list that uses Ajax to retrieve results from a database. Restricting the user to only select values provided by the Ajax call. Abilit ...

What is the best way to display converted value in Angular 8?

In my current project, I am utilizing .NET Core 2.2 for the backend and Angular 8 for the frontend. The scenario involves having integer values on the backend within a specified range. For example: [Required] [Range(1073741824, 1099511627776)] // ...

What is the best way to trigger a tooltip when an input field is clicked?

I want to implement a form that displays tooltips whenever a user clicks or focuses on an input field, and the tooltip should disappear when the user clicks elsewhere. While I understand the basics of using JavaScript's getElementById and click event ...

Retrieve information from a URL using an Express API

Every 45 minutes, my API receives a request: GET http://MyHost/mediciones/sigfox_libelium/{device}/{data}/{time}/{customData#trama} I need to extract {device}, {data}, {time}, and {customData#trama} from the URL and store them in separate variables. This ...

Incorporate various style components to enhance the appearance of an item in ExtJS

I'm attempting to add ellipsis to an item created by ExtJS. My goal is to only modify this item without adding any additional CSS files. After researching, I discovered there is a "style" parameter that accepts CSS styles and attempted the following: ...