AI And Uncertainty

AI is the technique of uncertainty management in computer software. AI is the discipline that you apply when you want to know what to do when you don’t know what to do.

Reasons for uncertainty

  • sensor limit
  • stochastic environment
  • laziness
  • ignorance – we don’t know

 

 

Uncertainty is designed into games, most notably in gambling, where chance is central to play.

 

Advertisements

Computer – Bridge Problem

The well known strategy card game bridge playing for computers is as hard as it is for humans. The decision theoretic, imperfect information and uncertainty aspects of pokers makes it a perfect test bed for many AI fields including machine learning.

Reinforcement learning (or latetest deep reinforcement learning) might be the best approach, as the case for many other AI games, nevertheless supervised learning is possible if you could get historical logs including winning information.

The problem can be broken down into :

Hand Strength estimation:
This is to estimate the winning potential of player’s own hand as well as the opponents, based on open cards. The most successful ones are using monte carlo sampling based. The idea is to complete the hands by sampling for inaccessible cards and count the #wins, and there by estimating the probability.
Exact computation of winning probability is slower than sampling. Parametric estimation using historic data might find some machine learning applications.

Opponent modeling:
This involves estimating the probability for available actions (pay card) for each opponent. Here we can use the players historic  data for estimation. One successful approach is using neural network for  opponent modeling (1). They consider various factors like player count, position, game type etc. Of course there could be different approaches.

Decision making and Risk management:
This involves coming up with utility functions and listing, rating strategies. This is one potential area for ML. We can score strategies based on historical or current data.

Approaches:
Various approaches have been tried. some of them are :
1) Probabilistic  approaches ( Bayesian networks (2) etc)
2) Rule based (event, action pairs)
3) Function based (neural networks , etc)
4) Genetic algorithms (3)

If by machine learning you mean classification and regression then these techniques have been used to predict the probability of an opponent action given a situation. This was used by Aaron Davidson in Page on cs.ualberta.ca A more elaborate technique that took account of both the current player and similar players was explored in Bayes-Relational Learning of Opponent Models from Incomplete …
If you extend machine learning to include the computation of Nash Equilibria then many computer poker researchers are doing that. Google
If you include cased based learning then there is SARTRE: System Overview. A Case-Based Agent for Two-Player… There is plenty of scope for applying Bayes theorem in poker: one example would be Bayes’ Bluff: Opponent Modelling in Poker

Courses

  1. AFCAI – Deepak Khemani
  2. Scheams in problem solving – Sandra Marshal
  3. SOAR Cognitive architecture – J Laird
  4. Knowledge Representation and Reasoning – Brachman and Levesque
  5. Meta Reasoning – Anita Raja
  6. Reasoning About Knowledge – J Halpern
  7. Logic In Games – Van Benthem
  8. Game Theory – Osborne
  9. Epistemic Game Theory  –
  10. Algorithmic Game Theory – Tim roughgarden
  11. Multi Agent Systems – yovav soham
  12. Machine Learning – Tom mitchell
  13. Artifical Neural Networks – Yagna narayana

The above are from books

 

from online courses

  1. Society of mind : Marvin minsky
  2. AI : P H winston
  3. Knowledge based AI: Ashok goel
  4. Machine learning:  Andrew Ng
  5. Natural language processing: Gurafsky
  6. Game theroy: K L brown

 

 

Deep Reinforcement Learning for Bridge

KBANN;

http://www.nature.com/nature/journal/v518/n7540/full/nature14236.html

David Silver

Google DeepMind

Deep Reinforcement Learning

http://auai.org/uai2015/invitedSpeakers.shtml

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

Lec 6:Common Knowledge and Agreement

Common knowledge is a fundamental notion of group knowledge.

Common knowledge is a necessary and sufficient condition for reaching an agreement and for coordinating actions.

Three famous illustrations:

  1. Coordinated attack.
  2. Agreeing to disagree.
  3. Simultaneous byzantine agreement.

Relation between common knowledge and agreement:

 

Formally capture the cognition: