ゲーム
ゲームの必勝法探索問題それ自身の困難性は、今のところ定義されておらず、ゲームのクラスに対する必勝法探索問題の困難性が定義されている。
ハミルトンゲームはNP完全問題である。(先手後手あわせて)n手で終了するゲームの必勝法を探索する問題は
∑ n P ∪ ∏ n P {\displaystyle \sum _{n}P\cup \prod _{n}P}
に属する。
(一般化された)しりとりはPSPACE完全問題である。
尚、二人零和有限確定完全情報ゲームには必勝法があることが知られている。
他のボードゲームは戦略と幸運の要素を結合する。バックギャモンは2つのサイコロのロールに基づいた最もよい戦略的な動きを決定することをプレイヤーに要求する。トリビアゲームは、人が得る問題に基づいたたくさんの無作為性を持っている。ユーロゲームは、多くのボードゲームより幸運のファクターがやや少ないことがしばしば存在することについて有名である。
ボードゲームのグループは、上で述べられているトリヴィアゲーム、ユーロスタイルボードゲームのほかにレースゲーム、ロール・アンド・ムーブ・ボードゲーム、アブストラクトゲーム、言葉遊び、ウォー・シミュレーションゲームを含む。いくつかのボードゲームは複数のグループに属し、他のジャンルの要素を含んでいる。たとえば、クラニアムはひとつの人気のある例であり、プレイヤーは4つの主要なスキルのそれぞれに成功しなければならない:芸術性、ライブパフォーマンス、トリヴィア、語学力。 子供は楽しがって遊ぶだろう。
囲碁、将棋、オセロなどは、現在の相手の手がすべて分かるという意味で、隠された情報がないゲームである(完全情報ゲーム)。
これに対し、ポーカー、麻雀などは、相手の手など、プレイヤーから隠された情報を推測するという要素の加わるゲームといえる(不完全情報ゲーム)。 電子ゲームではなくおもちゃである。
RPGとしばしば省略されて呼ばれるロールプレイングゲームは、通常、参加者が虚構の設定上で活動するキャラクターの役割を受け持つタイプのゲームである。本来のロールプレイングゲームという用語が指す、テーブルトークロールプレイングゲーム(TRPG)とも呼ばれるこれらのゲームは通常、テーブルに向かい合った複数人の参加者によってプレイされ、筆記具と紙を用いたフィクションの展開に終始傾注する。
プレイヤーたちは協力して、彼らのキャラクターに関連した設定を作り、その設定を発展させ、探求し、また他人になりきって日常生活の枠を飛び越えた冒険を経験することになる。今日のテーブルトークロールプレイングゲームは、伝統的なジャンルの境界を越えて、様々な作品が作られており、戦闘重視なものから、よりストーリー重視なものまで、数百種類のゲームが存在している。
ロールプレイングゲームという用語は、今日ではコンピュータRPGを指すためにも使われる(日本ではより一般的でもある)。あらかじめプログラムされた状況とストーリーを単独のプレイヤーが遊ぶゲームであることが多いが、インターネットの発達により、MORPG、MMORPGと呼称される小規模・大規模の複数プレイヤーが参加するコンピュータRPGも存在する。
また、一人で、コンピュータを用いずにプレイできるテーブルトークロールプレイングゲームとして、ゲームブックなども存在する。
なおコンピュータを用いず、ロールプレイング形式で行われるシミュレーションについては、「シミュレーション」を参照。
タイムシェアリング方式の電話回線でつないだコンピュータの時代から、オンラインゲームは一応行われていた。PLATOなどの初期の商用システムは厳密に教育的な分野と少なくとも同じくらいゲームによって有名であった。1958年、Tennis for Twoは訪問者の日を支配し、ブルックヘブン国立研究所のオシロスコープに注意を引きつけた。1980年代、パロアルト研究所は主にメイズウォーによって知られていた。それは訪問者に実地のデモとして提供された。パソコンで遊べるゲームはフラッシュゲームなどもある。とはいえ、これはアメリカの研究所の研究員の話であり、世界中の一般人はこんなことはできなかった。
一般の人々にとっては、1980年代後半のパソコン通信の時代でもオンラインゲームはあまり一般的ではなかった。1990年からすこしづつインターネットが普及したが、最初は従量制で時間あたりの料金が高すぎて、おまけに回線速度もとても遅かったので、オンラインゲームは普及しなかった。普及したのは、プロバイダー同士の競合が激化して、安い定額料金が設定され安心して遊べるようになり、回線の高速化つまりブロードバンドや光回線が一般的になってからである。
現在のオンラインゲームはインターネット接続を使用して行われる。いくつかがクライアントプログラムを献呈した一方、ブラウザゲームはウェブブラウザのみを必要とする。いくつかのより簡単なブラウザゲームは、ビデオゲームをほとんどしない人口統計のグループ(特に女性と中年)にアピールする。
ビジネスゲームはインタラクティブなボードゲームから、違う支柱(ボール、ロープ、輪など)と活動のさまざまな種類に関係しているインタラクティブゲームまでのさまざまな形式を取ることができる。これらのゲームの目的は組織的な性能のいくつかの面にリンクし、ビジネスの発展についての議論を生成することである。多くのビジネスゲームは組織的な行動に注目する。これらのいくつかがコンピュータシミュレーションである一方、他方はプレイと情報の聞き出しによるシンプルなデザインである。チームビルディングはそのような活動の共通のフォーカスである。
球技などのスポーツの試合というゲームがあるが、そういうゲームとのかかわりかたは、試合に参加する方法と、見て楽しむという方法がある。
スタンリー・フィッシュは、社会的なとりきめによる規則の操作の明白な例として、野球のボールとストライクを挙げた。ストライクゾーンというのは人々がそれがあるとみなすことに互いに合意した場合だけ存在している。物理的な実体はまったく無い。人々の心の中の決めごとによって生み出されているのである。そして、どの投球も、権限を与えられた審判員の判定によって「ストライク」とか「ボール」などと声でラベルを付けて分類されるまで、ボールでもストライクでもない。
なお、すべてのスポーツがゲームというわけではない。たとえば競走や体操などは、近代オリンピックにおいてどう扱われていようが、クロフォードなどの定義によるゲームにはあたらない。彼らは間接的な方法で互いに挑むのみである。直接的に相手に干渉したりはしない。
eスポーツについては次節 #対戦ゲーム、eスポーツ を参照のこと。
ランダム性(乱数的な要素)の有無という視点である。確定ゲーム (deterministic game) と不確定ゲーム(確率的ゲーム、probabilistic game) といった用語がある。
probabilistic gameの例として、各種トランプゲーム、まわり双六、バックギャモンなどがある。トランプゲームにおいてはカードをシャフルする(かき混ぜる)事がランダムさの源で、まわり双六やバックギャモンにおいてはサイコロの目に従うことがランダムさの源である。
deterministic gameの例としては囲碁、将棋、チェス、チェッカー、ダイヤモンドゲームなどがある。これらのゲームでは偶然の要素はないが、将棋などの「振り駒」で先手、後手を不確定ゲームで決めることは行われる。
フランス人社会学者のロジェ・カイヨワは、著書『遊びと人間』("Les jeux et les hommes")のなかで、以下のようにゲームを定義した。すなわち、楽しみのために行なわれること、時間と場所が区切られていること、勝敗が不確定であること、何かを生産するものではないこと、法律やルールに支配されること、現実の活動から意識的に切り離されていることをゲームの参加者が知っていることである。また彼は、playに対応するパイディアPaidea(娯楽)の類型に対するものとして、ルール的制約をもちgameに対応するルドゥスLudus(闘技)を提案した。