VICTOR: An Arcane Connect Four AI using Ancient Knowledge from the 80s

Related tags

Command-line victor
Overview

VICTOR

VICTOR is a program based on 'A Knowledge-based Approach of Connect-Four' by Victor Allis. The original program written in C has been lost to history. This current implementation is written in Rust.

Purpose

VICTOR can evaluate a connect four position and decide if black can draw or win the game, or if white can win the game. It can be used as follows:

$ ./target/release/victor_rs full-eval 34444445
score: -1, number of nodes: 1

Here, a score of -1 means that black can draw ensure themselves at least a draw. The string of numbers 3444445 represents a connect four position.

$ ./target/release/victor_rs show 34444445
...●...
...○...
...●...
...○...
...●...
..●○○..
White to play

In this case, the white player goes first and puts a disc in the third column from the right, the black plays in column 4 and white plays on top, again in column 4. This is how the string of numbers is interpreted, as a back and forth game between the white and black player.

Architecture

VICTOR currently uses two evaluation phases, the knowledge evaluation and the conspiracy search. The paper first mentioned also described a depth first approach which is not yet implemented.

Knowledge Evaluation

The knowledge evaluation phase takes a position and tries to 'solve' it using strategic rules. These rules come in the form of guarantees for particular empty squares. Take the position which we started with:

...●...
...○...
...●...
...○...
...●...
..●○○..
White to play

Black can employ a rule called ClaimEven. Which makes use of the fact that when white makes a move, black can immediately follow up playing on top of white. This rule ensures that black can get the following squares:

xxx●xxx
...○...
xxx●xxx
...○...
xx.●.xx
..●○○..
White to play

If we now check take a look at all the possible connect-fours for white, we see that all of them at least use one square that is claimed by black. This means that given perfect play for black, white can't make a connect four. Meaning that this position evaluates to -1, black can draw this game.

In the paper there are more examples of strategic rules with formal definitions. It also shows how those rules can and can't be combined to solve an entire board. It should be noted that knowledge evaluation sometimes falls short, and can't solve a position. This introduces the next evaluation phase: Conspiracy search.

Conspiracy Search

Conspiracy search is a best-first tree search. It takes a position and if it can't be solved by the knowledge evaluation it generates all the possible positions that follow from it. Let's work through an example:

.......
.......
.......
.......
○○○....
●●●....
White to play

Here, It's very clear who is winning, but computers are not intelligent unless we make them. So we generate 7 new positions of which one is winning. After white sees that move is winning, white will play it and win. Making sure that the starting position evaluates to 1. If after just a singe expansion, no position is clearly winning, we have to expand the tree further. This happens recursively.

Conspiracy search dictates how we expand the tree, making sure that we visit promising variations first. Because of my limited understanding of conspiracy search, I cannot adequately explain how it works.

Depth Search

The paper being adapted describes a third evaluation phase, a depth first search, which is not yet implemented in the code base, so I'll refrain from explaining it here.

Shortfalls

There are a couple (many) things in this current code base that simply don't work at all or don't work as well as they should.

  • The SpecialBefore rule doesn't work, and is not included in the knowledge evaluation.
  • It's very likely that the threat combination rules don't fully work. As in, the knowledge evaluation should be able to handle more positions with a better threat combination implementation.
  • There's a non-zero chance that my implementation of conspiracy search is wrong. I ran it against an alpha-beta search and it had a higher node count by a factor of at least two. That seems very weird.
  • Optimization: The current implementation is slow, too slow. And it needs a lot of work. Mainly the knowledge evaluation can use a lot of work.
  • General refactoring. This code is made with the idea that it's save-able, so it can be turned into decent code without a complete rework. Currently, it is not yet decent code.

Intention

The original intention of this project was to make a faster connect four AI than the alpha-beta AI I previously made in Rust, following this highly recommended tutorial. That AI was able to evaluate the starting position in about 4.5 minutes on my laptop. The current AI is not capable of that, and needs some work.

I also intent to do some academic reproduction with this study. Because I believe that code should be included in scientific papers, to make it easier for other researcher to build on, and test that code.

These two goals can be at odds. Making the AI faster might involve removing the conspiracy search from the code, making it less of a historical reproduction. The simplest solution is to create a historic branch in the git repository.

Conclusion

I was once told that a piece of writing should include a conclusion. But I don't have one. If you want to work on this, it's very much appreciated and please contact me.

You might also like...
Pure-Rust rewrite of the Linux fontconfig library (no system dependencies) - using ttf-parser and allsorts

rust-fontconfig Pure-Rust rewrite of the Linux fontconfig library (no system dependencies) - using allsorts as a font parser in order to parse .woff,

A CLI tool that allow you to create a temporary new rust project using cargo with already installed dependencies
A CLI tool that allow you to create a temporary new rust project using cargo with already installed dependencies

cargo-temp A CLI tool that allow you to create a new rust project in a temporary directory with already installed dependencies. Install Requires Rust

Mini Rust CLI to deploy sites to Netlify using their API

This is a Rust CLI that uses the Netlify API to deploy sites.

Build terminal dashboards using ascii/ansi art and javascript
Build terminal dashboards using ascii/ansi art and javascript

blessed-contrib Build dashboards (or any other application) using ascii/ansi art and javascript. Friendly to terminals, ssh and developers.

`decaf377-rdsa` is a randomizable signature scheme using the `decaf377` group.

decaf377-rdsa is a variant of RedDSA, instantiated using the decaf377 group. Signatures are parameterized by domain (for instance, Binding and SpendAu

A few demos showing how to estimate projects using Monte Carlo simulations.

Agile Monte Carlo Simulations Demos This is the repository which accompanies the blog post "How to replace estimations and guesses with a Monte Carlo

A CLI tool for getting screenshots of URLs using headless chrome

rustywitness 🦀 🌐 📸 Web screenshot utility A CLI tool for getting screenshots of URLs using headless chrome Built with ❤︎ by swanandx and contributo

Shellcode Runner/Injector in Rust using NTDLL functions directly with the ntapi Library
Shellcode Runner/Injector in Rust using NTDLL functions directly with the ntapi Library

RustSCRunner Shellcode Runner/Injector in Rust using NTDLL functions directly with the ntapi Library. Surprisingly this is my first ever Rust project

Kit-kat clock utility rewritten in Rust using minifb
Kit-kat clock utility rewritten in Rust using minifb

kitkat clock in Rust This is the plan9 cat clock utility rewritten in rust with minifb crate. $ kitkat --help Usage: kitkat [--hook|--crazy|--offset O

Owner
null
An m,n,k-game with Connect Four rules

Description A simple m,n,k-game with Connect Four rules (i.e. every token must be placed in the lowest possible position). The size of the board (m *

Elias 3 Nov 21, 2023
AskBend: SQL-based Knowledge Base Search and Completion using Databend

AskBend: SQL-based Knowledge Base Search and Completion using Databend AskBend is a Rust project that utilizes the power of Databend and OpenAI to cre

Databend Labs 87 Apr 7, 2023
FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config.

Connect quickly to your services ?? FastSSH is a TUI that allows you to quickly connect to your services by navigating through your SSH config. Instal

Julien 85 Dec 14, 2022
A tool for collecting rollup blocks from the Aztec Connect rollup, and exporting them to csv

Aztec Connect Data Gobbler The Aztec Connect Data gobbler is a tool made for extracting data from the Aztec Connect system using only L1 as its source

Lasse Herskind 6 Feb 17, 2023
A visual canvas and virtual machine for writing assembly to build cool things. Create machines and connect them together.

Visual Assembly Canvas A highly visual assembly editor, infinite canvas for wiring blocks and machines together, bytecode virtual machine runnable nat

Phoomparin Mano 31 Oct 11, 2023
A visual canvas and virtual machine for writing assembly to build cool things. Create machines and connect them together.

Visual Assembly Canvas A highly visual assembly editor, infinite canvas for wiring blocks and machines together, bytecode virtual machine runnable nat

Phoomparin Mano 32 Oct 11, 2023
Python/Rust implementations and notes from Proofs Arguments and Zero Knowledge study group

What is this? This is where I'll be collecting resources related to the Study Group on Dr. Justin Thaler's Proofs Arguments And Zero Knowledge Book. T

Thor 65 Dec 16, 2022
An ebpf knowledge base, based on llama_index and bpf-developer-tutorial

ebpf-knowledge-base An ebpf knowledge base, based on llama_index and bpf-developer-tutorial Usage First, you need to clone this repo: git clone --recu

eunomia-bpf 7 Apr 1, 2023
Using BDK from nodejs using WASM webpack 🦀

BDK + nodejs = ❤️ This repository shows how to use the bdk library in nodejs. It's just a proof-of-concept, not a complete example, and as such, it's

Daniela Brozzoni 10 Feb 21, 2023
Build terminal user interfaces and dashboards using Rust

tui-rs tui-rs is a Rust library to build rich terminal user interfaces and dashboards. It is heavily inspired by the Javascript library blessed-contri

Florian Dehau 9.3k Jan 4, 2023