CPLUSGEARS
  • Blog
  • Projects and Papers
  • Lecture Notes
  • ROS/Gazebo Tutorial
    • Lesson 1: Set-up
    • Lesson 2: URDF and XACRO
    • Lesson 3: Robot Plugins
    • Lesson 4: Programming our Rover
    • Lesson 5: Adding a LIDAR
  • Contact

Accelerating Tree Searches of Games of Imperfect Information

1/2/2020

0 Comments

 
A little bit ago I wrote about the Reconnaissance Blind Chess tournament and how my bot worked.

What you might notice is that for this game of RBC I used a chess engine, and had to have code around it to make up for the fact that RBC isn't really straight chess. Because of that there are some notable flaws:
  • The engine assumes that it would know if it was put into check. In RBC you might not know, and this could cost you the game.
  • The engine assumes that whatever board state you give it is true. This means that the "information value" of a move isn't taken into account.
What bothered me the most is that second point. In the game you could do things like telling the queen to move across the entire board, knowing it will be stopped at some point, but not knowing exactly where until it was. This could eliminate many board states and be an interesting and worthwhile move, but would not ever be even considered by a usual chess engine.

If you were to try to write a tree search which took into account the sets of potential boards you would run into another problem. The imperfect information version of chess has an exponentially larger tree than regular chess, which is already a pretty massive game.

In order to even approach searching that tree you would need some way of accelerating your tree search.

To do this I developed a small algorithm which in my very preliminary testing gives around a 3 times speedup with logarithmic time and poly-logarithmic space complexity


Read More
0 Comments

Reconnaissance Blind Chess

1/2/2020

2 Comments

 
Last summer I saw a posting about a competition called Reconnaissance Blind Chess. I have always been really fascinated by games so I decided to throw my hat in the ring.

A few weeks ago, with the competition all done, I was invited to NeurIPS by the JHUAPL to talk about how my bot worked.

I figured that it might be a bit interesting to other people then, to hear how my bot worked.

Read More
2 Comments

    Author

    Hi, I'm Billy, a PhD student studying Math.

    Github

    Archives

    January 2020
    August 2019
    April 2019
    December 2018
    June 2018
    April 2018
    March 2018

    Categories

    All
    AI
    Equi
    Games
    Manifold
    Ml
    Programming Language
    Ros
    Senior Thesis

    RSS Feed

  • Blog
  • Projects and Papers
  • Lecture Notes
  • ROS/Gazebo Tutorial
    • Lesson 1: Set-up
    • Lesson 2: URDF and XACRO
    • Lesson 3: Robot Plugins
    • Lesson 4: Programming our Rover
    • Lesson 5: Adding a LIDAR
  • Contact