未加星标

A JavaScript Connect Four AI

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二05 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

Might I interest you in a rousing game of Connect Four ? You and the computer take turns dropping discs into one of the seven colums below. The goal is to get four pieces of your color in a row (vertically, diagonally, or horizontally).

Winner: none yet... Player {{winner}}

Draw: no yes


A JavaScript Connect Four AI

That’s an AngularJS powered Connect Four AI that was originally written in C and then compiled to javascript using Emscripten . It runs the actual AI in a web worker to prevent your browser from locking up.

It was implemented using techniques from Stuart Russell and Peter Norvig’s excellent book, Artificial Intelligence: A Modern Approach (3rd Edition) . These techniques might not create the best Connect Four AI possible (in fact, Victor Allis’ thesis shows how to create a provably-unbeatable AI ), but it can still do pretty well! The code (in C, python, and JavaScript) is available on GitHub .

The main idea behind the AI is adversarial search . Think of all the possible games of Connect Four represented as a tree. The root of the tree is the empty board. The second tier of the tree represents all the possible moves that can be made by the first player. The third tier of the tree represents all the possible moves that can be made by the second player.

A small subset of the tree (for a small game board) might look like this:


A JavaScript Connect Four AI

Imagine expanding the tree all the way down to the bottom, where the leaf nodes are “terminal” states states where one player has won the game, or there is a draw. In order to make moves, the AI applies a minimax strategy . In other words, the AI assumes that its opponent will always play optimally, and thus tries to minimize the maximum gain of its opponent.

This tree is really big. The branching factor is approximately seven, and the depth of the tree could be as high as 42. So, while the the perfect tree formula would tell us that there are

boards, some smart mathematicians have figured out that there are “only” around 4 trillion different boards

. That’s still way too many to examine.

Thankfully, we can use a technique called alpha-beta pruning . The idea is pretty simple: do not bother searching branches that would either:

require our opponent to make a detrimental move (to get an outcome less than the outcome they could get if they played optimally) or, require us to make a move that was less advantageous than another move we could make

Now, this is a hand wavey oversimplification of how the process actually works. I suggest you read the chapters in Russell and Norvig, or fuss through the Wikipedia page, to get a better understanding.

In the average case, alpha-beta pruning reduces the number of nodes we need to evaluate from

to

. This brings us from 4 trillion boards to around 2.7 billion boards. A pretty good drop but still not enough for us to enumerate.

Next, we employ a heuristic function. Since we can’t reach the bottom of the tree, we’ll go down a certain depth and then make some kind of guess as to whether or not the board we are evaluating is a winning or losing board. I used a very simple heuristic: the number of possible four-in-a-rows. The computer would calculate how many ways it could win using alignments present in the current board, and then subtract the number of ways the computer’s opponent could win.

Now, the computer will exhaustively evaluate the tree to a certain depth (the number of moves to “think ahead”) and then use a heuristic to evaluate that board. Eventually, as the end of the game draws near, the computer finds winning or losing states within the prescribed depth, and plays perfectly. The hope is that the heuristic function can guide the AI to a winnable position. It seems to work pretty well if you can beat it, try increasing the number of moves to think ahead. It’ll make it slow down, but it’ll get exponentially more difficult.

Oh there’s one more complication. A lot of the boards that you encounter when going down the tree are duplicates (there is more than one way to get to a state). To avoid recomputing the desirability of these boards, we store them in a hash table.

It also looks like writing this type of AI is homework for AI classes at Cornell , Northeastern , and Purdue . I could only find one other Javascript Connect Four AI , which moves substantially faster than mine, but is easily defeated (which is exactly the behavior one would expect).

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

主题: JavaJavaScriptGitAngularJSGitHubPython
分页:12
转载请注明
本文标题:A JavaScript Connect Four AI
本站链接:http://www.codesec.net/view/481289.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(30)