Data

Tools

Indexes

Applications

Experiments

Open Source Science

knights_tour

https://github.com/shahafgev/knights_tour

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (7.9%) to scientific vocabulary
Last synced: 6 months ago · JSON representation ·

Repository

Basic Info
  • Host: GitHub
  • Owner: shahafgev
  • License: bsd-3-clause
  • Language: Python
  • Default Branch: master
  • Size: 545 KB
Statistics
  • Stars: 0
  • Watchers: 0
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created 8 months ago · Last pushed 8 months ago
Metadata Files
Readme License Citation

README.md

Deep Reinforcement Learning for the Knight's Tour with Graph Neural Networks

Project Overview

This project applies Deep Q-Learning (DQN) combined with Graph Neural Networks (GNNs) to solve the Knight's Tour problem on a chessboard. The Knight's Tour is a classic combinatorial problem where a knight must visit every square on the board exactly once. By modeling the board as a graph and leveraging GNNs, the agent learns to generalize move strategies across different board configurations.

Approach

  • Environment: The chessboard is represented as a graph, where each square is a node and edges represent valid knight moves. The environment is implemented as an OpenAI Gym environment (KnightTourEnv).
  • Agent: The agent uses a DQN architecture, where the Q-network is a GNN that processes the board's graph structure and outputs Q-values for each possible knight move.
  • Learning: The agent is trained via experience replay and periodically evaluated. The GNN enables the agent to learn spatial and structural patterns, improving generalization.

Directory Structure

  • DQN/train_DQN.py — Main training script for the DQN agent.
  • DQN/mpnn.py — GNN (Message Passing Neural Network) model definition.
  • DQN/gym-environments/gym_environments/envs/knight_tour_env.py — Knight's Tour Gym environment.
  • modelssample_DQN_agent/ — Directory for model checkpoints.

Setup Instructions

  1. Install dependencies:
    • Python 3.6+
    • Install required packages: bash pip install -r DQN/requirements.txt
  2. Install the custom Gym environment: bash cd DQN/gym-environments pip install -e . cd ../..
  3. (Optional) Set up Weights & Biases (wandb) for experiment tracking.

Running Training

To train the DQN agent on the Knight's Tour problem: bash python DQN/train_DQN.py

Evaluation

The script performs periodic evaluation during training. Model checkpoints are saved in modelssample_DQN_agent/.

Owner

  • Name: shahaf gev
  • Login: shahafgev
  • Kind: user
  • Location: israel

4th year Industrial Engineering and Management Student at BGU

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Almasan"
  given-names: "Paul"
  orcid: "https://orcid.org/0000-0003-3903-6759"
title: "Code of DRL+GNN architecture in OTN"
version: 1.0
date-released: 2021-11-22
url: "https://github.com/knowledgedefinednetworking/DRL-GNN"

GitHub Events

Total
  • Push event: 2
Last Year
  • Push event: 2

Dependencies

DQN/gym-environments/setup.py pypi
  • gym *
DQN/requirements.txt pypi
  • Keras-Preprocessing ==1.1.2
  • Markdown ==3.3.6
  • Pillow ==8.4.0
  • Werkzeug ==2.0.2
  • absl-py ==1.0.0
  • astunparse ==1.6.3
  • cachetools ==4.2.4
  • certifi ==2021.10.8
  • charset-normalizer ==2.0.7
  • cloudpickle ==2.0.0
  • cycler ==0.11.0
  • flatbuffers ==2.0
  • fonttools ==4.28.1
  • gast ==0.4.0
  • google-auth ==2.3.3
  • google-auth-oauthlib ==0.4.6
  • google-pasta ==0.2.0
  • grpcio ==1.42.0
  • gym ==0.21.0
  • h5py ==3.6.0
  • idna ==3.3
  • importlib-metadata ==4.8.2
  • keras ==2.7.0
  • kiwisolver ==1.3.2
  • libclang ==12.0.0
  • matplotlib ==3.5.0
  • networkx ==2.6.3
  • numpy ==1.21.4
  • oauthlib ==3.1.1
  • opt-einsum ==3.3.0
  • packaging ==21.3
  • protobuf ==3.19.1
  • pyasn1 ==0.4.8
  • pyasn1-modules ==0.2.8
  • pyparsing ==3.0.6
  • python-dateutil ==2.8.2
  • requests ==2.26.0
  • requests-oauthlib ==1.3.0
  • rsa ==4.7.2
  • scipy ==1.7.2
  • setuptools-scm ==6.3.2
  • six ==1.16.0
  • tensorboard ==2.7.0
  • tensorboard-data-server ==0.6.1
  • tensorboard-plugin-wit ==1.8.0
  • tensorflow ==2.7.0
  • tensorflow-estimator ==2.7.0
  • tensorflow-io-gcs-filesystem ==0.22.0
  • termcolor ==1.1.0
  • tomli ==1.2.2
  • typing-extensions ==4.0.0
  • urllib3 ==1.26.7
  • wrapt ==1.13.3
  • zipp ==3.6.0