4
$\begingroup$

I've seen data sets for classification / regressions tasks in domains such as credit default detection, object identification in an image, stock price prediction etc. All of these data sets could simply be represented as an input matrix of size (n_samples, n_features) and fed into your machine learning algorithm to ultimately yield a trained model offering some predictive capability. Intuitively and mathematically this makes sense to me.

However, I'm really struggling with how to think about the structure of an input matrix for game-like tasks (Chess, Go, Seth Blings Mario Kart AI) specifically (using the Chess example):

  1. How would you encode the state of the board to something that a model could train on? Is it reasonable to think about the board state as a 8x8 matrix (or 1x64) vector with each point being encoded by a numerical value dependent on the type of piece and color?
  2. Assuming a suitable representation of the board state, how would the model be capable of making a recommendation given that each piece type moves differently? Would it not have to evaluate the different move possibilities for each piece and propose which move it "thinks" would have the best long term outcome for the game?

  3. A follow up on 2 - given the interplay between a moves made now and moves made n moves into the future how would the model be able to recognize and make trade-offs between moves which may offer a better position now vs those that offer a position n moves in the future - would one have to extend the board state input to a vector of length 1x64n where n is the total number of moves for expected for an individual player or is this a function of a different algorithm which should be able to capture historical information which training?

I am unsure if I'm overthinking this and am missing something really obvious but I would appreciate any guidance in terms of how to approach thinking about this.

$\endgroup$
  • $\begingroup$ Welcome to AI! Very good questions, imo. (I've taken the liberty of adding a couple of tags to improve searchability.) $\endgroup$ – DukeZhou Jan 3 '18 at 17:32
  • 2
    $\begingroup$ Update: I've come across this blog post which runs through Reinforcement Learning and tackles almost all of the questions listed in the original post. I'm unsure if encoding the game in pixels would still work given the complexity with pieces and their unique movements but it's a start. $\endgroup$ – ZYH Jan 12 '18 at 15:40
1
$\begingroup$

The core of the question seems to really be: "how to approach thinking about this", where "this" is the input of an AI player.

Modern attempts at game playing AI players try to replace a human player "as is". No advantage whatsoever. This implies that we want to feed the same "raw input" to the software player and to the human player. For a video game, the raw input is usually the screen we see, but it could also include sound, vibration feedback from a game controller, force feedback from driving gears, etc. Basically any sensor input available. For a physical board game like Go, the raw input could be a video feed, as done for AlphaGo. Doing so, we fall back to the video game approach. So the input to the AI player is often a tensor, where each element is the intensity of a screen pixel, or some other sensor signal (note there is nothing here about the shape of the tensor, please see below).

The way of thinking here is actually pretty simple, and neat: We want an AI player to replace a human player. So we list up what the human player can sense, and model each input as a tensor (this includes vectors and matrices).

There is perhaps a subtlety here. We face choices not so obvious to make, and there are usually trials and errors (many errors). For example, the Deep-Q Network from DeepMind to play Atari games takes as input differences between two consecutive video frames. Some other approach could solve the same problem with actual sequences of inputs (e.g. 10 consecutive frames). The two approaches are valid---they just have different tradeoffs we must evaluate to find the best configuration.

Another subtelty is the "shape" of the input. Should a single (W, H) input frame be a (W*H) vector, or a (W, H) matrix, or something else? The ramifications can go far. If the frame is an RGB frame with transparency, the input could well be a tensor of shape (W, H, 4), a "cubic volume" with 4 "slices" of shape (W, H)---one for each RGB channel, and a fourth one for transparency. Imagine now if you also have sound, and can add a fifth "slice"---and more if you have stereo or Dolby system channels.

Last point: There is no reference to the architecture of the AI player beyond the input here. Although most exemples refer to recent architectures based on neural networks, this "thinking" also applies whatever can leverage the input. For example, the Big Blue system from IBM, who won Chess against Gary Kasparov, is an AI player using exclusively (if my memory's good) clever tree search. Yet its input is a tensor representing the Chess board.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.