import 'package:flutter_test/flutter_test.dart';
import 'package:dartmcts/dartmcts.dart';
void main() {
  test('adds one to input values', () {
    final calculator = Calculator();
    expect(calculator.addOne(2), 3);
    expect(calculator.addOne(-7), -6);
    expect(calculator.addOne(0), 1);
    expect(() => calculator.addOne(null), throwsNoSuchMethodError);
  });
}

name: dartmcts
description: A new Flutter package project.
version: 0.0.1
author:
homepage:
environment:
  sdk: ">=2.7.0 <3.0.0"
dependencies:
  flutter:
    sdk: flutter
dev_dependencies:
  flutter_test:
    sdk: flutter
  dataclass_generator: ^0.3.0+2
  build_runner: ^1.7.0
# For information on the generic Dart part of this file, see the
# following page: https://dart.dev/tools/pub/pubspec
# The following section is specific to Flutter.
flutter:
  # To add assets to your package, add an assets section, like this:
  # assets:
  #   - images/a_dot_burr.jpeg
  #   - images/a_dot_ham.jpeg
  #
  # For details regarding assets in packages, see
  # https://flutter.dev/assets-and-images/#from-packages
  #
  # An image asset can refer to one or more resolution-specific "variants", see
  # https://flutter.dev/assets-and-images/#resolution-aware.
  # To add custom fonts to your package, add a fonts section here,
  # in this "flutter" section. Each entry in this list should have a
  # "family" key with the font family name, and a "fonts" key with a
  # list giving the asset and other descriptors for the font. For
  # example:
  # fonts:
  #   - family: Schyler
  #     fonts:
  #       - asset: fonts/Schyler-Regular.ttf
  #       - asset: fonts/Schyler-Italic.ttf
  #         style: italic
  #   - family: Trajan Pro
  #     fonts:
  #       - asset: fonts/TrajanPro.ttf
  #       - asset: fonts/TrajanPro_Bold.ttf
  #         weight: 700
  #
  # For details regarding fonts in packages, see
  # https://flutter.dev/custom-fonts/#from-packages

# Generated by pub
# See https://dart.dev/tools/pub/glossary#lockfile
packages:
  _fe_analyzer_shared:
    dependency: transitive
    description:
      name: _fe_analyzer_shared
      url: "https://pub.dartlang.org"
    source: hosted
    version: "4.0.0"
  analyzer:
    dependency: transitive
    description:
      name: analyzer
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.39.10"
  archive:
    dependency: transitive
    description:
      name: archive
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.0.13"
  args:
    dependency: transitive
    description:
      name: args
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.6.0"
  async:
    dependency: transitive
    description:
      name: async
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.4.1"
  boolean_selector:
    dependency: transitive
    description:
      name: boolean_selector
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.0.0"
  build:
    dependency: transitive
    description:
      name: build
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.2.2"
  build_config:
    dependency: transitive
    description:
      name: build_config
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.4.2"
  build_daemon:
    dependency: transitive
    description:
      name: build_daemon
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.1.4"
  build_resolvers:
    dependency: transitive
    description:
      name: build_resolvers
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.3.7"
  build_runner:
    dependency: "direct dev"
    description:
      name: build_runner
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.9.0"
  build_runner_core:
    dependency: transitive
    description:
      name: build_runner_core
      url: "https://pub.dartlang.org"
    source: hosted
    version: "5.1.0"
  built_collection:
    dependency: transitive
    description:
      name: built_collection
      url: "https://pub.dartlang.org"
    source: hosted
    version: "4.3.2"
  built_value:
    dependency: transitive
    description:
      name: built_value
      url: "https://pub.dartlang.org"
    source: hosted
    version: "7.1.0"
  charcode:
    dependency: transitive
    description:
      name: charcode
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.3"
  checked_yaml:
    dependency: transitive
    description:
      name: checked_yaml
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.0.2"
  code_builder:
    dependency: transitive
    description:
      name: code_builder
      url: "https://pub.dartlang.org"
    source: hosted
    version: "3.2.1"
  collection:
    dependency: transitive
    description:
      name: collection
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.14.12"
  convert:
    dependency: transitive
    description:
      name: convert
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.1.1"
  crypto:
    dependency: transitive
    description:
      name: crypto
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.1.4"
  csslib:
    dependency: transitive
    description:
      name: csslib
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.16.1"
  dart_style:
    dependency: transitive
    description:
      name: dart_style
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.3.6"
  dataclass:
    dependency: transitive
    description:
      name: dataclass
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.3.0+1"
  dataclass_generator:
    dependency: "direct dev"
    description:
      name: dataclass_generator
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.3.0+2"
  fixnum:
    dependency: transitive
    description:
      name: fixnum
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.10.11"
  flutter:
    dependency: "direct main"
    description: flutter
    source: sdk
    version: "0.0.0"
  flutter_test:
    dependency: "direct dev"
    description: flutter
    source: sdk
    version: "0.0.0"
  glob:
    dependency: transitive
    description:
      name: glob
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.2.0"
  graphs:
    dependency: transitive
    description:
      name: graphs
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.2.0"
  html:
    dependency: transitive
    description:
      name: html
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.14.0+3"
  http_multi_server:
    dependency: transitive
    description:
      name: http_multi_server
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.2.0"
  http_parser:
    dependency: transitive
    description:
      name: http_parser
      url: "https://pub.dartlang.org"
    source: hosted
    version: "3.1.4"
  image:
    dependency: transitive
    description:
      name: image
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.1.12"
  io:
    dependency: transitive
    description:
      name: io
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.3.4"
  js:
    dependency: transitive
    description:
      name: js
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.6.2"
  json_annotation:
    dependency: transitive
    description:
      name: json_annotation
      url: "https://pub.dartlang.org"
    source: hosted
    version: "3.0.1"
  logging:
    dependency: transitive
    description:
      name: logging
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.11.4"
  matcher:
    dependency: transitive
    description:
      name: matcher
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.12.6"
  meta:
    dependency: transitive
    description:
      name: meta
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.8"
  mime:
    dependency: transitive
    description:
      name: mime
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.9.6+3"
  node_interop:
    dependency: transitive
    description:
      name: node_interop
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.1"
  node_io:
    dependency: transitive
    description:
      name: node_io
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.1"
  package_config:
    dependency: transitive
    description:
      name: package_config
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.9.3"
  path:
    dependency: transitive
    description:
      name: path
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.6.4"
  pedantic:
    dependency: transitive
    description:
      name: pedantic
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.9.0"
  petitparser:
    dependency: transitive
    description:
      name: petitparser
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.4.0"
  pool:
    dependency: transitive
    description:
      name: pool
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.4.0"
  pub_semver:
    dependency: transitive
    description:
      name: pub_semver
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.4.4"
  pubspec_parse:
    dependency: transitive
    description:
      name: pubspec_parse
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.1.5"
  quiver:
    dependency: transitive
    description:
      name: quiver
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.1.3"
  shelf:
    dependency: transitive
    description:
      name: shelf
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.7.5"
  shelf_web_socket:
    dependency: transitive
    description:
      name: shelf_web_socket
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.2.3"
  sky_engine:
    dependency: transitive
    description: flutter
    source: sdk
    version: "0.0.99"
  source_gen:
    dependency: transitive
    description:
      name: source_gen
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.9.5"
  source_span:
    dependency: transitive
    description:
      name: source_span
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.7.0"
  stack_trace:
    dependency: transitive
    description:
      name: stack_trace
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.9.3"
  stream_channel:
    dependency: transitive
    description:
      name: stream_channel
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.0.0"
  stream_transform:
    dependency: transitive
    description:
      name: stream_transform
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.2.0"
  string_scanner:
    dependency: transitive
    description:
      name: string_scanner
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.0.5"
  term_glyph:
    dependency: transitive
    description:
      name: term_glyph
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.0"
  test_api:
    dependency: transitive
    description:
      name: test_api
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.2.15"
  timing:
    dependency: transitive
    description:
      name: timing
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.1.1+2"
  typed_data:
    dependency: transitive
    description:
      name: typed_data
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.6"
  vector_math:
    dependency: transitive
    description:
      name: vector_math
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.0.8"
  watcher:
    dependency: transitive
    description:
      name: watcher
      url: "https://pub.dartlang.org"
    source: hosted
    version: "0.9.7+15"
  web_socket_channel:
    dependency: transitive
    description:
      name: web_socket_channel
      url: "https://pub.dartlang.org"
    source: hosted
    version: "1.1.0"
  xml:
    dependency: transitive
    description:
      name: xml
      url: "https://pub.dartlang.org"
    source: hosted
    version: "3.6.1"
  yaml:
    dependency: transitive
    description:
      name: yaml
      url: "https://pub.dartlang.org"
    source: hosted
    version: "2.2.1"
sdks:
  dart: ">=2.7.0 <3.0.0"

library dartmcts;
import 'dart:math';
var random = Random();
class InvalidMove implements Exception {}
abstract class GameState<MoveType, PlayerType> {
  GameState<MoveType, PlayerType> cloneAndApplyMove(MoveType move);
  List<MoveType> getMoves();
  GameState<MoveType, PlayerType> determine(
      GameState<MoveType, PlayerType> initialState);
  PlayerType winner;
  PlayerType currentPlayer;
}
class Node<MoveType, PlayerType> {
  GameState<MoveType, PlayerType> gameState;
  final Node<MoveType, PlayerType> parent;
  final MoveType move;
  int visits;
  final int depth;
  final Map<PlayerType, int> winsByPlayer;
  int draws;
  final GameState initialState;
  bool needStateReset = false;
  double c = 1.41421356237;
  Map<MoveType, Node<MoveType, PlayerType>> _children = {};
  Node(
      {this.gameState,
      this.parent,
      this.move,
      this.visits = 0,
      this.depth,
      this.winsByPlayer,
      this.draws,
      this.c})
      : initialState = gameState;
  determine() {
    gameState = gameState.determine(initialState);
  }
  resetState() {
    needStateReset = true;
  }
  addNewChildrenForDetermination(List<MoveType> moves) {
    for (var move in moves) {
      if (_children.containsKey(move)) {
        continue;
      }
      _children[move] = Node(
          gameState: gameState,
          move: move,
          parent: this,
          c: c,
          depth: depth + 1);
    }
  }
  Map<MoveType, Node<MoveType, PlayerType>> get children {
    // This GameState might not be selected during a simulation so we only generate
    // the children when necessary
    if (_children.isEmpty || needStateReset) {
      if (move != null) {
        gameState = initialState.cloneAndApplyMove(move);
      }
    }
    var moves = gameState.getMoves();
    addNewChildrenForDetermination(moves);
    return Map.fromEntries(_children.entries.where((x) => x.key == move));
  }
  double ucb1(PlayerType player) {
    if (parent == null || visits == 0) {
      return 0.0;
    }
    return (((winsByPlayer[player] ?? 0) + (draws * 0.5)) / visits) +
        (c * sqrt(log(parent.visits.toDouble() / visits)));
  }
  PlayerType getWinner() {
    return gameState.winner;
  }
  PlayerType currentPlayer() {
    return gameState.currentPlayer;
  }
  Node<MoveType, PlayerType> getBestChild() {
    if (children.isEmpty) {
      return null;
    }
    var sortedChildren = children.entries
      ..toList().sort((a, b) {
        var aVisits = a.value.visits;
        var bVisits = b.value.visits;
        if (aVisits == 0 && bVisits == 0) {
          return random.nextInt(100).compareTo(random.nextInt(100));
        }
        if (aVisits == 0) {
          return -1;
        }
        if (bVisits == 0) {
          return 1;
        }
        return -a.value
            .ucb1(currentPlayer())
            .compareTo(-b.value.ucb1(currentPlayer()));
      });
    return sortedChildren.first.value;
  }
  backProp() {
    var winner = gameState.winner;
    Node<MoveType, PlayerType> currentNode = this;
    while (currentNode != null) {
      currentNode.visits += 1;
      if (winner == null) {
        currentNode.draws += 1;
      } else {
        if (!currentNode.winsByPlayer.containsKey(winner)) {
          currentNode.winsByPlayer[winner] = 0;
        }
        currentNode.winsByPlayer[winner] += 1;
      }
      currentNode = currentNode.parent;
    }
  }
  Node<MoveType, PlayerType> getMostVisitedChild([List<MoveType> actualMoves]) {
    var currentChildren = children;
    if (actualMoves != null) {
      addNewChildrenForDetermination(actualMoves);
      currentChildren =
          Map.fromEntries(_children.entries.where((x) => x.key == move));
    }
    var sortedChildren = currentChildren.entries
      ..toList().sort((a, b) => a.value.visits.compareTo(b.value.visits))
      ..first.value;
    return sortedChildren.first.value;
  }
}
class MCTSResult<MoveType, PlayerType> {
  final Node<MoveType, PlayerType> root;
  final MoveType move;
  final List<Node<MoveType, PlayerType>> leafNodes;
  final int maxDepth;
  final int plays;
  MCTSResult({this.root, this.move, this.leafNodes, this.maxDepth, this.plays});
}
class MCTS<MoveType, PlayerType> {
  GameState<MoveType, PlayerType> gameState;
  double c = 1.41421356237;
  MCTSResult<MoveType, PlayerType> getSimulationResult(
      Node<MoveType, PlayerType> initialRootNode,
      {int iterations = 100,
      double maxSeconds,
      List<MoveType> actualMoves}) {
    var rootNode = initialRootNode;
    if (rootNode == null) {
      rootNode = Node(gameState: gameState, parent: null, move: null, c: c);
    }
    var plays = 0;
    var maxDepth = 0;
    var startTime = DateTime.now();
    var iterationsToRun = iterations;
    if (maxSeconds != null) {
      iterationsToRun = 9223372036854775807; // max integer value
    }
    while (plays < iterationsToRun) {
      rootNode.determine();
      if (maxSeconds != null) {
        var elapsedTime = DateTime.now().difference(startTime);
        if (elapsedTime.inSeconds > maxSeconds) {
          break;
        }
      }
      plays += 1;
      var currentNode = rootNode;
      while (currentNode != null &&
          currentNode.children.length > 0 &&
          currentNode.getBestChild() != null) {
        currentNode = currentNode.getBestChild();
        currentNode.resetState();
      }
      if (currentNode != null) {
        currentNode.backProp();
        maxDepth = max(maxDepth, currentNode.depth);
      }
    }
    var selectedMove = rootNode.getMostVisitedChild(actualMoves).move;
    return MCTSResult(
        root: rootNode, move: selectedMove, maxDepth: maxDepth, plays: plays);
  }
}

# dartmcts
A new Flutter package project.
## Getting Started
This project is a starting point for a Dart
[package](https://flutter.dev/developing-packages/),
a library module containing code that can be shared easily across
multiple Flutter or Dart projects.
For help getting started with Flutter, view our 
[online documentation](https://flutter.dev/docs), which offers tutorials, 
samples, guidance on mobile development, and a full API reference.

TODO: Add your license here.

## [0.0.1] - TODO: Add release date.
* TODO: Describe initial release.

# This file tracks properties of this Flutter project.
# Used by Flutter tool to assess capabilities and perform upgrades etc.
#
# This file should be version controlled and should not be manually edited.
version:
  revision: b041144f833e05cf463b8887fa12efdec9493488
  channel: stable
project_type: package

# Miscellaneous
*.class
*.log
*.pyc
*.swp
.DS_Store
.atom/
.buildlog/
.history
.svn/
# IntelliJ related
*.iml
*.ipr
*.iws
.idea/
# The .vscode folder contains launch configuration and tasks you configure in
# VS Code which you may wish to be included in version control, so this line
# is commented out by default.
#.vscode/
# Flutter/Dart/Pub related
**/doc/api/
.dart_tool/
.flutter-plugins
.flutter-plugins-dependencies
.packages
.pub-cache/
.pub/
build/
# Android related
**/android/**/gradle-wrapper.jar
**/android/.gradle
**/android/captures/
**/android/gradlew
**/android/gradlew.bat
**/android/local.properties
**/android/**/GeneratedPluginRegistrant.java
# iOS/XCode related
**/ios/**/*.mode1v3
**/ios/**/*.mode2v3
**/ios/**/*.moved-aside
**/ios/**/*.pbxuser
**/ios/**/*.perspectivev3
**/ios/**/*sync/
**/ios/**/.sconsign.dblite
**/ios/**/.tags*
**/ios/**/.vagrant/
**/ios/**/DerivedData/
**/ios/**/Icon?
**/ios/**/Pods/
**/ios/**/.symlinks/
**/ios/**/profile
**/ios/**/xcuserdata
**/ios/.generated/
**/ios/Flutter/App.framework
**/ios/Flutter/Flutter.framework
**/ios/Flutter/Flutter.podspec
**/ios/Flutter/Generated.xcconfig
**/ios/Flutter/app.flx
**/ios/Flutter/app.zip
**/ios/Flutter/flutter_assets/
**/ios/Flutter/flutter_export_environment.sh
**/ios/ServiceDefinitions.json
**/ios/Runner/GeneratedPluginRegistrant.*
# Exceptions to above rules.
!**/ios/**/default.mode1v3
!**/ios/**/default.mode2v3
!**/ios/**/default.pbxuser
!**/ios/**/default.perspectivev3
!/packages/flutter_tools/test/data/dart_dependencies_test/**/.packages