Home | All Fwiends | Random | Online | Music | Blog | Search

Uff

"You're a spineless liberal!"

Gender Questioning
1 years old
Hong Kong
Last Login:
1614030429000
Song: against me! - baby i'm an anarchist (lyrics)-9gEvxw9XKzo

Uff is in your extended network

Uff's Latest Blog Entry
Dinkelhuber [view more]
Proof Number Qango [view more]
Uff's blurbs

About me:

Visit a random profile
.
Visit yannikkeller.de

GABOR

What is GABOR?

GrAph Based bOard game solveR (GABOR) is a solving algorithm/program for a class of board games. That class is board games, where 2 players take alternating turns occupying squares. A player wins, if he manages to occupy all squares of a specific pattern. Real-world examples for this type of game are tic tac toe, Qango or Go-Moku. GABOR can, without modifications, deal with any game of this class, no matter the shape of the board or the layout of the winpatterns.

Why would you want to use GABOR?

On http://python.yannikkeller.de/solver/, you can find a community platform for sharing and exploring games and solutions created by GABOR. If you just want to see some of GABORs findings without installing anything, you should probably head over there. However, to start solving your own games, you will have to install GABOR on your computer. You can then head back to http://python.yannikkeller.de/solver/ and share your computed solutions with the world.

Installation

Installation instructions are for linux systems. You should also be able to get it to work on Windows or MacOS using the installation instructions for graph-tool.

Requirements: python3.8+, graph-tool, flask, flask-socketio, psutil
GABOR depends on graph-tool, which is easiest installed via conda. If you have conda ready, you can install from environment.yml via conda env create -f environment.yml. Activate the env via conda activate GABOR

If the install from environment.yml fails, you can try installing manually with the commands
conda install -c conda-forge graph-tool
conda activate gt
pip install flask flask_socketio psutil

Usage

Run export FLASK_APP=flask_server.py;flask run from the projects root. Head over to localhost:5000 in your favorite browser. To start solving a game, click the on a Analyze link and then Solve game for black/white. GABOR performs binary game evaluation, so when solving for black, you are checking if the game is won for black or not (White wins or draw). To fully solve a game, you will need to try and solve for black as well as for white.

Why Graph Based?

GABOR transforms any board game into a graph. Each winpattern will be a vertex and each square will be a vertex. Squares that are part of a winpattern share an edge with that winpattern. When a player occupies a square, that square will be removed from the graph and any connected winpattern vertex will be colored in that players color. If the winpattern vertex was already in the players color and has no edges left, the player wins. If the winpattern was already colored in the opponents player color, the winpattern vertex is removed. Any square vertex left without edges as a result is removed.

That way of representing the board game has the following advantages:

  • Uninteresting squares (Ones that correspond to no more winpatterns) are automatically removed
  • Heuristic move sorting is very easy (prefer square verticies, that are connected to to many winpattern verticies of low degree)
  • We can exploit graph isomorphisms to avoid computing theoretically equivalent positions multiple times. GABOR uses Weisfeiler-Lehman based graph hashing for that. We can even recognize and exploit inter-game isomorphisms. There might be endgames in one game, that are isomorphic to endgames in another game.
  • We can implement a general threat-space search algorithm (Threats are square verticies that are neighbours to a winpattern vertex of degree 2)

Algorithm

Inspired by the paper Go-Moku and Threat-Space Search, GABOR uses a combination of Proof-Number search and Threat-Space Search to solve games. A big advantage of GABORs graph representation are the transpositions/symetries/graph-isomorphisms. Thus, GABORs search structure is not a tree, as in the original Proof-Number search, but instead a directed acyclic graph (DAG). I used the practical algorithm described here to make PN-search work on my DAG. Also, GABOR's implementation of the threat-space is not specifically built for a single game, as in the original papers implementation, but exploits the graph structure to know what a threat is and what not.

Games solved using GABOR

To the best of my knowledge, GABOR is the first program to solve Qango, in all it's shapes and forms. You can view all proofs online at http://python.yannikkeller.de/solver/

Author

Yannik Keller

Who I'd like to meet:

The spectre of communism
https://i.imgur.com/Ddjs8R9.jpg

Uff's Fwiends Space
Uff has 160 fwiends.
View All Uff's Fwiends
Please login to leave a comment.
Comments
llilywebskateboarder
1608750883000

Earth anhel

kappablablaisweird
1606655710000

smells weird

Unknown Fox
1605478372000

e

kappablablaisweird
1605015887000

komm mal q liga

Marsie uwu
1600144427000

glitchcore sux lmao i hate glitchcore

Uff
1599081058000

Well, if it isn't Mr. Hotshot himself

Jaden Desmond
1599068584000

Jaden Desmond

Uff
1597275562000

My name is kayne west, and I approve of this message

kappablablaisweird
1596999089000

komm mal q liga

popbob
1596821268000

the oldest anarchy server in minecraft

kappablablaisweird
1596811193000

du Trollo

;)

MysteryMeatwad
1593869571000

They have.? Why? They do thatm Why? Don't do that!. That's not cool.

MysteryMeatwad
1591950884000

And the

redkyoin
1591367465000

I love that everything smells weird

angeleismywifey
1588572419000

LUXEMBURGISCH IST NUR EIN DEUTSCHER DIALEKT! LUXEMBURG EXISTIERT NICHT!

sad
1586214302000

maybe :/

sad
1586214349000

my 100th fwiend goes to......
volsuff (smells weird) :)

Zedd
1582911097000
Zedd
1582911061000
Bill
1582477717000

vollsuff

angeleismywifey
1582471255000

UND KRAUSE IST PROLEEEEEEEEEEEEEEEEEEEEEEEEEEET

Bill
1580780228000

Uff

zoe
1579061340000
Left 4 Dead
1579046847000

I meant to say Left 4 Dead 2! Silly me.

Left 4 Dead
1578956937000

Left 4 Dead 3

linda8bit
1576200163000

Thanx to your site I got into some super addicting doge clicker... that was evil xD

linda8bit
1576200062000
🌻Luar
1576110318000
Uff
1571873343000

Wait a minute, this isn‘t the bar. I gotta fire my assistant!

Russian Kid
1571676106000

и упражнение при реперандерите возбуждает в исключительном случае не купидон случайный случайный виноват дефекты торгового центра

Schnotty
1571523800000

Nice profile, thanks for sharing

Tila Tequila
1571467596000
dat boi
1571422288000
Janken Popp
1571334738000
Uff
1571331991000

Hey guyz, how doez this internet work???

(35/100)